将棋の合法手の数の統計

AlphaZero方式の強化学習では、指し手の確率分布を教師データとするため、局面の合法手の数の分だけ確率の値を保存しておく必要がある。
将棋の合法手の最大数は593であることが証明されているが、実際の対局ではそのような局面は現れない。
教師データを保存する容量を抑えるために、できれば実際に現れる局面の最大数に制限したい。
可変長フォーマットにするという案もあるが、機械学習でシャッフルやランダムサンプリングするため、固定長フォーマットにしておきたい。

そこで、実際の棋譜で合法手の数の統計量を調べてみた。

調査方法

以下のようなスクリプトでmatplotlibでヒストグラム表示と、Pandasで統計量を出力した。CSAファイルの解析にはcshogiを利用した。

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from cshogi import *
import sys
import glob

legal_moves = []

def read_kifu(kifu_list):
    positions = []
    parser = Parser()
    for filepath in kifu_list:
        parser.parse_csa_file(filepath.encode('utf-8'))
        board = Board()
        for move in parser.moves:
            legal_moves.append(len(board.leagal_move_list()))
            board.push(move)

kifu_list = glob.glob(sys.argv[1] + r"\*")

read_kifu(kifu_list)

plt.hist(legal_moves)
plt.show()

print(pd.Series(legal_moves).describe())
print(np.percentile(legal_moves, 99))
print(np.percentile(legal_moves, 99.9))

floodgateの1年分の統計

floodgateの2018年の棋譜を調査した結果は以下の通り。

count    4.754067e+06
mean     8.223365e+01
std      5.962379e+01
min      1.000000e+00
25%      3.800000e+01
50%      7.400000e+01
75%      1.110000e+02
max      4.730000e+02

99パーセンタイル	266
99.9パーセンタイル	347

棋譜数は47,813、局面の総数は4,754,067局面で、平均は82.2手で、最大は473手だった。
将棋の合法手の平均は約80手と言われているので、近い値になっている。
99.9パーセンタイルは347手で、ほとんどの局面で合法手の数は347手に収まっている。

elmoの自己対局で生成した教師データ

elmoの自己対局で生成した1000万局分でも調べてみた。

count    1.000000e+07
mean     1.021326e+02
std      6.950770e+01
min      1.000000e+00
25%      4.600000e+01
50%      9.600000e+01
75%      1.480000e+02
max      4.860000e+02

99パーセンタイル	284
99.9パーセンタイル	350

平均は102.1手、最大は486手、99.9パーセンタイルは350手だった。
平均がfloodgateの棋譜に比べて高いのは初期局面集を使っているためと思われる。

dlshogiの強化学習で生成した局面

dlshogiの強化学習で生成した250万局面でも調べてみた。

count    2.498567e+06
mean     9.635840e+01
std      6.277702e+01
min      2.000000e+00
25%      4.600000e+01
50%      8.900000e+01
75%      1.360000e+02
max      4.980000e+02

99パーセンタイル	275
99.9パーセンタイル	352

こちらも初期局面集を使用している。
平均は96.3手、最大は498手、99.9パーセンタイルは352手だった。

まとめ

調査した範囲で最大の合法手の数は、498手だった。
99.9パーセンタイルは352手のため、352に制限して、それを超えた分は、0に近い確率になっているはずなので除外しても問題なさそうである。
99パーセンタイルの284手に制限しても実用上問題ないかもしれない。

LeelaChessZeroではどうしているかソースを調べてみたところ、policyの出力のサイズでそのまま保存するという贅沢な使い方をしていた。
ディスクサイズとメモリサイズをケチるという発想はないようである。