chess:programming:search
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| chess:programming:search [2021/10/11 22:28] – created peter | chess:programming:search [2022/01/07 10:05] (current) – peter | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Chess - Programming - Search ====== | ====== Chess - Programming - Search ====== | ||
| + | |||
| + | 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. | ||
| + | |||
| + | 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. | ||
| ---- | ---- | ||
| - | ===== Negamax ===== | + | [[Chess: |
| - | Negamax is a common way of implementing minimax and derived algorithms. | + | [[Chess: |
| - | * 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: | + | [[Chess:Programming: |
| - | < | + | [[Chess: |
| - | max(a, b) == -min(-a, -b) | + | |
| - | </ | + | |
| - | This is how the pseudo-code of the recursive algorithm looks like. For clarity move making and unmaking is omitted. | + | [[Chess: |
| - | < | + | [[Chess: |
| - | 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; | + | |
| - | } | + | |
| - | </ | + | |
| ---- | ---- | ||
| ==== References ==== | ==== References ==== | ||
| + | |||
| + | http:// | ||
| + | |||
| + | http:// | ||
| http:// | http:// | ||
| + | http:// | ||
chess/programming/search.1633991303.txt.gz · Last modified: 2021/10/11 22:28 by peter