三目並べAIをAlphaBeta法で実装しています.
三目並べは以下のサイトを参考にしており,Minimax法で実装されていますが,それをAlphaBeta法に変更しました.
https://github.com/koki0702/tictactoe-ai-youtube
AlphaBeta法はMinimax法の上位互換であり,計算量を少なくしたアルゴリズムであることから,同じ手を打ってくることを期待しているのですが,結果が異なってしまっています.
どのサイトを見ても解決できず,お力をお借りしたいです.よろしくお願いします.
ソースコードを以下に示します.
mainプログラム
import Board as b
import NPC
import PLAYER
board = b.Board()
players = [NPC.AplhaBeta(0), PLAYER.HumanPlayer(1)]
# players = [NPC.MiniMax(0), PLAYER.HumanPlayer(1)]
player = 1 # 0 or 1
while True:
p = players[player]
p.play(board)
board.render()
if board.is_win(player):
break
elif board.is_end():
print("引き分け")
break
player = 1 if player == 0 else 0
Boardクラス
import copy
class Board:
def __init__(self) -> None:
self.state = [-1] * 9 #置かれている種類(O or X)
self.count = 0
def render(self):
MARKS = {0: 'X', 1: 'O'}
text = """
0|1|2
-----
3|4|5
-----
6|7|8
"""
for idx, x in enumerate(self.state):
if x is not -1:
text = text.replace(str(idx), MARKS[x]) # 4 -> X
print(text)
def put(self, player, idx):
if self.state[idx] != -1 or (not(0 <= idx <= 8)):
return False
self.state[idx] = player
self.count += 1
return True
def take(self, idx):
self.count -= 1
self.state[idx] = -1
def is_win(self, player):
s = self.state
if(
s[0] == s[1] == s[2] == player or
s[3] == s[4] == s[5] == player or
s[6] == s[7] == s[8] == player or
s[0] == s[3] == s[6] == player or
s[1] == s[4] == s[7] == player or
s[2] == s[5] == s[8] == player or
s[0] == s[4] == s[8] == player or
s[2] == s[4] == s[6] == player
):
return True
return False
def eva_value(self, player):
opp = 0 if player == 1 else 1
if self.is_win(player):
return 1
elif self.is_win(opp):
return -1
else:
return 0
def is_end(self):
if -1 in self.state:
return False
return True
def valid_puts(self):
puts = [] #置ける候補
for idx, player in enumerate(self.state):
if player == -1:
puts.append(idx)
return puts
def board_result(self, idx):
tmp = copy.deepcopy(self)
n_player = tmp.next_player()
tmp.put(n_player, idx)
return tmp
def next_player(self):
# 0...先行f, 1...後攻s
state = self.state
f = s = 0
if self.count == 0:
return 0
for p in state:
if p == 0:
f += 1
elif p == 1:
s += 1
if f == s:
return 0
elif f > s:
return 1
else:
return -1
NPCクラス #このプログラムにMiniMaxとAlphaBetaがあります
import random
import Board3x3 as bo
def main():
board = bo.Board()
cpu = AplhaBeta(0)
# score ,idx = alphabeta(board, cpu.player, cpu.depth, float('-inf'), float('inf'))
board.put(0,8)
board.put(1,4)
board.put(0,7)
board.put(1,6)
# score ,idx = alphabeta(board, cpu.player, cpu.depth, float('-inf'), float('inf'))
score ,idx = minimax(board, 0)
print(score, idx)
class RandomPlay:
def __init__(self , player):
self.player = player
def play(self, board):
idx = random.randint(0,15)
return board.put(self.player, idx), idx
def minimax(board, player):
maximize_player = 0
minimize_player = 1
if board.is_win(maximize_player):
return (1, None)
elif board.is_win(minimize_player):
return (-1, None)
elif board.is_end():
return (0, None)
opp = 1 if player == 0 else 0
if player == maximize_player:
max_score = float('-inf')
max_idx = None
for idx in board.valid_puts():
board.put(player, idx)
score, next_idx = minimax(board, opp)
if max_score < score:
max_score = score
max_idx = idx
board.take(idx)
return (max_score, max_idx)
else:
min_score = float('inf')
min_idx = None
for idx in board.valid_puts():
board.put(player, idx)
score, next_idx = minimax(board, opp)
if min_score > score:
min_score = score
min_idx = idx
board.take(idx)
return (min_score, min_idx)
def alphabeta(board, player, depth, alpha, beta):
# print("depth = ",depth)
maximize_player = 0
minimize_player = 1
# print(depth)
if board.is_win(maximize_player):
return (1, None)
elif board.is_win(minimize_player):
return (-1, None)
elif board.is_end() or depth == 0:
return (0, None)
opp = 1 if player == 0 else 0
if player == maximize_player:
for put in board.valid_puts():
score, next_idx = alphabeta(board.board_result(put), opp, depth-1, alpha, beta)
alpha = max(alpha, score)
if alpha >= beta:
break
next_idx = put
return alpha, next_idx
else:
for put in board.valid_puts():
score, next_idx = alphabeta(board.board_result(put), opp, depth-1, alpha, beta)
beta = min(beta, score)
if alpha <= beta:
break
next_idx = put
return beta, next_idx
class MiniMax:
def __init__(self, player):
self.player = player
def play(self, board):
score, idx = minimax(board, self.player, )
return board.put(self.player,idx), idx
class AplhaBeta:
def __init__(self , player):
self.player = player
self.depth = float('inf')
self.depth = 7
def play(self, board):
score ,idx = alphabeta(board, self.player, self.depth, float('-inf'), float('inf'))
# idx = alphabeta(board, self.player, self.depth, -500, 500)
return board.put(self.player, idx), idx
if __name__ == "__main__":
main()
PLAYERクラス
class Player:
def __init__(self, player):
self.player = player
def play(self, board, idx):
return board.put(self.player, idx)
class HumanPlayer:
def __init__(self, player):
self.player = player
def play(self, board):
while True:
print('0~8の数字を入力してください:', end="")
idx = input()
try:
idx = int(idx)
success = board.put(self.player, idx)
if success:
break
else:
print("適切な数字を入力してください")
except ValueError:
pass