はさみ五目並べプレイプログラムの開発
野田 統治郎† 苫米地 宣裕† 八戸工業大学大学院電気電子専攻† １．はじめに 思考ゲームをプレイするプログラムの研究は、人 工知能研究上の多くの課題を含んでおり、近年、情 報科学の重要な一分野として認められるようになっ た[1]-[3]。 本稿では、五目並べ[4]に相手の石を取ることがで きるというルールを加えた思考ゲーム(以下、はさみ 五目並べと呼ぶ)を提案し、本ゲームをプレイするプ ログラムを開発する。 本ゲームは、石を取り上げるというルールによっ て、通常の連珠よりも複雑であり、探索空間の極め て広いゲームとなっている。 ２．はさみ五目並べのルール 本研究で検討するはさみ五目並べは、五目並べゲ ームに、相手の石を取ることができるルールを付加 したものである。 付加したルールは次の通り。 [ルール１] 相手の二連を自分の石で挟み込んだ場 合、間の石を取ることができる。 [ルール２] 取った相手の石を自分の取石としてカ ウントする。 [ルール３] 取石が 10 個となった場合にも勝ちとす る。 [ルール４] 禁じ手(連珠における、先手 3-3、4-4 な ど)は無しとする。 ３．最善手探索 最善手探索は、深さ優先αβ枝刈り法を用いて行 う。以下、着手候補リストアップ方法、はさみ五目 並べの評価方法、思考アルゴリズムを述べる。 3.1 着手候補リストアップ方法 はさみ五目並べは、相手の石を取り除くというル ールを持っていることで、通常の五目並べより探索 空間が広くなっている。そこで、探索時間を短縮す るため、すでに着手してある石の近傍（8 近傍、ま たは、24 近傍）を着手候補とすることにした。 3.2 局面評価方法 本ゲームは、探索空間が悉皆探索を行うには広す ぎるので、一定の深さまでを探索した後に局面評価 を行い、最善手を決定する。 評価値を次のように定めた。 [評価１] 端に相手の石が置かれていない自分の四 連がある。20 点とする。 [評価２] 端に相手の石が置かれていない自分の三 連がある。6 点とする。 [評価３] 端に相手の石が置かれていない自分の二 連がある。2 点とする。 [評価４] 相手の石を取っている場合に点数をつけ る。2 個のとき 1 点、4 個のとき 3 点、6 個のとき6 点、8 個のとき 20 点とする。ま た、相手の取石の数はマイナスの評価値を つける。 以上の[評価１]から[評価４]の評価値を合計したも のを局面の評価とする。 3.3 思考アルゴリズム 前項で述べた知識、評価方法を基に思考アルゴリ ズムを作成した。本研究では、深さ優先探索方法を 用いて最善手を求めている。 思考アルゴリズムを以下に示す。 [手順１] 自分の必勝手を探索し、該当箇所があると き、着手する。 該当するならば[手順９]に移動する。 [手順２] 着手可能な場所(8 近傍)をリストアップす る。 [手順３] 着手候補から１つを選び、仮に着手をする。 [手順４] 差し手を戻し、深さを増やして[手順２]に 移動する。 [手順５] 先手番のとき、局面評価が最大の着手を最 善手とし、後手番のときは最低値の着手を 最善手として登録しておく。 [手順６] 未探索の探索候補があれば[手順４]へ戻り、 そうでない場合は[手順７]に移動する。 [手順７] 設定した深さまで先読みを行い、評価方法 に基づいて評価値を計算する。 [手順８] 最善手候補の石を着手する。 [手順９] 自分の五連、もしくは取石が 10 個かを判Development of the Program Playing Hasami-Gomoku. †Tojiro Noda and Nobuhiro Tomabechi, Electricity and Electronics Course, Graduate School of Engineering, Hachinohe Institute of Technology
2-1
2B-1
定し、該当するならばゲームを終了する。 [手順 10] 盤に着手する場所がなければ取り石の数 で勝敗を判定し、ゲームを終了する。 [手順 11] ゲームが終了していない場合は[手順１] に戻る。 ４．追い手探索 最善手探索とは別に、4 追い手のみを探索する。 これにより、追い手を見つけた場合に高速に処理す ることができる。同じ深さで、追い手、その阻止手 を仮に着手し、追い手が成功か失敗かを調べていく 探索方法をとっている。 追い手の手順は以下のようになる。 [手順１] 追い手候補がある場合、[手順２]へ移動す る。追い手候補がない場合、[手順７]へ移 動する。 [手順２] 追い手を仮に着手し、[手順３]へ移動する。 [手順３] 追い手の阻止候補がある場合、[手順 4]へ 移動する。阻止候補がない場合、[手順６] へ移動する。 [手順４] 阻止手を仮に着手し、[手順５]へ移動する。 [手順５] 次の深さへ進め、[手順１]へ移動する。 [手順６] 追い手の成功とし、結果を返す。 [手順７] 追い手の失敗とし、結果を返す。 ５．作成・実行結果 プログラムはC 言語を使用し作成した。ゲーム画 面は図2 に示すようにコマンドプロンプト画面で実 行している。プログラムを作成した結果、平均探索 時間は表１のようになった。 図2．実行画面 表１．平均探索時間(秒) 時間＼深さ 4 5 6 8 近傍 0.24 2.5 14 24 近傍 2.7 49 ストレスなくゲームをプレイすることを考慮し、 プログラムでは深さ6 先読みと 8 近傍を着手候補リ ストアップすることにしている。深さ7 とすると一 手の思考時間は10 分以上となっていく。 プログラムを実行した結果、全ての深さで先手が 勝利を収めた。また、評価値を変え実行した場合、 勝敗が逆転する結果が現われた。 8 近傍と 24 近傍の対決をさせた場合、深さ 5 先読 みまででは、24 近傍が先手後手に関わらず勝利する という結果が出た。 ６． 考察 実行結果から、はさみ五目並べは先手有利である ゲームと考えられる。しかし、評価値を変えること で勝敗が変わることから、現状では先手・後手どち らが有利であるか判断できない。今後、より正確な 評価値を探していく必要があると考えられる。 8 近傍と 24 近傍の対決結果については、8 近傍よ りも 24 近傍が強いという結果が出ているが、コン ピュータ対戦の棋譜を見ると、24 近傍の着手は遠回 りした解が多い。評価値の設定が 24 近傍にとって 適当でないのではないかと考えられる。 ７．まとめ 本研究では、はさみ五目並べプレイプログラムの 開発を行い、8 近傍リストアップ、深さ 6 先読みを するプログラムが完成した。 最善手探索については、石を盤面から取り除くこ とができるゲームであるため、探索空間が膨大にな っている。そのため、ストレスなくゲームをプレイ するためには深さ6 先読みが限界となっている。本 研究ではαβ探索法を用いて探索時間短縮を行って いるが、より深く先読みができるよう探索時間を短 縮していくことを検討している。 また、ゲームの性質を解明し、正確な評価値をゲ ームに組み込んでいく必要がある。 参考文献 [1] 松原 仁、竹内 郁雄、ゲームプログラミング、共立出版 1998-8 [2] 苫米地 宣裕、 立体４目並べの数理 、八戸工業大学情報シ ステム工学研究所紀要、Vol.11，pp1-4 ,1999-3. [3] 飯田 弘之、松原 仁、 ゲーム情報学の動向 、情報処理、 Vol.44,No.9,pp.895-899,2003-9. [4] 西村敏雄、 連珠必勝法：二手で勝つ 、熊本日日新聞情報文 化センター 2000-3．
