【はじめてのPython】オセロのCPUを作る④

こんにちは。ヒトツメです。
またも少し間が空いてしまいましたが、今回は前回学んだ再帰関数を使って、前々回に取り上げたアルファベータ法を実装していきたいと思います。

【はじめてのPython】オセロのCPUを作る③

こんにちは。ヒトツメです。前回は、CPUを作る上での考え方の一つとして、アルファベータ法による探索について考えていきました。 今回は、前回の考え方をベースにして、実装をしていこうと思うのですが、そこで非常に重要な考え方である、再帰関数を使い...

hitotsu-eye.com

2022.07.31

考え方の整理とActionの修正

そこで、実際に再帰関数を用いて、3手先の局面の石の個数を数えて手の評価をしていきたいと思うわけですが、その下準備として、どのように再帰関数を用いるかということを整理して考える必要があります。
というのも、再帰関数を用いて3手先のすべての局面を洗い出し、もっとも理想的な局面がどのような状態かを検討したとしても、その局面に持っていくための手がどれなのか等、実際にアクションをするときの動きなどが定まっていないと、ただただ局面を洗い出しているにすぎないからです。

そこで、次のような考え方を用いて、実装をしていきたいと思います。

1. その局面におけるすべての手を洗い出す
2. その一つ一つの手を指した状態における「理想的な局面」を導く
3. 一つ一つの手に関して、「理想的な局面」における石の数で評価を行う
4. もっとも評価が高かった手を選択する

ちなみに、ここでいう「理想的な局面」とは、お互いに最善となる手を指していながら、自分にとって最も望ましい局面を言います。要は、相手が自分の都合の良いように動いているわけではなく、きちんと最善手（と思われる手）を指している状態を言います。

これを、CPUが黒の手番の時に関して実装すると、次のようになります。

    def Action(self):
        if self.CPU_stone == 1:
            actionArr = placable(self.game, self.CPU_stone).reshape(64) * numpy.random.rand(64) * self.CPU_stone
            action = actionArr.argmax()
            row = int(action / 8)
            clm = action % 8
            return row, clm
        elif self.CPU_stone == -1:
            act = placableAct(self.game, self.CPU_stone)
            actionList = []
            zero_count = numpy.count_nonzero(self.game == 0.0)
            for action in act:
                [row, clm] = action
                self.copygame = self.game.copy()
                nextgame(self.copygame, row, clm, self.CPU_stone)
                self.stone = -1 * self.CPU_stone
                score = self.minimax(self.copygame, self.stone, zero_count)
                actionList.append([score, action])
            actionList.sort(reverse=True)
            row, clm = actionList[0][1]
            return row, clm

CPU_stoneが「-1」、つまり黒の時に、全ての手を洗い出し、その一つ一つを実際に刺した局面を作り出します。また、その局面について、self.minimax()という関数でscoreを評価しています。それをactionListに入れていき、scoreが降順になるように並び替え、先頭の手を選択する、という感じです。

minimax関数を実装

このように準備ができたところで、minimax関数を実装していきます。
ちなみに、上のminimax関数では、zero_countという引数をとっています。これは、局面における「0」、つまり何も置かれていない場所の数を表します。これによって、今の局面が何手先の局面かを表しています。

    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

実装は意外とシンプルで、if文がTrueの場合の処理は、何も置けなくなるか3手先の局面に至った状態で、自分と同じ色の石の数を返却するというものです。Falseの場合、相手方の手番における次の手を一つ一つ洗い出し、再帰関数を用いて、if文がTrueになるまで何度も処理をしていきます。
ポイントの一つ目は、gameをcopyしていることです。これをしなければ、分岐を探索するときに、きちんと分岐前の局面に戻ることが出来ません。
また、ポイントの二つ目は、scoreを「-1」で掛けて、より大きい場合にscoreを更新している点です。このようにすることで、相手にとっても自分の石を多くしようと最善手を取り、自分にとってのみ都合の良い局面に陥ることを防いでいます。
ちなみに、float(‘inf’)は、無限を表しています。

以上の実装を実際に動かしてみると、次のように、きちんと作動することが確認できます。

さいごに

とはいえ、これだと前々回に整理した枝刈りは行われていません。したがって、これだとアルファベータ法ではなく、単なるミニマックス法になります。
次回以降で、枝刈りの方法を整理し、処理を軽くして、アルファベータ法を実装していきたいと思います。