python - Python tic tac toe minmax 算法根本没有优化？

Question

在过去的几天里，我一直在研究这个井字游戏 min max 项目。现在程序正在运行，但计算机对手只是按数字顺序选择第一个可用空间，而不是实际优化。建议自己编译以更好地了解问题。如果有人知道我的脚本中的原因是什么，那将非常有帮助。

# MODULES
import pygame, sys
import numpy as np

# initializes pygame
pygame.init()

# ---------
# CONSTANTS
# ---------
WIDTH = 600
HEIGHT = 600
LINE_WIDTH = 15
WIN_LINE_WIDTH = 15
BOARD_ROWS = 3
BOARD_COLS = 3
SQUARE_SIZE = 200
CIRCLE_RADIUS = 60
CIRCLE_WIDTH = 15
CROSS_WIDTH = 25
SPACE = 55
# rgb: red green blue
RED = (255, 0, 0)
BG_COLOR = (28, 170, 156)
LINE_COLOR = (23, 145, 135)
CIRCLE_COLOR = (239, 231, 200)
CROSS_COLOR = (66, 66, 66)

# ------
# SCREEN
# ------
screen = pygame.display.set_mode( (WIDTH, HEIGHT) )
pygame.display.set_caption( 'TIC TAC TOE' )
screen.fill( BG_COLOR )

# -------------
# CONSOLE BOARD
# -------------
board = np.zeros( (BOARD_ROWS, BOARD_COLS) )

# ---------
# FUNCTIONS
# ---------
def draw_lines():
    # 1 horizontal
    pygame.draw.line( screen, LINE_COLOR, (0, SQUARE_SIZE), (WIDTH, SQUARE_SIZE), LINE_WIDTH )
    # 2 horizontal
    pygame.draw.line( screen, LINE_COLOR, (0, 2 * SQUARE_SIZE), (WIDTH, 2 * SQUARE_SIZE), LINE_WIDTH )

    # 1 vertical
    pygame.draw.line( screen, LINE_COLOR, (SQUARE_SIZE, 0), (SQUARE_SIZE, HEIGHT), LINE_WIDTH )
    # 2 vertical
    pygame.draw.line( screen, LINE_COLOR, (2 * SQUARE_SIZE, 0), (2 * SQUARE_SIZE, HEIGHT), LINE_WIDTH )

def draw_figures():
    for row in range(BOARD_ROWS):
        for col in range(BOARD_COLS):
            if board[row][col] == 1:
                pygame.draw.circle( screen, CIRCLE_COLOR, (int( col * SQUARE_SIZE + SQUARE_SIZE//2 ), int( row * SQUARE_SIZE + SQUARE_SIZE//2 )), CIRCLE_RADIUS, CIRCLE_WIDTH )
            elif board[row][col] == 2:
                pygame.draw.line( screen, CROSS_COLOR, (col * SQUARE_SIZE + SPACE, row * SQUARE_SIZE + SQUARE_SIZE - SPACE), (col * SQUARE_SIZE + SQUARE_SIZE - SPACE, row * SQUARE_SIZE + SPACE), CROSS_WIDTH )    
                pygame.draw.line( screen, CROSS_COLOR, (col * SQUARE_SIZE + SPACE, row * SQUARE_SIZE + SPACE), (col * SQUARE_SIZE + SQUARE_SIZE - SPACE, row * SQUARE_SIZE + SQUARE_SIZE - SPACE), CROSS_WIDTH )

def mark_square(row, col, player):
    board[row][col] = player

def available_square(row, col):
    return board[row][col] == 0

def is_board_full():
    for row in range(BOARD_ROWS):
        for col in range(BOARD_COLS):
            if board[row][col] == 0:
                return False

    return True

def is_board_empty(b):
    for row in range(BOARD_ROWS):
        for col in range(BOARD_COLS):
            if b[row][col] == 0:
                return True

    return False

def check_win(player, b):
    # vertical win check
    for col in range(BOARD_COLS):
        if b[0][col] == player and b[1][col] == player and b[2][col] == player:
            #draw_vertical_winning_line(col, player)
            return True

    # horizontal win check
    for row in range(BOARD_ROWS):
        if b[row][0] == player and b[row][1] == player and b[row][2] == player:
            #draw_horizontal_winning_line(row, player)
            return True

    # asc diagonal win check
    if b[2][0] == player and b[1][1] == player and b[0][2] == player:
        #draw_asc_diagonal(player)
        return True

    # desc diagonal win chek
    if b[0][0] == player and b[1][1] == player and b[2][2] == player:
        #draw_desc_diagonal(player)
        return True

    return False


def restart():
    screen.fill( BG_COLOR )
    draw_lines()
    for row in range(BOARD_ROWS):
        for col in range(BOARD_COLS):
            board[row][col] = 0

def minimax(b, max_play, play):
    if play == 1 and check_win(play, b):
        return -1
    if play == 2 and check_win(play, b):
        return 1
    if is_board_empty(b) == False:
        return 0
    if max_play:
        best = -10000
        for row in range(3):
            for col in range(3):
                if b[row][col] == 0:
                    b[row][col] = 2
                    best = max(best, minimax(b, False, play))
                    b[row][col] = 0
        return best
    else:
        best = 10000
        for row in range(3):
            for col in range(3):
                if b[row][col] == 0:
                    b[row][col] = 1
                    best = min(best, minimax(b, True, play))
                    b[row][col] = 0
        return best

def best_move(b, play):
    best = -1000
    move = (-1, -1)
    for row in range(3):
        for col in range(3):
            if b[row][col] == 0:
                b[row][col] = 2
                move_val = minimax(b, False, 2)
                b[row][col] = 0

                if(move_val > best):
                    move = (row, col)
                    best = move_val
    return move

def cpu_turn(b, play):
    choice = best_move(b, play)
    b[choice[0]][choice[1]] = 2


draw_lines()    

# ---------
# VARIABLES
# ---------
player = 1
game_over = False

# --------
# MAINLOOP
# --------
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            sys.exit()

        if event.type == pygame.MOUSEBUTTONDOWN and not game_over and player == 1:

            mouseX = event.pos[0] # x
            mouseY = event.pos[1] # y

            clicked_row = int(mouseY // SQUARE_SIZE)
            clicked_col = int(mouseX // SQUARE_SIZE)

            if available_square( clicked_row, clicked_col ):

                mark_square( clicked_row, clicked_col, player )
                if check_win( player, board ):
                    game_over = True
                draw_figures()
                player = player % 2 + 1

                

        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_r:
                restart()
                player = 1
                game_over = False
    if player == 2 and not game_over:
        cpu_turn(board, player)
        if check_win( player, board ):
            game_over = True
        draw_figures()
        player = player % 2 + 1

        

    pygame.display.update()

标签： pythonpygameminmax