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

开发打败高手的电脑将棋

基本信息

批准号：
18800017
负责人：
橋本剛
金额：
$ 1.54万
依托单位：
Japan Advanced Institute of Science and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (Start-up)
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

项目摘要

名人に勝つコンピュータ将棋の実現に向けて,動的なマージンを用いる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手詰みの「寿」をわずか数秒で解くなど従来手法に比べて圧倒的な性能を示した。

为了实现能够击败大师的计算机将棋，我们提出了使用动态边距的无用剪枝，改进了部分位置n-gram方法，并使用弱证明数作为处理Tsume中存在的重复计算问题的有效方法将棋搜索开发等关于使用边际的效用剪枝的研究，效用剪枝是一种在国际象棋中有效的剪枝技术，但由于搜索空间大和选择性搜索而被认为在将棋中无效。然而，近年来，由于Bonanza在将棋中使用无效修剪并取得了良好的效果，无效修剪在将棋中也引起了人们的关注。无效剪枝是一种给粗略评估值留出余量，并在其充分位于αβ WINDOW之外时对其进行剪枝的技术。到目前为止，效用剪枝中使用的边距一直使用常量，但存在一个问题，即它无法处理适当边距应根据情况而变化的情况。因此，我们首先分析了将效用剪枝余量视为常数所带来的问题，并提出、实现和评估了一种动态确定每次搜索余量的算法作为改进计划。结果，使用动态边际的效用剪枝在统计上比传统方法具有显着优势，有 175 胜、138 负和 1 平，证明了其优越性。通过改进部分位置n-gram方法，我们成功地从职业将棋棋手的比赛记录中提取频繁出现的走法序列，并将其合并到低噪声的搜索中。此外，通过计算棋步序列出现的频率，并将其视为实现概率搜索中的转移概率，我们能够有效地读取更多类似人类的棋步，并成功地加强了搜索。我们提出了一种新的搜索方法Weak Proof Number Search，它不受重复计数问题的影响来替代传统的df-pn进行死锁搜索，并且在基准测试中，它在短短几秒钟内解决了611个死锁“kotobuki”，与传统方法相比，它表现出了压倒性的性能。