Differences

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

--- chess:programming:search [2021/10/11 22:34] – peter
+++ chess:programming:search [2022/01/07 10:05] (current) – peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Search ======
-===== 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.
-<code>
+A chess program selects moves via use of a search function.
-score = alphaBetaMax(-oo, +oo, depth);
-</code>
+  * 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.
-<code>
-int alphaBetaMax( int alpha, int beta, int depthleft ) {
-   if ( depthleft == 0 ) return evaluate();
-   for ( all moves) {
-      score = alphaBetaMin( alpha, beta, depthleft - 1 );
-      if( score >= beta )
-         return beta;   // fail hard beta-cutoff
-      if( score > alpha )
-         alpha = score; // alpha acts like max in MiniMax
-   }
-   return alpha;
-}
-int alphaBetaMin( int alpha, int beta, int depthleft ) {
-   if ( depthleft == 0 ) return -evaluate();
-   for ( all moves) {
-      score = alphaBetaMax( alpha, beta, depthleft - 1 );
-      if( score <= alpha )
-         return alpha; // fail hard alpha-cutoff
-      if( score < beta )
-         beta = score; // beta acts like min in MiniMax
-   }
-   return beta;
-}
-</code>
 ----
-===== Minimax =====
+[[Chess:Programming:Search:About Searching|About Searching]]
-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:Alpha-Beta|Alpha-Beta]]
-<code>
+[[Chess:Programming:Search:Binary Search using pthread|Binary Search using pthread]]
-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:Minimax|Minimax]]
+[[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>
 ----
 ==== References ====
+http://web.archive.org/web/20120421170110/http://chessprogramming.wikispaces.com/Alpha-Beta
 http://web.archive.org/web/20120209041607/http://chessprogramming.wikispaces.com/Minimax
@@ Line 102: / Line 31: @@
 http://web.archive.org/web/20120209042116/http://chessprogramming.wikispaces.com/Negamax
+http://web.archive.org/web/20120427185347/http://chessprogramming.wikispaces.com/Quiescence+Search