|
|
How NagaSkaki
plays chess
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.
<<
Previous Next >>
|
