My basic understanding is that an engine usually has an evaluator that only looks at the current position, and a calculator that goes into move trees and calls to the evaluator to look at the resulting positions.
Mate and stalemate still require some form of calculation.
- Check means: one player has a move that takes a King.
- Mate or stalemate means: whatever move one player does, the other player will always have a next move that takes the King.
Then how is this determined? I see basically 2 options:
1. The evaluator does some calculation work and determines mate and stalemate accurately
2. The evaluator can't determine mate and stalemate, it only sees when a King is off the board, the calculator determines mate and stalemate but for that it must calculate sufficiently deep
How does an engine determine mate and stalemate?
Moderators: hgm, Rebel, chrisw
-
evert823
- Posts: 8
- Joined: Thu Oct 29, 2020 9:32 am
- Full name: Evert Jan Karman
-
Terje
- Posts: 347
- Joined: Tue Nov 19, 2019 4:34 am
- Location: https://github.com/TerjeKir/weiss
- Full name: Terje Kirstihagen
Re: How does an engine determine mate and stalemate?
If the side to move has no moves and is in check -> checkmate, not in check -> stalemate.
It is usually done in search, not in evaluation I think.
It is usually done in search, not in evaluation I think.
-
hgm
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How does an engine determine mate and stalemate?
The simplest way to do it is in the recursive search routine:
* If one of the moves of the player on move captures the opponent King, that player wins, and you return the maximum score (let's call it +INF)
* In the caller the score of the move reaching that position then shows up as -INF. Which you can also use as the initial value for determining the best score you can get, so that illegal moves are effectively ignored.
* if after considering all moves, the bestScore is still at -INF, you know you did not have any legal moves. So you are check- or stalemated.
* in that case you play a 'null move' (= turn pass), search it 1 ply deep and look what score you get. If it was also -INF, you were in check, and are thus checkmated
* when the null move had a different score, you are stalemated, and return the draw score (0 if you have no contempt for your opponent).
* when checkmated, you return -INF + 1 + ply, where 'ply' is the distance to the root of your search (so that you get less negative points the more you can delay the mate)
That is all. But you are right; it takes some depth to see mates at all this way. You won't recognize them in the leaves of your search tree.
One question: Did you use alpha-beta pruning in your engine, or do you always search all moves in every position. Using the '1 refutation is enough' principle will nearly double your search depth.
* If one of the moves of the player on move captures the opponent King, that player wins, and you return the maximum score (let's call it +INF)
* In the caller the score of the move reaching that position then shows up as -INF. Which you can also use as the initial value for determining the best score you can get, so that illegal moves are effectively ignored.
* if after considering all moves, the bestScore is still at -INF, you know you did not have any legal moves. So you are check- or stalemated.
* in that case you play a 'null move' (= turn pass), search it 1 ply deep and look what score you get. If it was also -INF, you were in check, and are thus checkmated
* when the null move had a different score, you are stalemated, and return the draw score (0 if you have no contempt for your opponent).
* when checkmated, you return -INF + 1 + ply, where 'ply' is the distance to the root of your search (so that you get less negative points the more you can delay the mate)
That is all. But you are right; it takes some depth to see mates at all this way. You won't recognize them in the leaves of your search tree.
One question: Did you use alpha-beta pruning in your engine, or do you always search all moves in every position. Using the '1 refutation is enough' principle will nearly double your search depth.
-
evert823
- Posts: 8
- Joined: Thu Oct 29, 2020 9:32 am
- Full name: Evert Jan Karman
Re: How does an engine determine mate and stalemate?
I did something like this:
The calculator keeps track of its best guaranteed move score. It passes this as parameter in the recursive call.
One level deeper it says: I found one counter move making this continuation worse than what was already guaranteed for my opponent, so I stop this search.
This proning was a bit hard to understand for me, but I think this is what you mean by '1 refutation is enough'.
The calculator keeps track of its best guaranteed move score. It passes this as parameter in the recursive call.
One level deeper it says: I found one counter move making this continuation worse than what was already guaranteed for my opponent, so I stop this search.
This proning was a bit hard to understand for me, but I think this is what you mean by '1 refutation is enough'.
-
hgm
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How does an engine determine mate and stalemate?
Indeed, when you have determined that a move has a score that punishes the opponent's preceding move more than another move he is already certain of, there is no need to examine more moves to see if you can punish it harder. The jargon for this is a 'beta cutoff'.
This is not the best you can do, however. The better alternative for the opponent that defines the reference for counting as refuted can also occur a few ply earlier, instead of just on the preceding ply. (This is called a 'deep cutoff'.) So while you are searching the three, in every node you will have a score 'window' (typically referred to as [alpha, beta]), defined by the best deviations (so far) from the currently investigated line by player A and by player B. If the current branch will score too high, one player will avoid it. If it scores too low, the other player will avoid it. So you are not interested how far outside the window the actual score is; as soon as you have one move that pushes the score out of the window one of the players will consider the current line refuted, and will avoid it by playing the better move he aready found. Only while the best-so-far score is still inside the window you have to keep trying other moves to see whether you can do better.
So the basic method is to start with a completely 'open' window [-INF, INF] in the root, and pass this in the recursive search call to the deeper plies. Each ply will shrink the window by pushing one of its bounds to the score of the best move it found so far ('raising alpha').
This is not the best you can do, however. The better alternative for the opponent that defines the reference for counting as refuted can also occur a few ply earlier, instead of just on the preceding ply. (This is called a 'deep cutoff'.) So while you are searching the three, in every node you will have a score 'window' (typically referred to as [alpha, beta]), defined by the best deviations (so far) from the currently investigated line by player A and by player B. If the current branch will score too high, one player will avoid it. If it scores too low, the other player will avoid it. So you are not interested how far outside the window the actual score is; as soon as you have one move that pushes the score out of the window one of the players will consider the current line refuted, and will avoid it by playing the better move he aready found. Only while the best-so-far score is still inside the window you have to keep trying other moves to see whether you can do better.
So the basic method is to start with a completely 'open' window [-INF, INF] in the root, and pass this in the recursive search call to the deeper plies. Each ply will shrink the window by pushing one of its bounds to the score of the best move it found so far ('raising alpha').