Tic Tac Toe bằng thuật toán Minimax

[minhquang251 (Quang Trương)]

Xin chào các bạn. Hiện tại mình đang làm một con AI chơi Tic Tac Toe bằng thuật Minimax. Tuy nhiên mình gặp một số vấn đề nên mình đưa lên diễn đàn nhờ giải đáp. Trước hết, đây là code của mình:

import copy
player = "O"
ai = "X"

board = [[""for i in range(5)]for i in range(5)] #Create board
for i in range(1,4):
    board[i][0]=i
    board[0][i]=i
board[0][0]="0"
board[4][0]='x'
board[0][4]='y'

def player(board): #Player Function
    q = 1
    while(q>0):
         choice = int(input("(1) Enter in xy: "))
         i = choice%10
         j = int(choice/10)
         if board[j][i] != "":
             print("Wrong input")
             continue
         else:
              board[j][i] = "X"
              q = q-1
def decision(board, choice): #Convert int to choice on board
    i = choice % 10
    j = int(choice / 10)
    board[j][i] = "O"
    return

def erase_board(list): #Board erasing function, which needed when recursion
    for i in range(1,4):
        for j in range(1,4):
            list[j][i]=""
def copy_board(board): #Copy board to do on the dupboard only
    return copy.deepcopy(board)
def spec_print(list): #print the grid
    for i in range(5):
        for j in range(5):
            if j==4:
                print(list[j][i])
                break
            else:
                print(list[j][i],end="\t")

def win(board, player):
    for j in range(1,4): #Check horizontal
        i=1
        if board[j][i]==board[j][i+1] and board[j][i]==board[j][i+2] and board[j][i] == player:
            return True
    for i in range(1,4): #Check vertical
        j=1
        if board[j][i]==board[j+1][i] and board[j][i]==board[j+2][i] and board[j][i] == player:
            return True
    if board[1][1] == board[2][2] and board[3][3] == board[2][2] and board[2][2] == player: # Check diagonal
        return True
    elif board[3][1]==board[2][2] and board[2][2]==board[1][3] and board[2][2]!=player: # Check diagonal
        return True
    else:
        return False

def score(board):
    if win(board, player):
        return -10
    elif win(board, ai):
        return 10
    else:
        return 0
def gameover(board):
    if win(board, player) == True or win(board, ai)== True:
        return True
    elif all(i != "" for i in board):
        return True

def ai(board, dupboard):
    global point
    if gameover(dupboard) == True:
        point = score(dupboard)
        if point == 10:
            choice = int(str(j)+str(i)) # Move Data Format
            decision(board, choice)
            point = 0
            return
        else:
            erase_board(dupboard)
            dupboard = copy_board(board)
            return ai(board, dupboard)
    for i in range(1,4):
        for j in range(1,4):
            if dupboard[j][i]=="":
                dupboard[j][i]="O"
                for a in range(1,4): # simulate player
                    for b in range(1,4):
                        if dupboard[b][a]=="":
                            dupboard[b][a]="X"
                            return ai(board, dupboard)

#Start program
point = 0
for i in range(1,5):
    spec_print(board)
    player(board)
    spec_print(board)
    dupboard = copy_board(board)
    ai(board, dupboard)
    if win(board,player)==True:
        break
    elif win(board,ai)==True:
        print("You lose")
        break
spec_print(board)
player(board)
if win(board, player) == True:
    print("You win")
else:
    print("Tide")

Vấn đề của mình, theo mình nghĩ nằm ở đoạn code này:

def ai(board, dupboard):
    global point
    if gameover(dupboard) == True:
        point = score(dupboard)
        if point == 10:
            choice = int(str(j)+str(i)) # Move Data Format
            decision(board, choice)
            point = 0
            return
        else:
            erase_board(dupboard)
            dupboard = copy_board(board)
            return ai(board, dupboard)
    for i in range(1,4):
        for j in range(1,4):
            if dupboard[j][i]=="":
                dupboard[j][i]="O"
                for a in range(1,4): # simulate player
                    for b in range(1,4):
                        if dupboard[b][a]=="":
                            dupboard[b][a]="X"
                            return ai(board, dupboard)

Mục đích của mình chính là sao y cái board gốc để tiện thao tác trên dupboard. Chương trình sẽ chạy vòng lặp lần lượt, bao gồm người chơi (giả lập) và ai, cho đến khi tất cả 9 ô đều được điền. Thắng thì point sẽ được +10, thua thì -10. Sau đó chương trình sẽ nhớ bước dẫn tới +10, để điền vào board.

Tuy vậy, khi chạy chương trình, thì mình mắc lỗi Maximun recursion depth exceed. Và mình chợt nhận ra rằng biến choice phụ thuộc vào i j, mà i j lại thay đổi, nên mình không thể lưu bước đầu tiên để có thể điền vào board. Đồng thời, khi gameover, dupboard bị xóa rồi tiếp tục được copied bởi board và vô tình thực hiện lại vòng lặp cũ.

Đây là 2 vấn đề mình đang tìm cách giải phù hợp. Mong các bạn có thể giúp đỡ.