The thinking process
When NagaSkaki has to make a move, it goes through the following process:
- Look in the opening book to see if it can skip the thinking process
- If a move was found in the opening book, make it!
- If not, decide how much time to use for this move (after each ply the thinking time is updated so that NagaSkaki can use less time for an obvious move and more time when it sees that it will lose material)
- Start a one ply search. This search cannot be interrupted, because we need at least one legal move.
- If there is more than one possible move, keep increasing the search depth by one ply until the time for this move runs out. These searches can be interrupted because we can use the best move of a previous search depth.
Here is a description of what happens inside NagaSkaki’s search algorithm:
- If we’re in the endgame and there is not enough material for checkmate, return a draw score
- Did the user press the stop button or is our time up? In that case stop the search and set a flag for the root function not to trust this score (because we were interrupted)
- Look in the hash table to see if we can skip the search and just return the hash score.
- Is this a draw by 50 move rule? If yes, return draw score
- Are we in check? If yes, we increment the search depth, because this might be a dangerous line.
- Try a null move (let the opponent make two moves in a row), if that doesn’t help the opponent he will probably not play this line and we don’t need to search this line further.
- If we didn’t find a best move in the hash table, do internal iterative deepening (do a search of only a few plies deep, and use the best move from that search)
- See if we can do futility and extended futility pruning (if we are so far behind that even the capture of say a queen won’t bring the score to that of the best line, we don’t need to bother searching deeper)
Now only do we start with the Alpha beta algorithm!
- Make the best move in the move list – each move is given a score as follows:
Hash move – very big bonus
Pawn that queens – big bonus
Bonus for captures – sort of MVV/LVA (most valuable victim/least valuable attacker)
Bonus for killer moves
Bonus for moves from history heuristic
Bonus if the piece moves to a good square - Apply extensions – search deeper if:
A pawn moves to the 7’Th rank
This is the last move with pieces on the board
We recapture with a piece of the same value - If the remaining search depth is more than zero, call the search function and get the score, else call the quiescent search (search only captures exhaustively)
- After all the moves are made, return the best score
- If there were no legal moves: return zero if we are not in check, return mate value if we are.