Chess Engines' Search Trees • page 1/2 • General Chess Discussion • lichess.org

Do chess engines generally use minimax to choose from candidate moves?

Are there generic packages/libraries that implement this?

Has anyone tried using other strategies (for example maximax or minimaxregret)?

Can anyone here speak from direct experience?

Do chess engines generally use minimax to choose from candidate moves? Are there generic packages/libraries that implement this? Has anyone tried using other strategies (for example maximax or minimaxregret)? Can anyone here speak from direct experience?

drwn

#2

Chess is a deterministic game, so I'm not sure how those decision making strategies could apply to chess engines. Chess engines are always 100% correct... until they aren't.

phoenixshade

#3

They use minmax in conjunction with alpha-beta pruning, which is kind of a way of estimating minmax when there are too many possibilities to evaluate all of them. Thus, unpromising lines are cut from the analysis. At times, this can actually cause the best move to be missed; there's a famous composition that involves 4 underpromotions that engines miss because the best line gets pruned before it is evaluated deeply enough.

petri999

#4

No alfa-beta as is cannot cause good move to missed. it merely heurestic to do reasoning like
Move 1: maintains score vevent
Move 2: with 1st reply opponent is better -> no point checking other replies as you alreasy knwo that move2 is worse than move 1

when you miss good moves is the alfa-beta heurestics like NULL move pruning i.e you first search to that your move is no-move and this is set as alfa-beta cut point and then you evaluate real moves. This makes programs generally stronger but can miss a good move. alfa-beta window has same property - depends on implementation

best place to start chess engine study: https://www.chessprogramming.org/Main_Page

And for search sub page https://www.chessprogramming.org/Search

and sample implementation of the engine https://www.chessprogramming.org/CPW-Engine

and in case you are a python programmes there is pychess to look at

No alfa-beta as is cannot cause good move to missed. it merely heurestic to do reasoning like Move 1: maintains score vevent Move 2: with 1st reply opponent is better -> no point checking other replies as you alreasy knwo that move2 is worse than move 1 when you miss good moves is the alfa-beta heurestics like NULL move pruning i.e you first search to that your move is no-move and this is set as alfa-beta cut point and then you evaluate real moves. This makes programs generally stronger but can miss a good move. alfa-beta window has same property - depends on implementation best place to start chess engine study: https://www.chessprogramming.org/Main_Page And for search sub page https://www.chessprogramming.org/Search and sample implementation of the engine https://www.chessprogramming.org/CPW-Engine and in case you are a python programmes there is pychess to look at

TheGreatUnwashed edited

#5

@drwn , thanks for your reply.

It is true that chess is a deterministic game and also one of perfect information.

However there is an aspect of the game that renders both of these descriptions somewhat meaningless.

Branches of the tree are not necessarily evaluated to terminal nodes (where the outcome is one of: 1(win), -1(loss) and (0) draw) but are evaluated to nodes determined to be stable by heuristic processes.

Those heuristic processes are incomplete and subject to error. Thus chess is not in any practical sense a game of perfect information, thus undermining the rationale for the choice of minimax as the necessarily best strategy.


@petri999, thanks for your response and the helpful links.

If anyone is actually implementing a chess-engine or is planning on doing so, I'll gladly flesh out the details of this argument, and its consequences.

@drwn , thanks for your reply. It is true that chess is a deterministic game and also one of perfect information. However there is an aspect of the game that renders both of these descriptions somewhat meaningless. Branches of the tree are not necessarily evaluated to terminal nodes (where the outcome is one of: 1(win), -1(loss) and (0) draw) but are evaluated to nodes determined to be stable by heuristic processes. Those heuristic processes are incomplete and subject to error. Thus chess is not in any _practical_ sense a game of perfect information, thus undermining the rationale for the choice of minimax as the _necessarily_ best strategy. ~~~ @petri999, thanks for your response and the helpful links. ~~~ If anyone is actually implementing a chess-engine or is planning on doing so, I'll gladly flesh out the details of this argument, and its consequences.

petri999

#6

Problem with anything else than min/max (monte carlo search can be proven to converge to min/max just with huge effort) is that it might be - actually for sure is - exploitable. All other means of deciding on move rely to a degree opponent not seeing something. And this is actually what montecarlo search does if dont let it run for ever. It will greater weight to opponents move that is in engines opinion most likely. Obviously if you let it long enough the min/max sense best move will emerge as most likely.

The power of min/max can be seen from Stockfish NNUE. it neural net for ordering move candidates and evaluation of leaf node. And it did beat LeelaChess0 which uses montecarlo search. Just side note that move ordering is of utmost importance in alfa-beta pruning.

anyway this kinda moot. even if you implement simplistic chess engine like the sample engine in link above it will of strength of a national master and be able to beat 99% of players attending tournament. Any decent engine with modern hw can beat any human. Whether engine is only 300 Elo points above best or 500 points is not that important. Besides the effort needed to go from good hobby engine to level of crafty/stockfish/rybka is huge. several tens of years of effort if you plan to do it on your own.

Problem with anything else than min/max (monte carlo search can be proven to converge to min/max just with huge effort) is that it might be - actually for sure is - exploitable. All other means of deciding on move rely to a degree opponent not seeing something. And this is actually what montecarlo search does if dont let it run for ever. It will greater weight to opponents move that is in engines opinion most likely. Obviously if you let it long enough the min/max sense best move will emerge as most likely. The power of min/max can be seen from Stockfish NNUE. it neural net for ordering move candidates and evaluation of leaf node. And it did beat LeelaChess0 which uses montecarlo search. Just side note that move ordering is of utmost importance in alfa-beta pruning. anyway this kinda moot. even if you implement simplistic chess engine like the sample engine in link above it will of strength of a national master and be able to beat 99% of players attending tournament. Any decent engine with modern hw can beat any human. Whether engine is only 300 Elo points above best or 500 points is not that important. Besides the effort needed to go from good hobby engine to level of crafty/stockfish/rybka is huge. several tens of years of effort if you plan to do it on your own.

TheGreatUnwashed edited

#7

@petri999, I appreciate your input -- there aren't many people in my life that would indulge me in a conversation that begins "let's talk about minimax".

The Monte Carlo analysis you talk about (AFAICT) refers to games of chance with known probabilistic outcomes.

Only chess isn't such a game.

Neither is it a game of perfect information (in any practical sense) for the reasons i gave above.

Therefore I wonder (just wonder) if there isn't a small crack in the idea that minimax is strictly the way to go.

EDIT: actually, I think I am not addressing your points at all. Let me think... (I'll be back)

@petri999, I appreciate your input -- there aren't many people in my life that would indulge me in a conversation that begins "let's talk about minimax". The Monte Carlo analysis you talk about (AFAICT) refers to games of chance with known probabilistic outcomes. Only chess isn't such a game. Neither is it a game of perfect information (in any practical sense) for the reasons i gave above. Therefore I wonder (just wonder) if there isn't a small crack in the idea that minimax is strictly the way to go. EDIT: actually, I think I am not addressing your points at all. Let me think... (I'll be back)

TheGreatUnwashed

#8

Hey @petri999

I've caught up now, and I'm still going to maintain that the motivation for minimax is that chess is a game of perfect information, like draughts (checkers) or noughts-and-crosses (tic-tac-toe).

The problem is that the chess tree is too big to search exhaustively, so searches are necessarily and arbitrarily truncated -- thus rendering the game not a game of perfect information in any practical sense. Indeed, it is already well-understood that this can lead to horizon effects (where the true consequences of a move are beyond the search depth).

Of course you are right, any half-decent chess-engine is already massively strong in comparison to your average human opponent.

Hey @petri999 I've caught up now, and I'm still going to maintain that the motivation for minimax is that chess is a game of perfect information, like draughts (checkers) or noughts-and-crosses (tic-tac-toe). The problem is that the chess tree is too big to search exhaustively, so searches are necessarily and _arbitrarily_ truncated -- thus rendering the game _not_ a game of perfect information in any practical sense. Indeed, it is already well-understood that this can lead to horizon effects (where the true consequences of a move are beyond the search depth). Of course you are right, any half-decent chess-engine is already massively strong in comparison to your average human opponent.

ProgrammerAngrim

#9

Do chess engines generally use minimax to choose from candidate moves?
yes. With lots of tree shaping and depth modifications, but as far as how to pick the best move.

Are there generic packages/libraries that implement this?
I expect so, but can't imagine them being fast enough to be used in very serious programs.

Has anyone tried using other strategies (for example maximax or minimaxregret)?
I've tried using an engine that just used the proof:disproof ratio from a proof number search as it's evaluation.
It plays oddly to say the least, in some situations it works well, but on average an evaluation based minmax can do better.
It is a good way to get a jump-start on a new chess variant though, since it uses nothing except win/lose/number of legal moves in a non-leaf position, and results in "better than most experienced humans" play in games where nobody knows what an evaluation should look like yet.

Can anyone here speak from direct experience?
yes.

>Do chess engines generally use minimax to choose from candidate moves? yes. With lots of tree shaping and depth modifications, but as far as how to pick the best move. >Are there generic packages/libraries that implement this? I expect so, but can't imagine them being fast enough to be used in very serious programs. >Has anyone tried using other strategies (for example maximax or minimaxregret)? I've tried using an engine that just used the proof:disproof ratio from a proof number search as it's evaluation. It plays oddly to say the least, in some situations it works well, but on average an evaluation based minmax can do better. It is a good way to get a jump-start on a new chess variant though, since it uses nothing except win/lose/number of legal moves in a non-leaf position, and results in "better than most experienced humans" play in games where nobody knows what an evaluation should look like yet. >Can anyone here speak from direct experience? yes.

petri999

#10

Are there generic packages/libraries that implement this?
I expect so, but can't imagine them being fast enough to be used in very serious programs.

well samples are good to understand. serious implementatios are hardedt to undestand. But there are implementatios good enoug for serious program available in variousl open&free licences
https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp
thats only about 2000 lines so can still be understood
https://github.com/MartinMSPedersen/Crafty-Chess/blob/master/source/search.c
thats only 1000 liness but stuff like Q-search is other file
GnuChess is also pretty strong http://svn.savannah.gnu.org/viewvc/chess/trunk/src/engine/search_full.cpp?view=log there is another search file there I did no bother to look are alternatives or parts os the same.

Oh jumps start with no evaluation function monte-carlo search with random move games to end also serves as evaluation . that was 1st decent strength Go programmin way. no onve ever managed to evaluation function manually that was any good

>Are there generic packages/libraries that implement this? I expect so, but can't imagine them being fast enough to be used in very serious programs. well samples are good to understand. serious implementatios are hardedt to undestand. But there are implementatios good enoug for serious program available in variousl open&free licences https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp thats only about 2000 lines so can still be understood https://github.com/MartinMSPedersen/Crafty-Chess/blob/master/source/search.c thats only 1000 liness but stuff like Q-search is other file GnuChess is also pretty strong http://svn.savannah.gnu.org/viewvc/chess/trunk/src/engine/search_full.cpp?view=log there is another search file there I did no bother to look are alternatives or parts os the same. Oh jumps start with no evaluation function monte-carlo search with random move games to end also serves as evaluation . that was 1st decent strength Go programmin way. no onve ever managed to evaluation function manually that was any good