コンピュータ将棋とは、将棋の対戦を目的としたコンピュータプログラムのこと。
背景
チェスや将棋、囲碁のように二人で行い、利害の合計が0(勝ち1、負け-1、引き分け0)で、指し手が有限で、偶然の要素がなく、相手の選択が常に把握できるゲームを二人零和有限確定完全情報ゲームという。
このゲームは理論上先手必勝、後手必勝、引き分けのいずれかに決定する。但し一局の選択肢はチェスで10の120乗、将棋で10の220乗、囲碁で10の360乗と宇宙の原子の数10の80乗より多い。そのため、いずれも解明には至っていない。
探索と評価関数
将棋は、形勢を判断する大局観と選択肢を考える読みで指し手を決める。コンピュータ将棋において、大局観と読みに相当するものが評価関数と探索になる。
評価関数
持ち駒の数や駒の配置、効き、手番等を点数化し合計した関数のこと。評価関数で特定の局面を計算したものを評価値という。評価値が高いほど形勢が良いと判断する。
探索
ある局面の有効な指し手を探す技術のこと。将棋は選択肢が膨大なため、限られた時間で効率よく探索を行う必要がある。基本的な探索手法にミニマックス法がある。これは評価値が相手の手番で最小、自分の手番で最大になるように探索する手法のこと。
たとえば選択肢が2つずつあり2手目まで探索する時、2手目(相手番)には4つの選択肢となる。これはトーナメント表のような図(ゲーム木)で表せる。2手目の局面の評価値がそれぞれ左から1,3,5,7だった時、1と3の最小1と、5と7の最小5が指し手の候補となる。
次に1と5から最大を選択する。つまり評価値5の局面を目指す指し手に決定する。この時、もし探索領域外(評価値5の局面の先)に突然不利な局面が現れるとしてもそれを読むことはできない。これを水平線効果という。
Bonanzaの登場
2005年、化学者の保木邦仁が将棋ソフトBonanzaを開発した。Bonanzaは以下に示す様々なアイデアによって、2006年ライバルが高スペックPCを使用する中、ノートPCで世界コンピュータ将棋選手権に初出場し優勝した。
ボナンザメソッド
評価関数を自動で調整する手法のこと。それまでは開発者が人力で評価関数を調整していた。Bonanzaはプロの棋譜(教師データ)から、プロの指し手を正解として評価関数を自動で調整した。このように正解を提示して学習させる方法を教師あり学習という。
玉と他2駒の位置関係で局面を捉える評価関数のこと。勝利の三角形ともいう。
広く浅く探索する手法のこと。元々コンピュータチェスで採用されていた手法だが、将棋は選択肢が多く機能しないと考えられていたため、それまで狭く深く読む選択探索が採用されていた。全幅探索は、選択探索が捨てていた有効な指し手に光を当てた。
技術的改良
Bonanzaの登場以降、様々な技術が開発され飛躍的に棋力(強さ)が向上した。
KPPT
玉(K)と他2駒(PとP)の3駒関係に手番(T)を加えた評価関数のこと。他にも王と玉と他1駒と手番のKKPTや、駒の効き(E)を加えたKPE等がある。
次元下げ
3駒関係を盤面の相対位置で考え評価関数に反映させる手法のこと。それまで3駒関係は絶対位置で考えていたため、プロの棋譜に現れにくい局面(入玉等)を苦手としていた。次元下げにより学習に利用できる局面が増加し、弱点の克服と棋力向上につながった。
枝刈り
特定の局面を探索対象から外し、効率を上げる手法のこと。たとえばミニマックス法は、探索中の情報から論理的に最大や最小をとらないと分かる局面も探索する。この無駄な探索を省く手法をαβ法という。他にも様々な枝刈り方法がある。
自己対局
コンピュータが自身のみでする対局のこと。プロの棋譜のみでは教師データが少ないため、自己対局を繰り返し増やした。このように、独力のみで学習する行為を強化学習という。
雑巾絞り
浅く探索した時の評価値を、深く探索した時の評価値に近づけるように評価関数を調整する手法のこと。発展形として勝敗結果を調整に取り入れる手法もある。強化学習の一種。
floodgate
2008年インターネット上に開設されたコンピュータ将棋の対局場のこと。対局の棋譜が入手でき教師データに利用できる。
プロとの対局
2013年、コンピュータとプロ棋士による団体戦、第2回将棋電王戦が開催されプロ棋士が初めて敗北した。2017年、名人佐藤天彦が2連敗したのを最後にコンピュータとの対局は行われていない。
その後の研究
2017年、アメリカの企業Googleがディープラーニングを行うプログラムAlphaZeroを開発し、3日間の学習で将棋ソフトトップのelmoに勝ち越したと発表した。2018年、日本でもディープラーニング評価関数(NNUE)が開発され効果を発揮している。
.jpg)
0 件のコメント:
コメントを投稿