目前正在测试一个使用 minimax 实现的连接四,并且正在使用 numpy 数组和一个常规矩阵。我尝试使用使用常规列表矩阵而不是 numpy 数组创建的板来运行 minimax 函数,并且它不断填充板状态而不是仅丢弃一块。我认为创建董事会状态的浅表副本并通过它不会影响事情,但我对此有点难过。它适用于 numpy 数组。
import numpy as np
import random
import math
import copy
ROW_COUNT = 6
COLUMN_COUNT = 7
PLAYER = 0
AI = 1
EMPTY = 0
PLAYER_PIECE = 1
AI_PIECE = 2
WINDOW_LENGTH = 4
def create_board():
board = [[0 for x in range(COLUMN_COUNT)] for i in range(ROW_COUNT)]
# board = np.zeros((ROW_COUNT,COLUMN_COUNT), dtype=int)
return board
def drop_piece(board, row, col, piece):
board[row][col] = piece
def is_valid_location(board, col):
return board[0][col] == 0
def get_next_open_row(board, col):
for r in range(ROW_COUNT-1, -1, -1):
if board[r][col] == 0:
return r
def print_board(board):
# print(np.flip(board, 0))
for i in board:
print(i)
def winning_move(board, piece):
# Check horizontal locations for win
for c in range(COLUMN_COUNT-3):
for r in range(ROW_COUNT):
if board[r][c] == piece and board[r][c+1] == piece and board[r][c+2] == piece and board[r][c+3] == piece:
return True
# Check vertical locations for win
for c in range(COLUMN_COUNT):
for r in range(ROW_COUNT-3):
if board[r][c] == piece and board[r+1][c] == piece and board[r+2][c] == piece and board[r+3][c] == piece:
return True
# Check positively sloped diaganols
for c in range(COLUMN_COUNT-3):
for r in range(ROW_COUNT-3):
if board[r][c] == piece and board[r+1][c+1] == piece and board[r+2][c+2] == piece and board[r+3][c+3] == piece:
return True
# Check negatively sloped diaganols
for c in range(COLUMN_COUNT-3):
for r in range(3, ROW_COUNT):
if board[r][c] == piece and board[r-1][c+1] == piece and board[r-2][c+2] == piece and board[r-3][c+3] == piece:
return True
def evaluate_window(window, piece):
score = 0
opp_piece = PLAYER_PIECE
if piece == PLAYER_PIECE:
opp_piece = AI_PIECE
if window.count(piece) == 4:
score += 100
elif window.count(piece) == 3 and window.count(EMPTY) == 1:
score += 5
elif window.count(piece) == 2 and window.count(EMPTY) == 2:
score += 2
if window.count(opp_piece) == 3 and window.count(EMPTY) == 1:
score -= 4
return score
def score_position(board, piece):
score = 0
## Score center column
# center_array = [int(i) for i in list(board[:, COLUMN_COUNT//2])]
center_array = [int(i) for i in [col[COLUMN_COUNT//2] for col in board]]
center_count = center_array.count(piece)
score += center_count * 3
## Score Horizontal
for r in range(ROW_COUNT):
# row_array = [int(i) for i in list(board[r,:])]
row_array = [i for i in board[r]]
for c in range(COLUMN_COUNT-3):
window = row_array[c:c+WINDOW_LENGTH]
score += evaluate_window(window, piece)
## Score Vertical
for c in range(COLUMN_COUNT):
# col_array = [int(i) for i in list(board[:,c])]
col_array = [col[c] for col in board]
for r in range(ROW_COUNT-3):
window = col_array[r:r+WINDOW_LENGTH]
score += evaluate_window(window, piece)
## Score posiive sloped diagonal
for r in range(ROW_COUNT-3):
for c in range(COLUMN_COUNT-3):
window = [board[r+i][c+i] for i in range(WINDOW_LENGTH)]
score += evaluate_window(window, piece)
for r in range(ROW_COUNT-3):
for c in range(COLUMN_COUNT-3):
window = [board[r+3-i][c+i] for i in range(WINDOW_LENGTH)]
score += evaluate_window(window, piece)
return score
def is_terminal_node(board):
return winning_move(board, PLAYER_PIECE) or winning_move(board, AI_PIECE) or len(get_valid_locations(board)) == 0
def minimax(board, depth, alpha, beta, maximizingPlayer):
valid_locations = get_valid_locations(board)
is_terminal = is_terminal_node(board)
if depth == 0 or is_terminal:
if is_terminal:
if winning_move(board, AI_PIECE):
return (None, 100000000000000)
elif winning_move(board, PLAYER_PIECE):
return (None, -10000000000000)
else: # Game is over, no more valid moves
return (None, 0)
else: # Depth is zero
return (None, score_position(board, AI_PIECE))
if maximizingPlayer:
value = -math.inf
column = random.choice(valid_locations)
for col in valid_locations:
row = get_next_open_row(board, col)
b_copy = board.copy()
drop_piece(b_copy, row, col, AI_PIECE)
new_score = minimax(b_copy, depth-1, alpha, beta, False)[1]
if new_score > value:
value = new_score
column = col
alpha = max(alpha, value)
if alpha >= beta:
break
return column, value
else: # Minimizing player
value = math.inf
column = random.choice(valid_locations)
for col in valid_locations:
row = get_next_open_row(board, col)
b_copy = board.copy()
drop_piece(b_copy, row, col, PLAYER_PIECE)
new_score = minimax(b_copy, depth-1, alpha, beta, True)[1]
if new_score < value:
value = new_score
column = col
beta = min(beta, value)
if alpha >= beta:
break
return column, value
def get_valid_locations(board):
valid_locations = []
for col in range(COLUMN_COUNT):
if is_valid_location(board, col):
valid_locations.append(col)
return valid_locations
def pick_best_move(board, piece):
valid_locations = get_valid_locations(board)
best_score = -10000
best_col = random.choice(valid_locations)
for col in valid_locations:
row = get_next_open_row(board, col)
temp_board = board.copy()
drop_piece(temp_board, row, col, piece)
score = score_position(temp_board, piece)
if score > best_score:
best_score = score
best_col = col
return best_col
在这里测试,只丢一块,然后运行 minimax 以获得最好的一块。
board = create_board()
print_board(board)
print("\n")
game_over = False
if is_valid_location(board,1):
row = get_next_open_row(board,1)
drop_piece(board, row, 1, PLAYER_PIECE)
print_board(board)
print("\n")
checker, score = minimax(board, 5, -math.inf, math.inf, True)
if is_valid_location(board,checker):
row = get_next_open_row(board,checker)
drop_piece(board, row, checker, AI_PIECE)
print_board(board)
print("\n")