Adding a mate searching thread to my engine

[Cardoso]

Hi,
I'm thinking on adding a mate searching thread to my checkers engine.
In checkers there is no mate but I'll use the word mate to speak the chess language.
With so much forward pruning going on in my engine some short wining lines are not detected until a very large nominal depth is reached. Just like some chess engines in the past going 30+ plies deep but failing to see mate in 10.
So at the tips of the search tree when I'm ready to return the eval (qsearch), and assuming the current position has valid moves, what should I return?
1 - zero
2 - alpha
3 - basic PST
I would appreciate your thoughts on this.
thanks,

Alvaro

[Chessnut1071]

Hi,
I'm thinking on adding a mate searching thread to my checkers engine.
In checkers there is no mate but I'll use the word mate to speak the chess language.
With so much forward pruning going on in my engine some short wining lines are not detected until a very large nominal depth is reached. Just like some chess engines in the past going 30+ plies deep but failing to see mate in 10.
So at the tips of the search tree when I'm ready to return the eval (qsearch), and assuming the current position has valid moves, what should I return?
1 - zero
2 - alpha
3 - basic PST
I would appreciate your thoughts on this.
thanks,

Alvaro

My objective is mate in minimum moves in minimum time. There are only 2 pruning variables, enemy king moves > 5 and checkmate. All others pruning variables fail at least once in simulations of 100,000 known checkmates. Bottom line, if you prune you will miss something. Also, using known checkmates verifies your engine's accuracy. There is a huge time penalty for this objective; however, when quantum computing becomes the norm, an optimized algorithm will become unbeatable.

[dangi12012]

Let me answer this straightforward:
Return 0 at the leafs.
Remove all pruning.

You will end up with pure alphabeta which should be around 7 lines of code and will find forced wins for you.

If that recursion returns a win it is a forced win IE mate in X


You can still do iterative deepening when the number of open paths remain low

[Chessnut1071]

Let me answer this straightforward:
Return 0 at the leafs.
Remove all pruning.

You will end up with pure alphabeta which should be around 7 lines of code and will find forced wins for you.

If that recursion returns a win it is a forced win IE mate in X


You can still do iterative deepening when the number of open paths remain low

]
AI tools, alpha/beta, Zobirst hash, evaluation function.
The evaluation function is the most critical requirement to speeding up the search. I found 7 significant variables which needs to be optimized using a nonlinear search.
1. single check, double check, discovered check
2. history by ply
3. captured piece type
4. pawn promotion
5. piece type moved
6 number of enemy king moves
7. ent passant

[abulmo2]

Hi,
I'm thinking on adding a mate searching thread to my checkers engine.
In checkers there is no mate but I'll use the word mate to speak the chess language.
With so much forward pruning going on in my engine some short wining lines are not detected until a very large nominal depth is reached. Just like some chess engines in the past going 30+ plies deep but failing to see mate in 10.
So at the tips of the search tree when I'm ready to return the eval (qsearch), and assuming the current position has valid moves, what should I return?
1 - zero
2 - alpha
3 - basic PST
I would appreciate your thoughts on this.
thanks,

Alvaro

I think you should return 3 - basic PST, or even the eval if it is not too slow. One problem is to remove the forward pruning to make the search not selective in the solving thread and to detect when the search is selective or not in the hash table.

[Cardoso]

Let me answer this straightforward:
Return 0 at the leafs.
Remove all pruning.

You will end up with pure alphabeta which should be around 7 lines of code and will find forced wins for you.

If that recursion returns a win it is a forced win IE mate in X


You can still do iterative deepening when the number of open paths remain low

So no heuristics that could possibly help?
About pruning, maybe the only pruning I can make safely is mate distance pruning. I'm going to test that.

[Joerg Oster]

Let me answer this straightforward:
Return 0 at the leafs.
Remove all pruning.

You will end up with pure alphabeta which should be around 7 lines of code and will find forced wins for you.

If that recursion returns a win it is a forced win IE mate in X


You can still do iterative deepening when the number of open paths remain low

You will end up with something able to solve mates in 4 or even up to mates in 7 in reasonable time.
Longer mates will take forever without additional pruning heuristics.

[Steve Maughan]

It's an interesting idea. Here's what I'd do:

Have one thread that is "tactical" and given search parameters alpha = (Mate - Max_Ply), beta = Mate i.e. in the mate range. Have it search normally with the standard pruning techniques. I suspect the hash table is where the magic comes in: don't store the results of this search unless the score is a mate score. Assuming you're using lazy SMP the other threads will then be guided by the hash table only if there is a mate to be found. Since you're only storing mate scores you won't clutter the hash table with irrelevant not-mate bounds.

I've no idea if it'll work but it's worth a try.

Steve

[dangi12012]

Let me answer this straightforward:
Return 0 at the leafs.
Remove all pruning.

You will end up with pure alphabeta which should be around 7 lines of code and will find forced wins for you.

If that recursion returns a win it is a forced win IE mate in X


You can still do iterative deepening when the number of open paths remain low

You will end up with something able to solve mates in 4 or even up to mates in 7 in reasonable time.
Longer mates will take forever without additional pruning heuristics.

Yes. Its the way to go for mate search.
Any pruning and you will lose otherwise found mates.

Its a simple also educational task since its a few lines of code. Should be quite beautiful

[Cardoso]

It's an interesting idea. Here's what I'd do:

Have one thread that is "tactical" and given search parameters alpha = (Mate - Max_Ply), beta = Mate i.e. in the mate range. Have it search normally with the standard pruning techniques. I suspect the hash table is where the magic comes in: don't store the results of this search unless the score is a mate score. Assuming you're using lazy SMP the other threads will then be guided by the hash table only if there is a mate to be found. Since you're only storing mate scores you won't clutter the hash table with irrelevant not-mate bounds.

I've no idea if it'll work but it's worth a try.

Steve

Well if I revisit an interior node one or more times, that takes a billion nodes to search I really wouldn't like to repeat the same search again for this subtree, so I have to use the hash table for non mating/mated positions also. What I could do is to give precedence for mating positions in the hash table replacing scheme. What do you think Steve?