名人に勝つコンピュータ将棋の開発

点击翻译按钮获取中文摘要

名人に勝つコンピュータ将棋の実現に向けて,動的なマージンを用いるFutility Pruningの提案,部分局面n-gram法の改良,詰め将棋探索で問題となる二重カウント問題の有効な対処法としてWeak Proof Number Searchの開発などを行った。マージンを用いるFutility Pruningの研究について,これまでfutility pruningは,チェスでは有効であるが将棋では探索空間の広大さと選択的探索が主流な事もあり,有効ではないと考えられていた枝刈り技術であった。しかし近年futility pruningを将棋に用いたBonanzaが好成績を収めて以降将棋でもfutility pruningが注目されることになった。futility pruningは大雑把な評価値にマージンを持たせαβのWINDOWから十分外れている場合に枝刈りをする技術である。これまでfutility pruningで用いるマージンには定数が用いられていたが,局面状況によって適切なマージンが変化すべきである場合に対応できないという問題があった。そこで,まずfutility pruningのマージンを定数で扱っている事による問題点を解析し,その改良案として,探索毎に動的なマージンを決定するアルゴリズムを提案,実装し評価を行った。その結果,動的なマージンを用いたfutility pruningが従来のものに比べて175勝138敗1分で統計的に有意に勝ち越し,その優秀性を証明することができた。部分局面n-gram法の改良では,プロ棋士の棋譜から頻度の高い指し手列を抽出し低ノイズで探索に組み込むことに成功した。また,指し手列の出現頻度をカウントし実現確率探索の遷移確率として扱うことでより人間らしい手筋を効率的に読ませることで探索の強化に成功した。詰み探索では従来のdf-pnに代わる二重カウント問題に影響されない新たな探索法Weak Proof Number Searchを提案し,ベンチマークテストでは611手詰みの「寿」をわずか数秒で解くなど従来手法に比べて圧倒的な性能を示した。