はじめに
今回は囲碁や将棋のように 2 人が交互に 1 手ずつ指していくゲームを取り上げます。コンピュータにゲームの相手をさせる場合、コンピュータの指し手を決定するためのプログラム、いわゆる「思考ルーチン」が必要になります。この思考ルーチンで使われる基本的なアルゴリズムが「ミニマックス法 (mini-max method)」と「アルファベータ法 (αβ method)」です。
難しそうな名前がついていますが、ミニマックス法の基本は深さ優先探索ですし、アルファベータ法はミニマックス法を効率化するための枝刈りにすぎません。拙作のページ 新・お気楽 Python プログラミング入門第 3 回 や 集合、グラフ、経路の探索 で説明した基本的な探索アルゴリズムを理解していれば、それほど難しい話ではないのです。
そうはいっても、実際のゲームで強い思考ルーチンを作成するのは簡単な話ではありません。チェスや将棋などに比べると、リバーシの思考ルーチンは簡単だといわれています。ところが、実際にプログラムしてみると、強い思考ルーチンを作るのは本当に難しい、というのが M.Hiroi の実感です。それでも、リバーシは終盤になると最後まで読み切ることができるので、初心者や初級者レベルよりも強いプログラムを作るのは比較的簡単なほうでしょう。
今回は「カラハ (kalah)」という簡単なゲームを題材に、ミニマックス法とアルファベータ法を説明します。まずは、思考ゲームの基本から説明しましょう。
●ゲームの木
二人で対戦するゲームの場合、ゲームの進行状況は盤面の状態で表すことができます。指し手が進むにつれて盤面の状態は変化し、最後にはゲームが終了します。このようなゲームでは、その状態の変化を木構造に対応させることができます。これを「ゲームの木 (game tree)」といいます。
たとえば、「エイト」というゲームを考えてみます。このゲームのルールは、2 人のプレーヤーが 1 から 3 までの数字を交互に選び、2 人が選んだ数の合計が 8 になったら勝ち、8 を越えたら負けになります。数字の選び方には条件があって、一番最初は好きな数字を選ぶことができますが、それ以降は前回相手が選んだ数を選ぶことはできません。
このゲームの木は、手作業でも簡単に作成することができます。下図にゲームの木の一部を示します。
先手は最初に 1 から 3 の中の好きな数字を選ぶことができます。この木は、最初に先手が 2 を選び、次に後手が 1 を選んだ状態のゲームの木を示しています。数字の合計が 8 以上になったらゲームは終了です。木の高さはたかだか 6 レベルしかないので、エイトはとても簡単なゲームであることがわかります。
エイトのように、ゲーム開始から終了までの「ゲームの木」を作成できれば完璧な指し手を実現できます。ところが一般のゲームでは、ある局面で可能な指し手は多数あるので、ゲームの木はとても大きくなります。このため、完全なゲームの木を作成することは不可能です。
そこで、不完全ですが数レベル分の木を作成します。つまり、数手先読みするわけです。先読みした局面の状態は、ほとんどが勝ちでも負けでもない曖昧なものです。ここで、その局面の状態を評価して、自分が有利であれば 50 点とか不利であれば -10 点という具合に、局面の状態を数値化します。この処理を行う関数を「評価関数」といいます。とりあえず勝ち負けはわかりませんが、この評価値が高くなるように、つまり自分が有利になるように指し手を進めていくわけです。
もしも、完璧な評価関数がわかれば、その局面の状態から最善手がわかることになり、わざわざ木を探索する必要はありません。ところが、一般のゲームは状況がとても複雑なので、局面を正確に評価することは至難の技です。計算した評価値はどうしても適当なものになってしまいます。そこで、これを補うために「ミニマックス法」という手法を使います。
ミニマックス法の考え方はそれほど難しいものではありません。自分にとって良い指し手は相手にとって都合が悪く、逆もまたそうであるという仮説に基づいたアルゴリズムです。ゲームの木を何層か探索して、その局面を評価することは同じですが、「相手は自分に取って最悪の指し手を選択する」と仮定するところが、このアルゴリズムのポイントです。つまり、自分の指し手では評価値が最大になるように選択し、相手の指し手では評価値が最小になるように選択するのです。これが「ミニマックス」という名前の由来です。
ひらたくいえば、相手の手を先読みして自分の手を決めるということです。たとえば将棋の場合でも、駒の動かし方がわかる程度の初心者では相手の手を読むことは難しいですが、慣れてくると 2 手 3 手程度の先読みはできるようになります。これがプロ棋士になると、十数手から二十手前後まで考えるというのですから驚きです。
ミニマックス法を使う場合でも、評価関数が適切なものであれば、ゲームの木を深く探索するほど正確な評価値を求めることができるようになります。ただし、木を深いレベルまで探索しようとすると、特に囲碁や将棋のような一つの局面で有効な指し手が多数あるゲームでは、木の枝が多数分岐するので、探索のために消費するメモリと時間が膨大なものになってしまいます。
これを防ぐために、あとで説明する「アルファベータ法」という方法を用いたり、ほかにもさまざまな工夫を行うことで無駄な木の探索を極力省くようにします。それでもハードウェアの限界により、ある程度のレベルで探索を打ち切ることになります。また、持ち時間が設定されている場合は、それも考慮して探索レベルを決める必要があります。
●ミニマックス法
それでは、具体的にミニマックス法を説明しましょう。ここでは、簡単な仮想ゲームを考えてみます。このゲームは、先手後手とも指し手は常に 2 通りあって、そのうちの一つを選ぶことでゲームが進行します。
ミニマックス法を使う場合、局面の評価値が必要になります。評価関数は、先手が有利 (後手が不利) な局面ほど大きな値 (正の値)、逆に後手が有利 (先手が不利) なほど小さな値 (負の値)、互角の場合は 0 になるように作るのが一般的です。
探索のレベルは、先手－後手－先手の 3 手先まで読むことにします。先手の局面 R を探索すると、下図に示すゲームの木になりました。
評価値は最も深いレベル、この場合は 3 手指した後手の局面で計算します。3 レベルまで探索すると 8 通りの評価値が計算されますが、この評価値を使って、A と B のどちらの手を指すかミニマックス法で決定します。
R - A - C の局面に注目してください。この局面では、先手は 2 通りの指し手があり、それぞれ G と H という局面になります。この局面の評価値を計算すると、それぞれ 1 と 3 になります。ここでは先手の手番ですから、評価値が最大になるような指し手を選択します。したがって、局面 C の評価値は 3 に定まります。
同様に R - A - D の局面を計算すると、局面 D の評価値は 4 になります。局面 C と D の評価値が決まったので、局面 A の評価値を決めることができます。局面 A は後手の手番ですから、今度は評価値が最小になるような指し手を選びます。局面 C と D の小さい方を選ぶので、局面 A の評価値は 3 になります。
同様に局面 B の評価値を求めると 2 になります。局面 R は先手の手番なので、評価値の大きい指し手を選びます。この場合は、A が有利であることがわかります。このように、先手番では評価値が最大値となる指し手を選び、後手番では評価値が最小値となる指し手を選ぶことで、指し手を決定する方法がミニマックス法なのです。
ただし、ミニマックス法で選んだ指し手が最善手である保証はありません。この例では、ゲームの木を 3 レベル探索して A を選びましたが、もう一段深く探索してみると B の方が有利だった、ということもありえます。ようするに、3 手先までは読んでいたが、その先の手は読んでいなかった、ということです。これは私達がゲームをプレイする場合でもあることですね。
もしも、ゲームの木を最後まで探索できれば、最善手を指すことができます。たとえば、リバーシは終盤になると最後まで読み切ることが可能なゲームです。この状態になるとコンピュータは最善手を指してきます。コンピュータリバーシの得意技「終盤の大逆転」は、ゲームの木を最後まで読み切るからこそできることなのです。
●ゲーム「カラハ (Kalah)」の説明
それでは、例題として取り上げるゲーム「カラハ (Kalah)」を説明します。このゲームはルールこそ単純ですが、展開がスリリングで面白いゲームです。
上図に示すように、カラハの盤面は 6 個の穴が向かい合って並んでいます。左右にはカラハ (kalah) と呼ばれる穴があり、右隣が自分のカラハです。初期状態では、各穴に 6 個ずつ石が入っていて 2 つのカラハは空の状態です。ゲームの目的は、自分のカラハに過半数以上の石を集めることです。
カラハは自分の穴の一つから石を全部取り出し、右隣の穴から反時計回りに石を一つずつ配っていくことで、ゲームを進めていきます。石を配るとき、自分のカラハには石を入れますが、相手のカラハには入れません。そして、最後の石が入る穴の位置によって、2 通りのスペシャルケースが発生します。
- 自分のカラハに入ったならば、続けて自分の石を配ることができる。
- 最後の石が自分の空の穴に入り、向かいの穴に相手の石がある場合は、両方の石を自分のカラハに入れることができる。
このあと、手番は相手に移る。
本ページでは 1 番目のケースを英大文字で KALAH、2 番目のケースを「両取り」と書くことにしましょう。これ以外の場合は、自分の番は終わり相手の番になります。それから、もう一つスペシャルケースがあり、自分の穴に石が無くなった場合は、相手の穴に残った石を全て相手のカラハに入れてゲームを終了します。
カラハは最大でも 6 通りの指し手しかないので、ゲームの木が簡単で扱いやすいこと、それから単純な評価関数でも探索レベルを増やすと相当に強くなること、などの理由からミニマックス法の枠組みによく当てはまります。例題にはちょうどよい思考ゲームなのです。
●プログラムの作成
それでは、プログラムを作りましょう。最初に、盤面を表すクラスを定義します。
リスト : 盤面の定義
# 定数
SIZE = 14 # 盤面の大きさ
FIRST_KALAH = 6 # 先手、先手のカラハの位置
SECOND_KALAH = 13 # 後手、後手のカラハの位置
STONE = 72 # 石の個数
EVEN = STONE // 2
NORMAL = 0 # 通常の穴に入った場合
KALAH = 1 # KALAH に入った場合
GAMEOVER = 2 # ゲーム終了
# 盤面
class Board:
def __init__(self, b):
self.board = b[:]
def __getitem__(self, x):
return self.board[x]
def copy(self):
return Board(self.board)
クラス名は Board としました。盤面の実体は配列 (Python のリスト) で、インスタンス変数 board に格納します。穴との対応はルールの説明でも示したように、先手側の穴は左側から 0 - 5 でカラハの位置は FIRST_KALAH (6) になります。後手側の穴は反時計回りに 7 - 12 で、カラハの位置は SECOND_KALAH (13) になります。このように定義すると、穴に石を配るときには添字をひとつずつ増やしていけばいいので処理が簡単になります。FIRST_KALAH と SECOND_KALAH は手番を表すのにも使います。
特殊メソッド __getitem__() は角カッコ [ ] で盤面の要素にアクセスするために定義します。メソッド copy() は Board のオブジェクトをコピーするために使用します。
●Board のメソッド
次は盤面を操作するメソッドを定義します。最初に、石を配るメソッド distribute() を作ります。
リスト : 石を配る (終了位置を返す)
def distribute(self, turn, pos):
num = self.board[pos]
self.board[pos] = 0
while num > 0:
pos += 1
if pos == SIZE: pos = 0
if (turn == FIRST_KALAH and pos == SECOND_KALAH) or \
(turn == SECOND_KALAH and pos == FIRST_KALAH): continue
self.board[pos] += 1
num -= 1
return pos
この処理は簡単です。引数 turn は手番を、pos は石を取り出す穴の位置を表します。まず、pos 番目の穴にある石の数を変数 num にセットし、その穴を 0 にクリアします。あとは while ループで石を一つずつ配っていきます。pos が盤面の範囲を越えたら 0 に戻します。このとき、pos が相手のカラハでないことを確かめて、穴にある石の数を一つ増やしていきます。最後に配り終わった位置 pos を返します。
次は両取りのチェックを行うメソッド check_capture() を作ります。
リスト : 両取りのチェック
def check_capture(self, turn, pos):
if (turn == FIRST_KALAH and 0 <= pos <= 5) or \
(turn == SECOND_KALAH and 7 <= pos <= 12):
if self.board[pos] == 1 and self.board[12 - pos] > 0:
# 両取りができる
num = self.board[12 - pos] + 1
self.board[turn] += num
self.board[pos] = 0
self.board[12 - pos] = 0
return True
return False
check_capture() は両取りの条件をそのままコーディングしただけです。引数 turn は手番を、pos はチェックする穴の位置を表します。まず pos の条件をチェックします。turn が FIRST_KALAH であれば pos は 0 - 5 の範囲で、SECOND_KALAH であれば 7 - 12 の範囲であることを確認します。次に、pos の穴に石が一つあり、向かいの穴に石があることを確認します。向かいの穴の位置は 12 - pos で計算できます。
条件を満たしているのであれば、両取りする石の数を num にセットしてカラハに追加します。pos と向かいの穴は 0 にクリアして True を返します。両取りできない場合は False を返します。
次は、終了をチェックするメソッド check_gameover() を作ります。
リスト : 終了チェック
# 穴にある石を数える
def count_stone(self, turn):
n = 0
for x in range(turn - 6, turn): n += self.board[x]
return n
# 石をカラハに入れる
def put_stone_into_kalah(self, turn):
n = 0
for x in range(turn - 6, turn):
n += self.board[x]
self.board[x] = 0
self.board[turn] += n
# 終了チェック
def check_gameover(self):
if self.count_stone(FIRST_KALAH) == 0:
self.put_stone_into_kalah(SECOND_KALAH)
return True
elif self.count_stone(SECOND_KALAH) == 0:
self.put_stone_into_kalah(FIRST_KALAH)
return True
elif self.board[FIRST_KALAH] > EVEN or \
self.board[SECOND_KALAH] > EVEN:
return True
return False
count_stone() は turn 側の穴の石を数えるメソッドです。先手側の穴に石がなければ後手側にある石を全てカラハに入れます。逆に、後手側の石が無くなれば、先手側の石を全てカラハに入れます。put_stone_into_kalah() は指定されたサイドの石を全てカラハに入れるメソッドです。それから、どちらかのカラハが過半数 EVEN (36)より多くの石が入っているならばゲーム終了です。ゲーム終了の場合は True を返し、そうでなければ False を返します。
これらのメソッドを使って、石を動かすメソッド move_stone() を作ります。
リスト : 石を動かす
def move_stone(self, turn, pos):
pos = self.distribute(turn, pos)
if pos == turn: return KALAH
self.check_capture(turn, pos)
return NORMAL
引数 turn は手番を、pos は石を動かす穴の位置を表します。最初に、distribute() で石を配る処理を行い、最後の石が入った穴の位置を pos にセットします。次に、最後の石がカラハに入ったかチェックします。turn はカラハの位置で表されているので、turn と pos が等しいのであれば、最後の石がカラハに入ったことがわかります。この場合は KALAH を返します。最後に、check_capture() を呼び出して両取りのチェックを行ってから return で NORMAL を返します。
●ゲーム木の探索
それでは、ゲームの中心となるゲーム木の探索処理を作りましょう。先手の指し手を選ぶ関数を move_first() とし、後手の指し手を選ぶ関数を move_second() とします。move_first() は次のようになります。
リスト : 思考ルーチン
# 定数
MAX_VALUE = 100 # 評価値の最大値
MIN_VALUE = -100 # 評価値の最小値
# 先手の指し手を選ぶ
def move_first(depth, board):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MIN_VALUE
move = []
for pos in range(0, 6):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(FIRST_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_first(depth, b)
else:
# 後手番
v, _ = move_second(depth - 1, b)
# ミニマックス法 : 先手は大きな値を選ぶ
if value < v:
value = v
move = [pos] + m
return value, move
引数 depth はゲーム木の探索レベルを表します。引数 board は現在の局面を表します。カラハのように、1 手指すたびに局面の大部分が変化するようなゲームでは、局面をコピーしてから石を動かして新しい局面を生成するといいでしょう。逆に、局面の一部分しか変化しないゲームでは、局面を直接書き換えて新しい局面を生成する方法が一般的です。 この場合、バックトラックするとき新しい局面から前の局面に戻す処理が必要になります。
ゲームが終了する、または depth が 0 になったとき、board の評価値を計算して返します。評価関数は先手番のカラハと後手番のカラハの差 (board[FIRST_KALAH] - board[SECOND_KALAH]) としました。もしも、勝負がついている場合は FIRST_WIN (99) または SECOND_WIN (-99) を返します。
とても単純な関数ですが、これでも十分に機能します。実際、探索レベルを上げると、M.Hiroi はほとんど勝てなくなります。評価値はメソッド value_func() で計算し、その結果と空の配列を return で返します。
次に、ミニマックス法で指し手を求めます。変数 value は評価値を格納し、評価値の最小値 MIN_VALUE (-100) で初期化します。先手は評価値の高い手を選択するので、最初に調べた手は必ず選択されることになります。あとは、評価値を比較して、高い手を選択すればいいわけです。変数 move は選択した指し手を格納します。
次の for ループで、実際に石を動かして探索を行います。最初に pos の位置に石があるかチェックします。次に、copy() で局面をコピーしてから move_stone() で石を動かし、その結果を result にセットします。
●KALAH の処理
result が KALAH の場合、最後の石がカラハに入りました。この処理は少々厄介です。指し手は 1 手とは限らず、複数になる場合もあるからです。この処理を繰り返しで実現しようとすると面倒なことになってしまいますが、再帰を使うとあっさりと実現できます。探索レベルと手番を変えずに、そのまま再帰するだけでいいのです。
その中で KALAH にならない指し手が選択されると、手番を変えて move_second() が呼び出されるので、ミニマックス法は正常に動作します。この処理は次のように書き換えても、同じ指し手が選択されます。
リスト : KALAH の処理
if result == KALAH:
# 手番は同じまま
_, m = move_first(depth, b)
for x in m:
b.move_stone(FIRST_KALAH, x)
# 後手番
v, _ = move_second(depth - 1, b)
KALAH で move_first() を呼び出したとき後手番の探索も行われるので、そのあとの move_second() で無駄な探索が行われることになりますが、選択される指し手は同じになります。
ゲームの木を作成する場合、交互に手番が移るときはゲームの木の高さと探索レベルは一致しますが、KALAH の処理が含まれるとゲームの木はいっきに高さを増すことになります。探索レベルが 2 の場合でも、お互いに最後の石がカラハに入る局面では、木の高さは 10 を越えることもあるでしょう。
ところで、KALAH の処理では相手のことを考えずに、自分の評価値を最大にする指し手を選ぶ方法もあります。
リスト : KALAH の処理 (簡易版)
if result == KALAH:
# 手番は同じままで 1 手だけ探索
_, m = move_first(1, b)
for x in m:
b.move_stone(FIRST_KALAH, x)
# 後手番
v, _ = move_second(depth - 1, b)
move_first() を呼び出すとき、depth を 1 に指定します。これで相手を考慮せずに自分の指し手を選ぶことができます。ゲームの木の高さは抑えられるので、実行速度は速くなるでしょうが、自分のことしか考えていないので思考ルーチンは弱くなると思います。これはあとで試してみましょう。
あとは、石をカラハに入れたときの指し手を集めておけばいいわけです。指し手は配列に格納して返すことにしましょう。一般に、ミニマックス法で必要なのは評価値だけで、指し手はなくても動作するのですが、今回は指し手も返すことにします。
●ミニマックス法のプログラム
次の処理がミニマックス法の心臓部です。先手は評価値の大きい方が有利なわけですから、いちばん大きな評価値 (マックス) の指し手を選びます。選んだ指し手は move に格納し、その評価値は value に格納しておきます。評価値 v が value よりも大きい値であれば、その指し手を選べばいいわけです。最後に return で value と move を返します。
次は後手の指し手を選ぶ関数 move_second() を作ります。
リスト : 後手の指し手
def move_second(depth, board):
if board.check_gameover() or depth == 0:
# 盤面の評価
return board.value_func(), []
#
value = MAX_VALUE
move = []
for pos in range(7, 13):
if board[pos] == 0: continue
b = board.copy()
# 石を動かす
result = b.move_stone(SECOND_KALAH, pos)
m = []
if result == KALAH:
# 手番は同じまま
v, m = move_second(depth, b)
else:
# 先手番
v, _ = move_first(depth - 1, b)
# ミニマックス法 : 後手は小さな値を選ぶ
if value > v:
value = v
move = [pos] + m
return value, move
後手番の場合、先手番とは逆にいちばん小さな評価値 (ミニマム) の指し手を選択することに注意してください。変数 value は評価値の最大値 MAX_VALUE に初期化します。石がカラハに入った場合は move_second() を再帰呼び出しして、カラハ以外の穴に入った場合は move_first() を再帰呼び出しします。そして、ミニマックス法では v が value よりも小さい場合に value と move の値を更新します。あとは、全ての指し手を調べるだけです。とても簡単ですね。
このほかに KALAH 簡易版を実装した関数 move_first1() と move_second1() を用意します。これは簡単なので説明は省略します。詳細は プログラムリスト１ をお読みください。
●ゲームの進行
最後に、ゲームを進める処理を作成します。探索レベルによって局面を評価する回数がどのくらい増えるのか確かめてみましょう。次のリストを見てください。
リスト : ゲームの実行
def play(first_depth, second_depth, think1 = move_first, think2 = move_second):
init_count()
board = Board([6,6,6,6,6,6,0,6,6,6,6,6,6,0]) # 初期状態
turn = FIRST_KALAH
while True:
if turn == FIRST_KALAH:
value, move = think1(first_depth, board)
else:
value, move = think2(second_depth, board)
# 表示
for x in move:
print('move', x)
board.move_stone(turn, x)
board.print_board()
print()
if board.check_gameover():
print('Game Over')
board.print_board()
print_count()
return
if turn == FIRST_KALAH:
turn = SECOND_KALAH
else:
turn = FIRST_KALAH
引数 first_depth は先手の探索レベル、second_depth は後手の探索レベルです。think1 は先手の思考ルーチン、think2 は後手の思考ルーチンです。最初に初期状態の盤面を生成して変数 board にセットします。変数 turn は手番を表します。あとは while ループの中で思考ルーチンを呼び出してゲームを進めます。
思考ルーチンの返り値を value, move で受け取ります。そして、move から指し手を一つずつ取り出して、メソッド move_stone() で石を動かします。盤面の表示はメソッド print_board() で行います。あとは play() を呼び出すだけです。
●実行結果
それでは実行結果を示します。
表 : 局面の評価回数 (ミニマックス法)
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 41, 31 : 43, 17 : 26, 37 : 39, 33
: 11775 : 90968 : 318340 : 1221294
3 : 39, 23 : 40, 32 : 53, 19 : 48, 24
後 : 4383 : 41159 : 654559 : 588627
手 4 : 36, 36 : 43, 29 : 34, 38 : 44, 28
: 160765 : 131496 : 510241 : 1734092
5 : 23, 49 : 26, 39 : 43, 29 : 35, 37
: 3648321 : 1580529 : 2488362 : 4806261
上段 : 先手の石数, 後手の石数
下段 : 局面の評価回数
先手 : move_first()
後手 : move_second()
勝敗 : 先手 10 勝, 後手 5 勝, 1 分
探索レベルを増やすと、局面を評価する回数は大幅に増加します。当然ですが、それだけ実行時間も長くなります。次に、KALAH 簡易版の結果を示します。
表 : 局面の評価回数 (ミニマックス法 KALAH 簡易版)
先手
: 2 : 3 : 4 : 5
-------+---------+---------+---------+---------
2 : 37, 23 : 37, 22 : 41, 31 : 39, 33
: 2625 : 9584 : 28001 : 134349
3 : 35, 37 : 49, 23 : 43, 21 : 37, 25
後 : 2681 : 19940 : 19330 : 177671
手 4 : 26, 46 : 35, 37 : 31, 41 : 49, 23
: 47871 : 58461 : 56932 : 144941
5 : 45, 27 : 37, 27 : 28, 44 : 24, 48
: 121195 : 75151 : 146399 : 437150
上段 : 先手の石数, 後手の石数
下段 : 局面の評価回数
先手 : move_first1()
後手 : move_second1()
勝敗 : 先手 10 勝, 後手 6 勝
通常版に比べて局面の評価回数が激減しています。それだけ KALAH の処理が重たいことがわかります。どちらの場合も先手が勝ち越しているので、カラハは先手が有利なゲームなのかもしれません。
最後に、通常版と KALAH 簡易版の対戦結果を示します。
表 : 通常版 vs 簡易版
先手
: 2 : 3 : 4 : 5
------+--------+--------+--------+--------
2 : 37, 30 : 43, 17 : 36, 36 : 37, 19
後 3 : 37, 28 : 38, 26 : 38, 14 : 37, 35
手 4 : 30, 42 : 32, 40 : 37, 17 : 37, 35
5 : 37, 25 : 19, 37 : 37, 35 : 39, 33
上段 : 先手の石数, 後手の石数
先手 : move_first()
後手 : move_second1()
勝敗 : 先手 11 勝, 後手 4 勝, 1 分
表 : 簡易版 vs 通常版
先手
: 2 : 3 : 4 : 5
------+--------+--------+--------+--------
2 : 30, 42 : 31, 41 : 34, 38 : 39, 33
後 3 : 36, 36 : 30, 42 : 31, 41 : 31, 41
手 4 : 15, 57 : 28, 44 : 49, 23 : 39, 33
5 : 20, 52 : 37, 22 : 36, 36 : 20, 40
上段 : 先手の石数, 後手の石数
先手 : move_first1()
後手 : move_second()
勝敗 : 先手 4 勝, 後手 10 勝, 2 分
先手後手ともに通常版のほうが勝ち越しました。予想通り KALAH の処理を簡略化すると思考ルーチンは弱くなるようです。興味のある方はいろいろ試してみてください。
●参考文献
- 松原仁・竹内郁雄 編著, 『bit別冊 ゲームプログラミング』, 共立出版, 1997
- 松原仁 編著, 『コンピュータ将棋の進歩』, 共立出版, 1996
- 松原仁, 『将棋とコンピュータ』, 共立出版, 1994
改訂 2022 年 11 月 26 日