こんにちは。ヒトツメです。
またもかなり間が空いてしまいましたが、オセロのCPUを作っていこうと思います。
前回は、ミニマックス法まで実装できたので、枝刈りをしてアルファベータ法を実装したいと思います。
どういう場合に枝刈りするか
前回までの考え方の整理として、どのような場合に枝刈りをするのかという話から入りたいと思いますが、そもそも、前回実装したミニマックス法では、3手先の局面をすべからくすべて探索していました。
これにより、双方が最善手を選んだ場合における、自分の石が最も多くなる場合を探索することに成功しました。
この図で行くと、オレンジの8個の局面をすべて探索したということです。
しかしながら、オレンジの左から3つ目が4点になっている時点で、青の左から2つ目は4点以上が確定します。この時点で、オレンジの4つ目は点数計算をしなくてよくなります。
このように不要な部分を枝刈りしていくのが、アルファベータ法です。
実装してみる
そこで実際に実装してみるわけですが、再帰関数を使う部分など、大枠はミニマックス法と全く変わりません。
違うのは、点数の更新をするタイミングで、今まで出ている点数との比較が発生するという部分だけです。
def minimax(self, game, stone, zero_count):
if numpy.count_nonzero(game == 0.0) == 0 or numpy.count_nonzero(game == 0.0) <= zero_count - 3:
stone = -1 * stone
return numpy.count_nonzero(game == self.CPU_stone)
else:
best_score = (-float('inf'))
act = placableAct(game, stone)
for action in act:
[row, clm] = action
copy_game = game.copy()
nextgame(copy_game, row, clm, stone)
stone = -1 * stone
score = -1 * self.minimax(copy_game, stone, zero_count)
stone = -1 * stone
if score > best_score:
best_score = score
return best_score
def alphabeta(self, game, stone, zero_count, alpha, beta):
if numpy.count_nonzero(game == 0.0) == 0 or numpy.count_nonzero(game == 0.0) <= zero_count - 3:
stone = -1 * stone
return numpy.count_nonzero(game == self.CPU_stone)
else:
act = placableAct(game, stone)
for action in act:
[row, clm] = action
copy_game = game.copy()
nextgame(copy_game, row, clm, stone)
stone = -1 * stone
score = -1 * self.alphabeta(copy_game, stone, zero_count, -beta, -alpha)
stone = -1 * stone
if score > alpha:
alpha = score
if alpha >= beta:
return alpha
return alpha並べて書くとこの通りで、ほとんど違いはありません。
違うのは、アルファベータ法では、アルファとベータを引数にとり、すでに出ている点数と比較しながら、スコアを更新している点です。
「if score > alpha:」とすることで、今まで出てきた点数よりも自分の手が高くなる場合にのみ更新を行い、「if alpha >= beta:」とすることで、これ以上点数が高得点になることが期待できなくなったタイミングで、スコアの返却を行っています。
再帰呼び出しの際にalphaとbetaを入れ替えることで、先手と後手を入れ替えています。
アクションの部分でも、ミニマックス法と異なるところはほとんどなく、次のような記載になります（ミニマックス法との比較のため、ミニマックス法での手の選択の部分をコメントアウトしています）。
#score = self.minimax(self.copygame, self.stone, zero_count)
score = self.alphabeta(self.copygame, self.stone, zero_count, -float('inf'), float('inf'))実行してみると、きちんと動くことが確認できます。
さいごに
一応、オセロのCPUづくりは今回で完了となります。
これをさらに改良していくとなると、3手先を読んだ状態での状態評価を行わなければならず、機械学習が必要になるため、その基礎部分がない状態で作っていくと、説明が非常に煩雑になる可能性が高いためです。
掻い摘んで仕組みだけ説明しておくと、3手先の自分の石の数ではなく、3手先の状態での「勝ちやすさ」を評価基準とし、その「勝ちやすさ」の評価を、機械学習で行うということです。
Pythonは機械学習に向いた言語だといわれていますが、ほかにもできることはたくさんありますし、開発環境などを考えると、ほかにもいろいろと着手するべきことがあるということです。
もちろん、オセロをPythonで作った以上、機械学習の実装はやりたいので、いつかその過程も乗せれればと思います。
コメント