TT management ?

[Chessnut1071]

What was the complete solution presented for the puzzle?

Checkmate in 9 moves! - Chess Forums - Chess.com
1. e5 c7
2. exd6 kd7
3. Qb7+ Ke6
4. Rae1+ Kf5
5. Bxg5+ Kxg5
6. Qe7+ Rf6
7. Re5+ Kg6
8. Qe8* Kh6
9. h5# 1 - 0

I’m not sure how that got through visual screening.

whoops 1. e5 Kc7

Black's first two moves in the above are inferior.
1...d5 is by far the best reply. Black is still lost, but a forced mate is much farther away.
Also 2...Kc8 holds off the mate at least three moves longer than 2...Kd7. In other words, 2...Kd7 leads to Mate in 7, but 2...Kc8 is at least a Mate in 10.

JVM ? 4 U
how long did it take your engine to prove there was no 9-move mate? My engine took an embarrassing 7:58:01 [hh/mm/ss] checking every possible move. If your engine found that in under an hour, I'd like to know how you did it.

[JVMerlino]

how long did it take your engine to prove there was no 9-move mate? My engine took an embarrassing 7:58:01 [hh/mm/ss] checking every possible move. If your engine found that in under an hour, I'd like to know how you did it.

My engine does not have a mate-solving mode. I used two programs to confirm this:
1) Chessmaster 9000 has a mate-solving feature, and The King took 4 minutes and 10 seconds to prove there was no mate in 9.
2) ChestUCI took 1 minute and 40 seconds.

Both of them use various tricks to reduce the search space, but I have no idea what they are. As far as I'm aware, the code for ChestUCI is open source. So I suggest you look there for ideas.

[Chessnut1071]

how long did it take your engine to prove there was no 9-move mate? My engine took an embarrassing 7:58:01 [hh/mm/ss] checking every possible move. If your engine found that in under an hour, I'd like to know how you did it.

My engine does not have a mate-solving mode. I used two programs to confirm this:
1) Chessmaster 9000 has a mate-solving feature, and The King took 4 minutes and 10 seconds to prove there was no mate in 9.
2) ChestUCI took 1 minute and 40 seconds.

Both of them use various tricks to reduce the search space, but I have no idea what they are. As far as I'm aware, the code for ChestUCI is open source. So I suggest you look there for ideas.

That's the problem "tricks." Unless they do an exhaustive search there's no way prove they just didn't give up when their algorithm didn't find it-ego-Chessmaster 9000. thx for the reply. I'm pretty sure now my engine will find the mate if it exists; however, it's the time that worries me.

[Ras]

how long did it take your engine to prove there was no 9-move mate? My engine took an embarrassing 7:58:01 [hh/mm/ss] checking every possible move. If your engine found that in under an hour, I'd like to know how you did it.

My CT800 engine has a dedicated mate solver with some tricks to find a mate if there is one - but if there is none, it amounts to full search with alpha-beta reduction only, i.e. no unsafe pruning. For "go mate 9", it took ~19 minutes (single threaded on Ryzen 5700G) to show that there is no mate in 9:

Code: Select all

info depth 17 seldepth 17 score cp 0 time 1115307 nodes 1417257052 nps 1270732
info string error (no mate found)
bestmove 0000

With "go mate 10", showing that there is no mate in 10 either, it took 10:40 hours:

Code: Select all

info depth 19 seldepth 19 score cp 0 time 38431488 nodes 53708569986 nps 1397514
info string error (no mate found)
bestmove 0000

The trick is modified move sorting: rank checks highest, then MVV/LVA, then history. Also, drop any move that does not deliver check in the last depth level because without check, it cannot be a checkmate. Any end position without check (or with check, but no checkmate) is scored as draw because homogenous scores help with beta-pruning, and hash tables are used only for such draw positions (which is nearly every position).

For positions that do have a solution, there is another trick: restrict the moves of the attacking side to check-giving moves because mate problems often involve a series of checks. First in all depth levels, then non-checks at exactly one depth level (iterating that through all depth levels), and then increasing from the deepest level onwards. Means, allow non-checks in the last-but one and the one before, then also in the level before that, and so on. The defending side ofc always has all moves.

What takes long if there is no solution is the last iteration with all moves for both sides except the last depth level of the attacking side that must be a check.

[Joerg Oster]

how long did it take your engine to prove there was no 9-move mate? My engine took an embarrassing 7:58:01 [hh/mm/ss] checking every possible move. If your engine found that in under an hour, I'd like to know how you did it.

My CT800 engine has a dedicated mate solver with some tricks to find a mate if there is one - but if there is none, it amounts to full search with alpha-beta reduction only, i.e. no unsafe pruning. For "go mate 9", it took ~19 minutes (single threaded on Ryzen 5700G) to show that there is no mate in 9:

Code: Select all

info depth 17 seldepth 17 score cp 0 time 1115307 nodes 1417257052 nps 1270732
info string error (no mate found)
bestmove 0000

With "go mate 10", showing that there is no mate in 10 either, it took 10:40 hours:

Code: Select all

info depth 19 seldepth 19 score cp 0 time 38431488 nodes 53708569986 nps 1397514
info string error (no mate found)
bestmove 0000

The trick is modified move sorting: rank checks highest, then MVV/LVA, then history. Also, drop any move that does not deliver check in the last depth level because without check, it cannot be a checkmate. Any end position without check (or with check, but no checkmate) is scored as draw because homogenous scores help with beta-pruning, and hash tables are used only for such draw positions (which is nearly every position).

For positions that do have a solution, there is another trick: restrict the moves of the attacking side to check-giving moves because mate problems often involve a series of checks. First in all depth levels, then non-checks at exactly one depth level (iterating that through all depth levels), and then increasing from the deepest level onwards. Means, allow non-checks in the last-but one and the one before, then also in the level before that, and so on. The defending side ofc always has all moves.

What takes long if there is no solution is the last iteration with all moves for both sides except the last depth level of the attacking side that must be a check.

My current Matefish dev takes about 19 min as well (single-threaded).
Yet it searches much more nodes than CT800.

Code: Select all

info depth 17 seldepth 17 multipv 1 score cp 0 nodes 2405743233 nps 2073062 tbhits 0 time 1160478 pv f3c3
bestmove f3c3

However, I don't have a TT implemented and no history tables.
Checks are also ranked highest, captures by MVV only, LVA didn't help.
I already give knight checks a small bonus.
Next I will test bonuses for rook/queen contact checks.
At the root, I also give a bonus for move(s) which restrict the opponent's king mobility most.

I will definitely try the check-restricting trick for all depth levels. Thank you for this hint.

[hgm]

I agree that scoring all non-mate positions the same would optimally prove there is no mate at a given depth. But I doubt it would be optimal for finding a mate if there is one. You could not benefit from iterative deepening, for instance, if any move is as good as any other before you have the depth needed to see the mate.

[Chessnut1071]

I agree that scoring all non-mate positions the same would optimally prove there is no mate at a given depth. But I doubt it would be optimal for finding a mate if there is one. You could not benefit from iterative deepening, for instance, if any move is as good as any other before you have the depth needed to see the mate.

This is a perfect application for a multi-core processor with zero-pruning on the main thread and "tsume" on an alternate core. I can think of 3 other useful evaluations to run parallel. Question: say you have a 2.6 GHz processor with 4 cores. How much of that 2.6GHz does it split between the cores, or, do they all get 2.6 GHz? I'm not that familiar with multi=core apps yet.

[Joerg Oster]

I agree that scoring all non-mate positions the same would optimally prove there is no mate at a given depth. But I doubt it would be optimal for finding a mate if there is one. You could not benefit from iterative deepening, for instance, if any move is as good as any other before you have the depth needed to see the mate.

That's also what I'm actually doing in Matefish.
So I start the search with a root depth of 1, and increment by 2 per iteration.
The purpose is to make sure there is no shorter mate than the one requested.

There is another reason, though.
Not all GUIs support to search for a specified mate limit.
Does Winboard/Xboard offer this feature?
The Fritz GUI seem to only support this for their own mate engine.
Arena has this implemented afaik, not sure about BanksiaGUI or ShredderGUI or Scid or ScidvsPC or others ...

Users thus often simply start an infinite analysis, and the engine
will have no info about the requested mate length.

[hgm]

They all run at 2.6GHz. But you should distinguish cores and Hyper Threads; one core as 2 HT, and these divide the capacity of the core. So that they would run at 1.3GHz if their partner HT is fully loaded.

The problem with your approach of having one tsume thread is that it would find the mate even if there is a single non-checking move in the solution. A check extension is much more flexible; the more non-checks the larger the nominal depth needs to be to find the solution, but eventually it will always find it.

[Chessnut1071]

They all run at 2.6GHz. But you should distinguish cores and Hyper Threads; one core as 2 HT, and these divide the capacity of the core. So that they would run at 1.3GHz if their partner HT is fully loaded.

The problem with your approach of having one tsume thread is that it would find the mate even if there is a single non-checking move in the solution. A check extension is much more flexible; the more non-checks the larger the nominal depth needs to be to find the solution, but eventually it will always find it.

Not sure we're talking about the same thing. You can write a specific function for single ply extension for check; however, simply placing a high weight on check in the evaluation function does exactly the same thing in checkmate solutions. It's almost as fast as extension and simpler to code. When there's plys with no checks it's just as fast.