Chess non-hamax function

Question

Hello!

I am trying to write a negamax search algorithm for my chess engine, but I cannot get it to work. As an example, I use the pseudocode wikipedias, but for some reason it does not give the expected results. When I run it using layer 2, it changes my board data structure, although this should not. After the function is finished working with layer 2, all white (or black. Depends on which player calls the function). Pawns move 2 spaces forward from the starting position.

My move and unmake move functions work fine, as I tested them with a non-recursive function that searches up to 5 layers. Then it worked perfectly. There must be something wrong with my negamax implementation.

Many thanks for your help!

def negaMax(self, board, rules, ply, player): """ Implements a minimax algorithm. """ if ply == 0: return self.positionEvaluation() self.max_eval = float('-infinity') self.move_list = board.generateMoves(rules, player) for self.move in self.move_list: board.makeMove(self.move, player) self.eval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player)) board.unmakeMove(self.move, player) if self.eval > self.max_eval: self.max_eval = self.eval return self.max_eval 

Answer 1

The main problem here is that I consider using object variables instead of a local variable.

self.move is an object variable, every time you change it - each level of recursion “sees” the change, which is usually bad for recursive algorithms.

Recursive algorithms should be self-sufficient and minimal if there are any changes in the calling environment - this greatly facilitates the flow of the algorithm.

The two main problems that I see in this code are:

• self.move must be a local variable (declare it as move ). When you later do: board.unmakeMove(self.move, player) - I suspect that the board cancels another move that was set deeper in the recursion tree, and not the one you intended. Using a local variable will eliminate this unwanted behavior.
• Each level of the recursive call sets self.max_eval = float('-infinity') - so you are constantly changing it, although this is probably not what you want to do.

The solution should be something like this:

 def negaMax(self, board, rules, ply, player): """ Implements a minimax algorithm. """ if ply == 0: return self.positionEvaluation() max_eval = float('-infinity') move_list = board.generateMoves(rules, player) for move in move_list: board.makeMove(move, player) currentEval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player)) board.unmakeMove(move, player) if currentEval > max_eval: max_eval = currentEval return max_eval 

I'm not 100% sure that it will really solve everything in the code (but it will solve part of it), but I am 100% sure that I will avoid object variables, which will make your code much easier to understand and debug.