I am trying to implement a simple minimax algorithm for chess. I have a seemingly working algorithm now, but there may be an error in logic somewhere.
#minimax algorithm
def minimax(BOARD, DEPTH, MAXIMIZE, counter):
#create a list of legal moves
moves = list(BOARD.legal_moves)
score = []
counter = counter + len(moves)
if MAXIMIZE:
if not moves:
return None
#find the best move for the AI
#go through every legal move
for i in moves:
#make copy of the board and push the next legal move
b = deepcopy(BOARD)
b.push(i)
if DEPTH > 1:
#recursively call minimax to go down the tree
temp_move = minimax(b, DEPTH-1, True, counter)
#if the minimax function returns a value
if temp_move is not None:
b.push(temp_move[0])
#evaluate board position at every point
score.append(evals(b, PIECE_VALUE))
#counter = evals(b, PIECE_VALUE, counter)[1]
#select a move with the max board position score
best_move = moves[score.index(min(score))]
return best_move, counter
else:
if not moves:
return None
#find the best move for the human
for i in moves:
#make copy of the board and push the next legal move
b = deepcopy(BOARD)
b.push(i)
if DEPTH > 1:
#recursively call minimax to go down the tree
temp_move = minimax(b, DEPTH-1, False, counter)
if temp_move is not None:
b.push(temp_move[0])
#evaluate board position at every point
score.append(evals(b, PIECE_VALUE))
#counter = evals(b, PIECE_VALUE, counter)[1]
#select a move with the min board position score
best_move = moves[score.index(max(score))]
return best_move, counter
I have a counter int that should count the number of nodes in the tree whenever the 'minimax' function is called, but at any depth I set it returns a value between 15 and 20. Does my function fail to run past depth 1? At depth 3 or 5 it should have hundreds of nodes, but counter always returns ~20.
Full code for reference:
# importing required libraries
import chess
import chess.polyglot
import math
from copy import deepcopy
import random
#initialise chess board
B = chess.Board()
#define search depth
DEPTH = 2
PIECE_VALUE = {
'p':-1,
'r':-5,
'n':-3,
'b':-3,
'k':0,
'q':-9,
'P':1,
'R':5,
'N':3,
'B':3,
'K':0,
'Q':9
}
#genereate a random move from a list of legal moves
def random_ai(BOARD, PIECE_VALUE):
#move = random.choice(list(BOARD.legal_moves))
#print ("selecting a random move")
print ("selecting the best move")
move = select(BOARD, PIECE_VALUE)
return move
#evaluation function
def evals(BOARD, PIECE_VALUE):
score = 0
#iterate over the board and add up all the pieces
for i in range (64):
if BOARD.piece_at(i) is not None:
score = score + PIECE_VALUE[BOARD.piece_at(i).symbol()]
return score
#selection function with minimax and alpha beta pruning
def select(BOARD, PIECE_VALUE):
counter = 0
result = minimax(BOARD, DEPTH, True, counter)
if result is not None:
counter = result[1]
print ("Counter ", counter)
move = result[0]
return move
#minimax algorithm
def minimax(BOARD, DEPTH, MAXIMIZE, counter):
#create a list of legal moves
moves = list(BOARD.legal_moves)
score = []
counter = counter + len(moves)
if MAXIMIZE:
if not moves:
return None
#find the best move for the AI
#go through every legal move
for i in moves:
#make copy of the board and push the next legal move
b = deepcopy(BOARD)
b.push(i)
if DEPTH > 1:
#recursively call minimax to go down the tree
temp_move = minimax(b, DEPTH-1, True, counter)
#if the minimax function returns a value
if temp_move is not None:
b.push(temp_move[0])
#evaluate board position at every point
score.append(evals(b, PIECE_VALUE))
#counter = evals(b, PIECE_VALUE, counter)[1]
#select a move with the max board position score
best_move = moves[score.index(min(score))]
return best_move, counter
else:
if not moves:
return None
#find the best move for the human
for i in moves:
#make copy of the board and push the next legal move
b = deepcopy(BOARD)
b.push(i)
if DEPTH > 1:
#recursively call minimax to go down the tree
temp_move = minimax(b, DEPTH-1, False, counter)
if temp_move is not None:
b.push(temp_move[0])
#evaluate board position at every point
score.append(evals(b, PIECE_VALUE))
#counter = evals(b, PIECE_VALUE, counter)[1]
#select a move with the min board position score
best_move = moves[score.index(max(score))]
return best_move, counter
Your code doesn't do anything with the count that is returned from a recursive call. You should use it to update your local counter.
So change the two occurrences of this code:
if temp_move is not None:
b.push(temp_move[0])
to:
if temp_move is not None:
b.push(temp_move[0])
counter = temp_move[1]