We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The algorithm is actually pretty simple, but took me a while to figure out since it is easy to overthink. It actually does not (and should not) involve any heuristics or predictions since chess is purely mathematical.
White wins if for any white move black cannot produce a winning move, and white loses if for any black move white cannot produce a winning move.
Pseudocode of the recursive function:
booleannextTurn(currentPlayer,board,currentMove):ifcurrentMove>mreturncurrentPlayer.colorisblack// win if black, lose if whiteforeachmoveincurrentPlayer.generateMoves(board):if(move.takesQueenornotnextTurn(oppositePlayer,move.newBoard,currentMove+1):returntruereturnfalse
Notice the "not" in front of nextTurn. nextTurn always returns true on the first possible move that wins for the current player, and false if there weren't any. So by negating the result of this function for the next player we get a result of true (winning) if no possible moves by the opponent resulted in a win for them, or a result of false (losing) if there was any possible move that resulted in a win for the opponent. Then on the first instance of true in the loop, we return true since our move won.
Since a draw is not possible in this version of chess, this can be used to recursively determine if white can always win.
In addition, infinite loops (repeating moves over and over forever) are impossible in this problem because it always terminates due to the condition that we will never exceed a max number of moves. However, you can reduce the search space by storing past positions so that looping does not occur.
Making a recursive tree of the results of a call to nextTurn that returns false might look like this:
Simplified Chess Engine
You are viewing a single comment's thread. Return to all comments →
The algorithm is actually pretty simple, but took me a while to figure out since it is easy to overthink. It actually does not (and should not) involve any heuristics or predictions since chess is purely mathematical.
White wins if for any white move black cannot produce a winning move, and white loses if for any black move white cannot produce a winning move.
Pseudocode of the recursive function:
Notice the "not" in front of
nextTurn.nextTurnalways returnstrueon the first possible move that wins for the current player, andfalseif there weren't any. So by negating the result of this function for the next player we get a result oftrue(winning) if no possible moves by the opponent resulted in a win for them, or a result offalse(losing) if there was any possible move that resulted in a win for the opponent. Then on the first instance oftruein the loop, we returntruesince our move won.Since a draw is not possible in this version of chess, this can be used to recursively determine if white can always win.
In addition, infinite loops (repeating moves over and over forever) are impossible in this problem because it always terminates due to the condition that we will never exceed a max number of moves. However, you can reduce the search space by storing past positions so that looping does not occur.
Making a recursive tree of the results of a call to nextTurn that returns false might look like this:
This returned false because there was a black move that did not allow white to win.
An illustration of white winning:
This returned true because white always had a path to a win no matter what black did.