こんにちは。ヒトツメです。
前回は、オセロのCPUを作る第一歩として、いままで作ってきたgameUIクラスにCPUの手番を組み込み、CPUがランダムに手を指すというのを作ってきました。
今回は少し話を進めて、CPUが少し頭を使って次の手を考えるようにしていきたいと思います。
CPU vs. CPU
ただ、その前に、まずCPUとCPUが戦えるようにする必要があります。
というのも、今回作ろうとしている新しいCPUが、ランダムなCPUより強いことを証明する必要があるためです。そのために、新しくplayoutというクラスを作り、CPU同士で戦わせることが出来るようにします。
class playout():
def __init__(self, game):
self.game = game
self.player = 1
def play(self):
while numpy.sum(placable(self.game, 1)) > 0 or numpy.sum(placable(self.game, -1)) > 0:
self.CPU_player = CPU(self.game, self.player)
row, clm = self.CPU_player.Action()
nextgame(self.game, row, clm, self.player)
self.player = -1 * self.player
able = placable(self.game, self.player)
if numpy.sum(able) == 0.0: #どこにも置けない場合、手番を変更
self.player = -1 * self.player
buf = ''
buf = buf + '白：'+str(numpy.count_nonzero(self.game == 1.0)) + '個'
buf = buf + ' / 黒：'+str(numpy.count_nonzero(self.game == -1.0)) + '個'
if numpy.count_nonzero(self.game == 1.0) > numpy.count_nonzero(self.game == -1.0):
return buf + ' / 白の勝ち'
elif numpy.count_nonzero(self.game == 1.0) < numpy.count_nonzero(self.game == -1.0):
return buf + ' / 黒の勝ち'
else:
return buf + ' / 引き分け'考え方は非常にシンプルで、今までの考え方とほぼ同じです。手詰まりの時に相手に手番を渡すロジックを入れながら、とにかく両方が手詰まりになるまで、CPUクラスに石を置く場所がどこかを考えさせながら、石を設置していくだけです。
この時、CPU側は置ける位置にしか石を置かないので、置けない場所に置いているかどうかの判定などは不要です。あくまでどんどんCPU側に石を置かせます。
iter = 0
result = []
while iter < 500:
game = numpy.zeros((8, 8))
game[3][3] = 1
game[4][4] = 1
game[3][4] = -1
game[4][3] = -1
p = playout(game)
result.append(p.play())
iter += 1
print(result)試しに500回ほどplayoutを行い、その結果をresultというリストに格納すると、次のような結果になりました。
500回くらいだと、大数の法則はそこまで強く働かず、ちょっと偏りが出てしまうようです。
もしくは、完全ランダムだと、先手番の方が有利なのかもしれません。
3手先の石の数を数える
CPU同士を戦わせる準備ができたので、少しCPU側が頭を使って次の手を考えるようにしていきたいと思います。
そこで、一番わかりやすい戦略として、3手先の石の数を数えて、それが最大になるような手を指すようにしていきます。例えばそれぞれ石を置くことが出来る場所が平均4つあったとします。この時、単純に計算すれば、64（＝4の3乗）通りの状態を考えれば、何が最善手かが分かりそうです。
ただ、3手以上先を考えるようになってくると、全部計算するのは面倒ですし、単純に比較するだけだと、相手が最弱の手を指すことによって得られる結果を選択してしまうことになり、最善手を指すことが出来るとは限りません。
そこで、次の二つの考え方を採用します。
相手は必ず最善手を指すと考えて手を評価する
例えば、お互い2通りしか手が存在しないと簡略化して考えたとき、3手先の局面の評価が、次の図のようになっていたとします。
この時、最終的に3手目を自分が指したときの最良の状態は、右端の8点の状態です。ただそれは、その一手前の局面で相手が右側の手を選んだ場合のみで、左側の手を選ぶと、良くても2点にしかなりません。
逆に、そもそもの手として、左側の手を選んでおけば、どう転んでも3点以上になります。
このように、単純に最終的な局面を評価するのではなく、最終的な局面とそれを導くための相手の手を考慮して、次の一定に対する評価を下していくこととします。
いらない部分は枝刈りする
また、全部を検索せず、ある程度の枝刈りをしていくことで、計算を簡略化していきます。
例えば、5点の部分は、そのすぐ左にある4点の局面の計算ができた時点で、計算不要です。というのも、最大化・最小化をしていく中で、緑の3点の手から続く青の5点の手は、4点以上が確定しており、且つ、青の3点が出た時点で、緑の3点は確定してしまうからです。
同じように、右側の青の2点が出た時点で、緑の2点は2点以上ではなくなります。したがって、青の8点から続く枝も、計算する必要がなくなります。
このような枝刈りの方法をアルファベータ法と呼びます。
さいごに
以上のように、一定の評価基準を設けて、探索をしながら次の一手を選ぶという手法は、将棋や囲碁のAIでも使われている手法です。
次回以降はこれらの手法を実際に実装した場合にどのような記述になるか、というところを解説していきたいと思います。
コメント