Background: I am trying to develop a Chess game which allows the user to play against the computer using Kivy framework in python and the minimax algorithm. The way I made the game is weird to begin with as I made it so that its an 8x8 chess board of buttons, each button having an image under it, either empty representing an empty position or an image of a chess piece representing the piece and an ID to each position of the grid. As a piece moves from one position (or id) to another, the piece can be identified to be at such position by getting the source of the image at that id. Also almost the entire game is written under a CustomButton class and all functions are called at the release of any button.
The Problem: The chess game works just fine but upon implementing the minimax algorithm, it does not seem to work. I do not get an error but rather the algorithm keeps looping endlessly, even when depth is 0, and the recursion count reaches thousands till I stop running it. Here is the code to the relevant functions:
def reformat_all_moves(self, all_moves):
temp = []
for id, moves in all_moves.items():
for move in moves:
temp.append((id, move))
return temp
def get_all_moves(self): # Find all possible moves for the Computer, assume the computer is always the black player.
_, id_list = self.parent.parent.all_buttons()
king_id = 0
all_moves = {}
# Get a list of all black possible moves
for id in id_list:
button = self.parent.parent.find_button(id)
src = button.get_src()
if 'king' in src:
king_id = id
if 'black' in src:
moves, _, _, _ = self.helper_action(id, src, button, (0, ''), False, id_list, False)
all_moves[id] = moves
check, _, _ = self.checkmate(king_id, 0, id_list, (0, ''))
if check[1] and check[0] == 'black':
self.next_moves(king_id)
moves_dict = self.reformat_possible_moves()
return moves_dict
return all_moves
def eval(self, state_of_game):
total_eval = 0
piece_value = {'pawn': 1, 'knight': 3, 'bishop': 3, 'rook': 5, 'Queen': 9, 'king': 10}
white_eval = 0
black_eval = 0
numbers = [1,2,3,4,5,6,7,8,9,10,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
new_id = 0
temp = {}
temp_list = []
for id in state_of_game: # get rid of duplicates
if id in temp:
value = temp.get(id)
temp[id] = value+1
else:
temp[id] = 1
for key, value in temp.items():
temp_list.append(key)
state_of_game = temp_list
print(state_of_game, len(state_of_game), self.changes)
for id in state_of_game:
if self.check_for_change_id(id) is not None:
src, new_id = self.check_for_change_id(id)
else:
src = self.parent.parent.find_button(id).get_src()
for piece, value in piece_value.items():
if piece in src:
if 'black' in src:
black_eval += value
elif 'white' in src:
white_eval += value
total_eval = black_eval - white_eval
print(total_eval, f'Black: {black_eval}, White: {white_eval}' )
return total_eval
def minimax(self, state_of_game, depth, alpha, beta, max_player): # The state of game will be represented by the "id_list"
self.recursion_count += 1
print(Fore.YELLOW + f"Recursion count: {self.recursion_count}, {depth}")
if depth == 0 or self.terminal():
return self.eval(state_of_game), None
original_state = copy.deepcopy(state_of_game)
if max_player:
best_val = -float('inf') # Negative infinity
print(Fore.BLUE + 'Best_val Max Player: ', best_val, self.recursion_count)
all_moves = self.get_all_moves()
moves_list = self.reformat_all_moves(all_moves)
print(Fore.YELLOW + 'MAX')
for id_move in moves_list:
new_state_of_game, move_id_src, id = self.make_move_comp(original_state, id_move)
# To get the value of the new_state_of_game
val, _ = self.minimax(new_state_of_game, depth - 1, alpha, beta, False)
# Undo the changes
self.undo_comp_move(id_move, new_state_of_game)
best_val = max(best_val, val)
best_move = (id, move_id_src)
alpha = max(alpha, val)
if beta <= alpha:
print(Fore.RED + 'broken')
break
return best_val, best_move
else:
worst_val = float('inf') # Positive infinity
all_moves = self.get_all_moves()
moves_list = self.reformat_all_moves(all_moves)
print(Fore.GREEN + 'MIN')
for id_move in moves_list:
new_state_of_game, move_id_src, id = self.make_move_comp(original_state, id_move)
# To get the value of the new_state_of_game
val, _ = self.minimax(new_state_of_game, depth - 1, alpha, beta, True)
# Undo the changes
self.undo_comp_move(id_move, new_state_of_game)
worst_val = min(worst_val, val)
worst_move = (id, move_id_src)
beta = min(beta, val)
if beta <= alpha:
print(Fore.RED + 'broken')
break
return worst_val, worst_move
def make_move_comp(self, original_state, id_move):
id = id_move[0]
move = id_move[1]
if self.check_for_change_id(id) is not None: # Check if the id is in the "changes" dict.
first_button = '' # There should be no problem in passing a fake first_button value/string as the code will terminate before the need of using the first_button, since allow is set to False here.
(first_img_src, id_to_pass) = self.check_for_change_id(id)
self.changes.pop(id_to_pass) # undo the change
else:
first_button = self.parent.parent.find_button(id)
first_img_src = first_button.get_src()
id_to_pass = id
if self.check_for_change_move(move) is not None: # Check if the move is in the "changes" dict.
src = self.check_for_change_move(move)[0]
self.changes.pop(move)
else:
move_button = self.parent.parent.find_button(move)
src = move_button.get_src()
move_id_src = (move, src)
self.changes[move] = (first_img_src, id)
#_, _, _, new_state_of_game = self.helper_action(id_to_pass, first_img_src, first_button, move_id_src, False, original_state,False) # The move should be the id of the second button
new_state_of_game = original_state
new_state_of_game.remove(id_to_pass)
new_state_of_game.append(move)
return new_state_of_game, move_id_src, id
def undo_comp_move(self, id_move, state_of_game):
id = id_move[0]
move = id_move[1]
if self.check_for_change_id(id):
src, id_to_remove = self.check_for_change_id(id)
self.changes.pop(id_to_remove)
if move in state_of_game:
state_of_game.remove(move)
state_of_game.append(id)
return state_of_game
def preform_action_comp(self):
move = 0
self.recursion_count = 0
_, id_list = self.parent.parent.all_buttons()
all_moves = self.get_all_moves()
# Checking terminal State
if len(all_moves) == 0 and self.checkmate_bol:
return None
elif len(all_moves) == 0 and not self.checkmate_bol:
return None
best_val, best_move = self.minimax(id_list, 3, -float('inf'), float('inf'), True)
move_id_src = best_move[1]
id = best_move[0]
button = self.parent.parent.find_button(id)
src = button.get_src()
# Append the move to the log list
self.log.append(move_id_src[1])
# Preform action
False_movement = self.action(button, src, True, id, move_id_src) # The move should be the id of the second button
print(id_list)
if False_movement:
print(Fore.RED + "FALSE")
print(best_val, best_move)
self.preform_action_comp()
P.S 1. the self.changes is a dictionary which keeps track of a change done by the computer throughout the running of this algorithm, as since to identify a certain piece at a certain ID it has to physically be at that button, however to get around that I just add the source of the image and the original id (the true position of the image) and the hypothetical "changed" id as the key, to be able to retrieve it later. 2. The evaluation function eval() is only a simple random right now as a starter, but it isn't working the way it is supposed to, obviously.
I would really appreciate any help or guidance regarding this matter, I am aware that this isn't the most common way of developing a chess game but I took it as a challenge to myself. Thank you for your time and help.
Checked that the way the algorihtm is written is correct, tried changing the return statement to be inside the for loop, and thats the only time it actually runs as expected, and stops at depth 0. However as expected it just executes the first move in the moves list.