Differences

This shows you the differences between two versions of the page.

--- chess:programming:search [2021/10/11 22:43] – peter
+++ chess:programming:search [2022/01/07 10:05] (current) – peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Search ======
-[[Chess:Programming:Search:Alpha-Beta|Alpha-Beta]]
+The object of Chess is to checkmate the other player, to avoid being checkmated, or to achieve a draw if that is the best thing given the circumstances.
-[[Chess:Programming:Search:Minimax|Minimax]]
-[[Chess:Programming:Search:Negamax|Negamax]]
-[[Chess:Programming:Search:Quiescence Search|Quiescence Search]]
+A chess program selects moves via use of a search function.
+  * A search function is a function that is passed information about the game, and tries to find the best move for side that the program is playing.
 ----
-----
+[[Chess:Programming:Search:About Searching|About Searching]]
-===== Minimax =====
+[[Chess:Programming:Search:Alpha-Beta|Alpha-Beta]]
-Minimax is an algorithm used to determine the score in a zero-sum game after a certain number of moves, with best play according to an evaluation function.
+[[Chess:Programming:Search:Binary Search using pthread|Binary Search using pthread]]
-<code>
+[[Chess:Programming:Search:Minimax|Minimax]]
-int maxi( int depth ) {
-    if ( depth == 0 ) return evaluate();
-    int max = -oo;
-    for ( all moves) {
-        score = mini( depth - 1 );
-        if( score > max )
-            max = score;
-    }
-    return max;
-}
-int mini( int depth ) {
-    if ( depth == 0 ) return -evaluate();
-    int min = +oo;
-    for ( all moves) {
-        score = maxi( depth - 1 );
-        if( score < min )
-            min = score;
-    }
-    return min;
-}
-</code>
+[[Chess:Programming:Search:Negamax|Negamax]]
+[[Chess:Programming:Search:Quiescence Search|Quiescence Search]]
-----
-===== Negamax =====
-Negamax is a common way of implementing minimax and derived algorithms.
-  * Instead of using two separate subroutines for the Min player and the Max player, it passes on the negated score due to following mathematical relation:
-<code>
-max(a, b) == -min(-a, -b)
-</code>
-This is how the pseudo-code of the recursive algorithm looks like. For clarity move making and unmaking is omitted.
-<code>
-int negaMax( int depth ) {
-    if ( depth == 0 ) return evaluate();
-    int max = -oo;
-    for ( all moves)  {
-        score = -negaMax( depth - 1 );
-        if( score > max )
-            max = score;
-    }
-    return max;
-}
-</code>
-----
-===== Quiescence Search =====
-<code>
-int Quiesce( int alpha, int beta ) {
-    int stand_pat = Evaluate();
-    if( stand_pat >= beta )
-        return beta;
-    if( alpha < stand_pat )
-        alpha = stand_pat;
-    until( every_capture_has_been_examined )  {
-        MakeCapture();
-        score = -Quiesce( -beta, -alpha );
-        TakeBackMove();
-        if( score >= beta )
-            return beta;
-        if( score > alpha )
-           alpha = score;
-    }
-    return alpha;
-}
-</code>
 ----