詰将棋におけるdf-pn+探索のための，展開後の証明数と反証数を予測する評価関数

• 金子, 知適

• 田中, 哲朗

• 山口, 和紀

• 川合, 慧

書誌事項

タイトル別名

• Evaluation Function for df-pn+ in Shogi based on Prediction of Proof and Disproof Numbers after Expansion

抄録

本稿では，実戦での詰将棋探索を効率的にすることを目的に，将棋の棋譜にあらわれる局面を対象に詰みやすさを予測する評価関数について提案し，df-pn+探索と組み合わせて効果を確認した．詰将棋ではdf-pn探索が効果的であることが知られているが，それに評価関数を組み合わせたdf-pn+探索は，評価関数設計の難しさからあまり使われていなかった．そこで，本稿では機械的な方法で評価関数を作ることを試みた．具体的には，df-pn+探索の評価関数の一つである，局面の証明数と反証数の初期値を設定する関数に着目し，その関数の調整方法として，訓練例の局面についてdf-pn探索で指定のノード数を探索した後の証明数と反証数をあらかじめ求め，評価関数にそれらの値を予測させる方法を提案した．実際に，何種類かの特徴量を用いた評価関数について，実戦の棋譜に表れた約30万局面を用いてパラメータを最小二乗法手法により自動的に調整し，別の実戦に表れた約千局面を対象に実験を行った．その結果，作成した評価関数を用いたdf-pn+探索は，評価関数を用いないdf-pn探索に比べて，効果的に詰や不詰を発見できることを確認した．最も良い評価関数の場合，平均して半分以下の探索ノード数で詰を発見した．

Evaluation functions for checkmate search in Shogi-game are proposed, that are suitable for df-pn+ search. They estimate initial values of proof number and disproof number in a newly expanded state in the search. We trained evaluation functions so that they predict proof numbers and disproof numbers of a given state after expansion by normal df-pn search of specified number of nodes. The parameters in our evaluation functions were statistically determined by means of least mean squares, by using states appeared in real game records. Our experiments showed that df-pn+ search combined with the proposed evaluation functions were actually more efficient than df-pn search without any evaluation function, for proving or disproving states appeared in real game records. With the best evaluation function, the number of node expanded was reduced to half on average.

収録刊行物

• ゲームプログラミングワークショップ2004論文集

  ゲームプログラミングワークショップ2004論文集 2004 14-21, 2004-11-12

詳細情報

• CRID: 1050011097125760896
• NII論文ID: 170000080208
• Web Site: http://id.nii.ac.jp/1001/00097541/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN