The following paragraphs describes briefly the tree search techniques used by KKFChess for a REGULAR chess game. Searches for other chess variant will be similar but not exactly the same.
Like all good chess engines, KKFChess employs an iterative deepening search that can be time or depth bounded. It can also terminate early if certain conditions like mate found, book move, EGTB move, only move or worst alternatives.
The window width of KKFChess is variable. It is widen gradually according to the last search results and last windowing widths. Normally both the upper and lower bound will be shifted but sometimes only one of them will move (usually after failing high or low).
The PVS in KKFChess is the normal null-window type.
The search order for moves in normal chess is:
Hashed moves (from the PV hash table).
Capturing or promoting moves
Killer moves
Non-capturing and non-promoting moves (ordered by move history and piece square values)
Hashed moves are moves that are taken from the hash table. In KKFChess, these moves are taken from the PV hash table and not the positional hash table.
KKFChess keeps 3 killer moves for each ply level. These killers moves have an aging factor that helps the engine to decide which killer move to replace when a new one is found. When a killer move is found, it is either added as a "young" killer and displacing the "oldest" one if it is a new killer, or it's age made "young" again if it is an existing one.
Additional killer moves from 2, 4 and 6 plys down are also checked to increase the probability of a cut off before any moves are generated. One killers for the same search ply are updated.
Unlike most chess engines, KKFChess stores history moves using not only the "from" and "to" square but also the "piece" to move. It is had to say if it is better or worst but that's the way I like it done.
Searches at the root position are handled differently from searches for sub-trees. Root moves search is a modified form of the principle variation search with a much wider windowing re-search if the null-width search returned a boundary score. This wider windowing allows some more distinctions between how good or bad each move is relative to each other.
KKFChess uses fractional search extensions with certain type of positions:
Mate threat detected (by null-move)
Recapturing a piece of the same value
Pushing a passed pawn
Side to move is in check
Forced reply
Pawn promotion
Piece sacrifice on a square next to an enemy king
Most of the above extensions are controllable through the configuration file or console commands.
Futility pruning and razoring are employed to reduce the branching factor of the game tree. Pruning in KKFChess works differently then the conventional razoring/pruning methods. Nodes below P=2 are examined and if the material score is below the expected maximum positional score (plus some margin) then the node is not expanded and the quiescent search called. There are two razoring points, one at P=2 and the other at P=3, both with different margins. P is the remaining depth of the search.
This is an experimental technique that I am testing. The idea is to reduce the search depth of positions outside the main principle variation (in fact moves that were not found in the PV hash table) by assuming that these lines are inferior than the main PV. This helps to speed the search up most of the time but at occasions can cause the engine to exclude a better move until it searches deeper. The speed gained usually allows a deeper search so the draw backs and gains seem to be balanced; unless the depth reduction is chosen to be so large that no other moves besides the ones on the main PV are expanded.
KKFChess uses a null-move search of (D-2) except in real or near pawns only endgames, or in a position where the side to move is in check or the previous move was a null-move. The score from the null search is verified by performing a non-null search at D-1. The latter search not only verifies the null-move but also performs internal iteration on potential null-moves.
Internal iterative search (IIS), if enabled, is used to help ordering moves by performing a shallower search to find a good move for the current position if there were no good moves available (from the hash tables or killer list). Unlike other chess programs, KKFChess only performs a D-4 ply search during IIS. With IIS enabled, the engine was able to find the correct move sequence faster for some positions but slowed down the search for others. Hence it is disabled by default.
IIS may now be redundant since the verified null-move performs similar functions but only to candidate cut-off moves.
Before any nodes are expanded, the engine probes into the learned hash table, the positional hash table, the mating hash table and the endgame tablebases.
To help reduce the horizon effect, KKFChess uses quiescent searches to expand terminal positions with moves that capture or promote. Being checkmated is detected but not giving checkmate - the latter is time consuming because the need to know if the opponent has any legal replies.
Quiescent search probes the EGTBs when appropriate. These probes are most useful during the endgame. Special logic is in place to reduce the number of probes performed so that the search is not slowed down too much when probable positions are reached during quiescent search.
KKFChess does not use SEE (thought I have coded it). Instead, there is a razoring logic built into the quiescent search that mimics SEE.
KKFChess utilizes the "lazy" evaluation technique to exclude the evaluation of time consuming items that will have little effect on the search results - most of the time the tree search functions are looking for bounds and not exact evaluations.
Before a search begins, a maximum positional score (MPS) is estimated for use with the pruning logic. This value is based on the expected material gain/loss of root position. So a position with no queens will have a lesser MPS than one with a queen in either colour. Exception to this are positions with passed pawns, which are treated as if one of the pawns has already queened.
Ideally the MPS and the lazy limit should be recalculated for each position during the search, especially when a passed pawn is created, but for simplicity reasons they are only set once at the root position, just before the search begins.