合法手の話

その昔，"指し手生成祭"という祭があったようです。（詳しくはググってください。）

将棋の局面で反則にならない手が何種類あるかってのをリストにする速度を競ってたそうです。私は先日Go言語で組んだのだとざっくり200kくらいが最高値でした。たぶん一桁負けてますね。

これが何に有効かというと速度の問題ももちろんですが，探索の枝の生成になります。コンピュータ将棋の本質は木探索なので枝の数とかその性質とかが重要ですね。

　

 　

枝の数が気になるってことで，python-shogiでざっと棋譜読んで数えさせてみました。

こういうときはカジュアルなライブラリが便利です。

　

bleu48.hatenablog.com

　

まぁ，こんな感じで簡単に数えられますね。

kifフォルダ以下のkifファイルを全部読んで全局面の合法手生成をしますのでちょっと時間かかります。

　

import shogi.KIF
import os

def find_all_files(directory):
for root, dirs, files in os.walk(directory):
  for file in files:
    yield os.path.join(root, file)
num_board=0
sum_moves=0
for filepath in find_all_files("kif"):
  kif = shogi.KIF.Parser.parse_file(filepath)[0]
  board = shogi.Board()
  for move in kif['moves']:
    board.push_usi(move)
    moves=[]
    for m in board.legal_moves:
      moves.append(m)
    sum_moves += len(moves)
    num_board += 1
print("局面数",num_board,"総合法手数",sum_moves,"局面当たりの平均合法手数",sum_moves/num_board)

 　

沢山やると遅いので，うちの選手権棋譜24局だけですが

局面数 3920 総合法手数 387904 局面当たりの平均合法手数 98.95510204081633

ってことで，割と手が広いようです。 

皆さんも手持ちの棋譜で調べてみてください。