「Tohske」アピール文書 　　　　　　　　　　　　　　　　　　　　　　　　　東北大学　大学院情報科学研究科 　　　　　　　　　　　　　　　　　　　　　　　草野　一彦、須藤　郁弥、本田　耕一 　コンピュータ将棋プログラム「Tohske」について解説する。 １．定跡 　プロおよびアマチュア強豪の棋譜から、その局面で手番を持っている側が２勝以上して いる約７万局面を抽出し、定跡としている。探索を開始する前に局面が定跡に含まれてい るかどうかを調べ、含まれている場合には手番を持っている側の勝ち数が多い手を優先し、 ランダムに定跡中の手を返す。 ２．探索 　一般的なアルファベータ探索と静止探索を元に、以下の枝刈りや探索の延長を行ってい る。 　・局面表により同一局面の探索を省略 　・次の手法で指し手の並び替え 　　　・反復深化による浅い探索での最善手 　　　・キラー手 　　　・Static Exchange Evaluation 　・Null Move枝刈り 　・王手時に探索を１手延長 　・Scout法 ３．評価関数 　現在、ボナンザメソッドを用いて以下の評価項目を学習中である。 　・駒の価値 　・持駒の価値 　・駒の位置にたいする価値 　・２駒の相対位置にたいする価値 ４．ぼっち合議 　現在、「合議アルゴリズム」[1]を元にした「ぼっち合議」を「Tohske」に組み込み中で ある。「ぼっち合議」のアルゴリズムについて解説する。 　「合議アルゴリズム」は塙と伊藤によって提唱された、疎結合なシステム上での思考ゲ ームの並列探索を目的としたアルゴリズムである[2]。複数のプログラムを同時に動かして 多数決を取り全体の指し手とするという簡潔な手法である。合議アルゴリズムを本将棋に 適用した「文殊」は、個々のプログラムとして評価関数に乱数を加えたBonanzaを用い、プ ログラムあたりのマシンスペックはBonanzaに大きく劣る（より性能の低いマシンで１台あ たり２つのプログラムを動かしている）ものの、選手権ではBonanzaより上位に入賞した。 　本アルゴリズムの主要なアイデアは、合議アルゴリズムを密結合なシステムに適用する ことである。具体的にはミニマックス探索で用いている評価値をベクトルとして、i番目の 要素にi番目のプログラムの評価値に対応する値を格納する。ミニマックス探索の擬似コー ドを以下に示す。 vect Minmax( STATE *s, int depth ) { // 末端 if ( depth >= s->maxdepth || s->board.IsFinished() ) { // 静止探索 int v = Quiescence( s, depth ); vect r; for ( int i=0; iboard.GetHash() ); return r; } // 子局面を探索 vect value = vect(-INF); MOVE move[ CBoard::MAXMOVE ]; int movenum = s->board.GenerateMove( move ); for ( int m=0; mboard.Move( move[m] ); vect v = -Minmax( s, depth+1 ); s->board.Undo( move[m] ); // 更新 for ( int i=0; i value[i] ) { value[i] = v[i]; if ( depth == 0 ) s->bestmove[i] = move[m]; } } return value; } 　BNは仮想的なプログラムの台数、vectは要素数BNのベクトル、NormalRand(i,h)は整数i とハッシュ値hを元に正規乱数を生成する関数である。一般的なミニマックス探索との違い は静止探索の評価値に異なる乱数を加えてベクトルとしていることと、評価値の更新をベ クトルの要素ごとに行っていることのみである。プログラムの実行時間の大半が静止探索 や手の生成であることから、この探索は合議アルゴリズムと同様の結果を、仮想的なプロ グラムの台数によらず、ほぼ一定の時間で得ることができる。 　本アルゴリズムはアルファベータ探索にたいしても適用することが可能である。 vect Minmax( STATE *s, int depth, vect alpha, vect beta ) { // 末端 if ( depth >= s->maxdepth || s->board.IsFinished() ) { // 静止探索 int v = Quiescence( s, depth, alpha.min(), beta.max() ); vect r; for ( int i=0; iboard.GetHash() ); return r; } // 子局面を探索 vect value = alpha; MOVE move[ CBoard::MAXMOVE ]; int movenum = s->board.GenerateMove( move ); for ( int m=0; mboard.Move( move[m] ); vect v = -Minmax( s, depth+1, -beta, -alpha ); s->board.Undo( move[m] ); // 更新 for ( int i=0; i value[i] ) { value[i] = v[i]; if ( depth == 0 ) s->bestmove[i] = move[m]; if ( value >= beta ) break; } } return value; } 　ここで、value >= betaは全ての要素でvalue[i] >= beta[i]が成り立つとき真となるよ う定義している。 　ベクトルの全ての要素についてアルファベータ探索の枝刈りの条件を満たした場合に枝 刈りを行っているため仮想的な思考プログラムの個数を増やすと思考時間が長くなるが、 仮想プログラムの台数を８台とした場合でもおおよそ１台の場合の２倍程度に収まってい る。乱数の分散などのパラメタを適切に設定することができれば本アルゴリズムは充分実 用になるものと考えている。 ―――――――― [1] 合議システムと文殊, http://homepage1.nifty.com/ta_ito/ito-lab/gougi/gougi.html [2] 塙雅織、伊藤毅志：思考アルゴリズムにおける最適合議システム、第３回エンターテ 　　イメントと認知科学シンポジウム予稿集より(2009.3).