計測自動制御学会東北支部 第 229 回研究集会(2006.6.9)
資料番号 229-10

はさみ五目並べプレイプログラムの設計
Design of the Program Playing Hasami-Gomoku○野田統治郎*, 苫米地 宣裕*○ Toujirou Noda*, Nobuhiro Tomabechi**八戸工業大学大学院電気電子工学専攻*Electricity and Electronics Course, Graduate School of Engineering, Hachinohe
Institute of Technology
キーワード： はさみ五目(Hasami-Gomoku), 五目並べ(line-5 tic-tac-toe) , 人工知能(artificialintelligence) , ゲーム (game), プログラム(program), 設計(design)

連絡先： 〒 031-8501 青森県八戸市妙字大開 88 番地 1 号 八戸工業大学 システム情報工学科 苫米地
研究室 苫米地宣裕, Tel.:0178-25-8051, E-Mail:tomabech@hi-tech.ac.jp１．

はじめによって、通常の連珠よりも複雑であり、探索空間の極めて広いゲームとなっている。

思考ゲームをプレイするプログラムの研究は、人工知能研究上の多くの課題を含んでおり、

２．

はさみ五目並べのルール

近年、情報科学の重要な一分野として認められるようになった[1]-[4]。

本研究で検討するはさみ五目並べは、五目並

本研究では、連珠、将棋，囲碁などの様々なべゲームに、相手の石を取ることができるルー思考ゲームをプレイできる思考ゲームプレイルを付加したものである。

ロボットの開発を目指している。
本稿では、五目並べ[5]に相手の石を取ることはさみ五目並べのルールを以下のように定ができるというルールを加えた思考ゲーム(以める。

下、はさみ五目並べと呼ぶ)を取り上げ、本ゲー[ルール１] 盤は、１３×１３の広さとする。

ムをプレイするプログラムを開発する。

[ルール２] 先手と後手は交互に着手をする。
[ルール３]

本ゲームは、石を取り上げるというルールに

1

先手と後手は、石の色によって識別する。先手は黒、後手は白とする。
[ルール４]

先手
後手

先手、第一着手は中心６×６の位置とする。

[ルール５]

相手の二連を自分の石ではさみこんだ場合、間の石を取ることができる。これを、図１に示す。

[ルール６]

取った相手の石を、自分の取石としてカウントする。

[ルール７]

図２．ゲームの木

縦、横、斜めのいずれかの一直線上に五連ができるか、もしくは、取石が 10 個となったら勝ちとする。

[ルール８]

3.1

はさみ五目並べは、相手の石を取り除くとい盤に着手場所がない場合、取石のうルールを持っていることで、探索空間が広く数で勝敗を決める。
[ルール９]

着手候補リストアップ方法

なっている。そのために、全探索では探索時間盤に着手場所がなく、また取石のが膨大になってしまう。そこで、すでに着手し数が同じ場合は引き分けとする。
[ルール 10] 禁じ手（連珠における、先手、３てある石の近傍（8 近傍、または、25 近傍）を-３、４-４などの禁止）は無しとす着手候補とすることにした。

る。
3.2

評価方法

本ゲームは、探索空間が悉皆探索を行うには広すぎるので、一定の深さまでを探索した後に局面評価を行い、最善手を決定する。局面評価とはある局面において点数をつけることで、プここに着手レイヤにとって有益な局面ほど大きな評価値をつけるように設計する。
評価対象と評価値を次のように定めた。

間の白石二

[評価１]

つが消える

端に相手の石が置かれていない自分の四連がある。20 点とする。

[評価２]

端に相手の石が置かれていない自分の三連がある。6 点とする。

図１．[ルール５][評価３]

端に相手の石が置かれていない自分の二連がある。2 点とする。

３．

[評価４] 自分の取石の数が増える。

最善手探索

取石の数と点数は以下の通りとする。
最善手探索は、思考ゲームにおいての中枢的・ 2 個のとき、1 点とする。

機能である。先読みをするためのゲームの木を・ 4 個のとき、3 点とする。

図２に示す。ゲームの木は、1 つの親ノードと・ 6 個のとき、6 点とする。

2 つ以上の子ノードを持ち、終端の部分には評・ 8 個のとき、20 点とする。
[評価５] 相手の取石の数が増える。

価値が与えられる。
以下、着手候補リストアップ方法、はさみ五取石の数と点数は以下の通りとする。

目並べの評価方法、思考アルゴリズムを述べる。
2・ 2 個のとき、−1 点とする。

・ 4 個のとき、−3 点とする。

４．

追い手探索

・ 6 個のとき、−6 点とする。
・ 8 個のとき、−20 点とする。

最善手探索とは別に、4 追い手のみを探索する。別にすることで追い手を見つけた場合に高以上の[評価１]から[評価４]の評価値を合計し速に処理することができる。追い手側、阻止すたものを局面の評価とする。

る側というように交互に最善手を仮想的に着手し探索していく。

3.3

思考アルゴリズム

追い手思考アルゴリズムは以下のようにな

前項で述べた知識、評価方法を基に思考アルる。

ゴリズムを作成した。本研究では、深さ優先探4.1

索方法を用いて最善手を求めている。

追い手をする側(手順１)

思考アルゴリズムを以下に示す。

自分の必勝手を探索し、該当箇所があるとき、着手する。該当するならば(手順１)

自分の必勝手を探索し、該当箇所が（手順４）に移動する。
(手順２)あるとき、着手する。
該当するならば（手順９）に移動する。

四連を作れる場所をリストアップする。

（手順２）着手可能な場所(8 近傍)をリストア四連を作れる場所がなかったら(手順ップする。

５)へ移動する。
(手順３) 仮に着手し、相手の番に変わる(次の（手順３）着手候補から１つを選び、仮に着手をする。

深さへ進む)。
(手順４)（手順４）差し手を戻し、深さを増やして（手順２）に移動する。

自分の五連、もしくは取石が 10個かを判定し、該当するならば最善手（手順 5）先手番のとき、局面評価が最大の着として登録して追い手探索を終了す

手を最善手とし、後手番のときは最低る。
(手順５) 追い手探索を終了する。

値の着手を最善手として登録しておく。

4.2（手順６）未探索の探索候補があれば（手順４）追い手を阻止する側(手順１)へ戻り、そうでない場合は（手順７）に移動する。

自分の必勝手を探索し、該当箇所があるとき、着手する。該当するならば(手順５)に移動する。

（手順７）設定した深さまで先読みを行い、評(手順２)

価方法に基づいて評価値を計算する。
（手順８）最善手候補の石を着手する。

相手の四連を阻止する場所をリストアップする。

（手順９）自分の五連、もしくは取石が 10(手順３)個かを判定し、該当するならばゲーム着手候補リストの中の一つを仮に着手する。

(手順４)を終了する。
（手順 10）盤に着手する場所がなければ取り阻止することができたら(手順６)へ移動する。阻止できない場合は(手順石の数で勝敗を判定し、ゲームを終了

３)へ戻る(手順５) 前の深さへ戻す(相手の番に変わる)。

する。
（手順 11）ゲームが終了していない場合は（手(手順６)

順１）に戻る。

次の深さへ進める(相手の番に変わる)。

3

５．

プログラム作成

5.1

プログラムの全体構成

はさみ五目並べプレイプログラムを、C 言語を用いて作成した。探索方法には、深さ優先探索法を採用した。
プログラムの全体構成は、図３に示す。

開始

追い手探索

追い手失敗

NO

YES
手番の交代

先読み探索

着手を進める

勝敗判定

NO

図４．プレイ画面

勝利している
YES
終了

図３．

5.2

プログラムの構成フローチャート

プログラム作成結果

プログラム作成をした結果、1339 ステップとなった。

図５．プレイ画面

現在、はさみ五目並べはコマンドプロンプト画面でプレイしている。プレイ実行画面を図４、8 近傍リストアップ、深さ４先読みとすると探索時間は平均 17 秒となった。これがストレ

図５に示す。

スなく待つことのできる限界と思われる。
１ゲームの平均探索時間は表１の通りであり、ゲームの着手数は平均 30 手ほどになる。

4深さ34

参考文献

5

[1]

時間
8 近傍

0.6

17257

25 近傍

3.555910800

表 1．

松原仁、竹内郁雄、

ゲームプログラミング、共立出版 1998-8[2] 苫米地 宣裕、

ゲーム終了時の平均探索時間(秒)“立体４目並べの数理”、
八戸工業大学情報システム工学研究所紀要、以上のことから、プログラムでは、深さ 4 先読

Vol.11，pp1-4 ,1999-3.

みと 8 近傍リストアップを採用することにした。

[3] 飯田 弘之、松原 仁、“ゲーム情報学の動向”
、

5.3

実行結果

情報処理、Vol.44,No.9,pp.895-899,2003-9.

① ゲームは先手がすべて勝利を収める結果となった。

[4]② 8 近傍、25 近傍を対決させた場合、深さ 4潔、天野真家、“知能ロボットの技術：人工知能からのアでは先手後手に関わらず 8 近傍が勝利するプローチ”という結果が出た。

情報処理、Vol.44,No.12,pp.1212-1213,2003-12.

[5]5.4 考察

西村敏雄、
連珠必勝法：二手で勝つ

結果①は、禁じ手なしのルールでは先手が有

熊本日日新聞情報文化センター

利であると考えられる。
結果②は、深さ４までの局面では、8 近傍よりも 25 近傍が高い評価値を与えられたが、ゲームがそれ以上の深さに進むにつれて有効でなくなったためと考えられる。

６．

小暮

まとめ

本研究では、はさみ五目並べプレイプログラ
ムの設計・制作を行った。
最善手探索については、石を盤面から取り除くことができるゲームであるため、探索空間が膨大になっている。そのため、ストレスなくゲームをプレイするためには深さ４先読みが限界となっている。今後、αβ探索法などを取り入れ探索時間短縮していくことを検討している。
リストアップ方法では 8 近傍が有効であると考えられた。そこで、より深く探索した場合にも同等に勝利するかを調べたいと考えている。
また、ゲームの数理を解明し、ゲームに組み込んでいく必要がある。
5

2000-3．