Checkmate evaluation functions

[Chessnut1071]

Fairy-Max 4.8 takes 2.29sec to settle on mate in 7 (i7 3.2GHz, single core):

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 17	    #7 	22.8M  	0:15.00	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2e1 g7g5 a4a6 b7b8 b4c6
 16	    #7 	14.6M  	0:09.95	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 15	    #7 	9.90M  	0:06.97	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 14	    #7 	6.93M  	0:05.07	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 13	    #7 	5.01M  	0:03.80	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 12	    #7 	3.56M  	0:02.79	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #7 	2.85M  	0:02.29	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #8 	2.58M  	0:02.10	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a4c6 b8c8 c6c7
 10	+11.57 	2.14M  	0:01.76	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a5c6 b8c8 a4a8 c8d7 a8h8
  9	+9.19 	1.01M  	0:00.84	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 h8c8 a4c6 a8b8 c6b6
  9	+9.10 	646678	0:00.54	a6f1 a8b7 c6b4 b7b8 a4a6 g1e3 f4e3 c7c5 a6b6 b8a8 b6a6 a8b8 d4c5
  8	+8.10 	428438	0:00.37	a6f1 a8b7 c6b4 b7b8 a4a6 g1f1 e1f1 h1g3 h2g3 e6e5 d4e5
  7	+5.95 	259062	0:00.23	a6f1 a8b7 c6b4 b7b8 a4a6 g1f2 a2f2 h1f2 e1f2
  6	+4.43 	120069	0:00.12	a6f1 a8b7 c6e7 b7b8 a2g2 g1g2 f1g2 c8e8 e7d5 e6d5 g2h1
  5	+3.45 	21191  	0:00.03	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  4	+3.45 	9862 	0:00.01	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  3	+0.97 	4301 	0:00.00	a6f1 a8b7 a4a6 b7c6 a2g2 g1g2 f1g2
  2	+0.14 	1122  	0:00.00	a6f1 a8b7 a2g2 b6b5 a4b5
  1	 -0.63 	158   	0:00.00	a6f1 a8b7 a2b2

That is with an evaluation that is little more than material and centralization. And a rudimentary move sorting that searches the hash move first, and then all other moves in move generation order.

Any public code on this?

Not in any Chess engine I know; for playing games it is not very useful. Unlike in Shogi, where it appears to be a worthwile method for finding very deep forced mates that one often has there, when there are many pieces in hand. I know SPEAR uses PNS for that, but I don't think that is public. But there must be other open-source Shogi programs.

Shogi is rather simple, all moves are check. I can usually find made in less than 2 or 3 seconds even at 22-ply with Shogi. However, I am at a loss on PNS or how it works. I can program anything if I knew how it works.

[hgm]

Well, Wikipedia provides a pretty compact description. The search is somewhat like MCTS: you build a tree in memory, initially only the root node, by adding nodes to it one by one. To decide where to add, you walk the tree from the root, selecting a daughter each time based on proof and disprrof numbers. This makes you end up in a leaf, which you then 'expand' by creating all daughters, and evaluating those (i.e. test whether they are mate or definitely exclude mate, or are still undecided). And then update the proof/disproof numbers along the path that led you to the former leaf by backpropagating those towards the root in the described way.

In your case 'proven' would mean checkmate within N moves, disproven would be "more than N moves played, and no checkmate yet". An AND node would be where the stm is checkmated, an OR node where he can force checkmate.

I am not claiming that PNS would solve the problems you have; I just noticed that some Shogi engines use it, and then come up with extremely deep mates. It seems a good method for positions with a few very much forced lines.

Given that very simplistic chess programs seem to be much faster at finding the checkmate in the position you posted by simple alpha-beta search, it seems there could be a lot to improve for you there too. It is like the complex algorithm you use to order moves only slows you down, as programs without any move ordering at all are a thousand times faster.

[Joerg Oster]

Fairy-Max 4.8 takes 2.29sec to settle on mate in 7 (i7 3.2GHz, single core):

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 17	    #7 	22.8M  	0:15.00	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2e1 g7g5 a4a6 b7b8 b4c6
 16	    #7 	14.6M  	0:09.95	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 15	    #7 	9.90M  	0:06.97	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 14	    #7 	6.93M  	0:05.07	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 13	    #7 	5.01M  	0:03.80	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 12	    #7 	3.56M  	0:02.79	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #7 	2.85M  	0:02.29	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #8 	2.58M  	0:02.10	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a4c6 b8c8 c6c7
 10	+11.57 	2.14M  	0:01.76	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a5c6 b8c8 a4a8 c8d7 a8h8
  9	+9.19 	1.01M  	0:00.84	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 h8c8 a4c6 a8b8 c6b6
  9	+9.10 	646678	0:00.54	a6f1 a8b7 c6b4 b7b8 a4a6 g1e3 f4e3 c7c5 a6b6 b8a8 b6a6 a8b8 d4c5
  8	+8.10 	428438	0:00.37	a6f1 a8b7 c6b4 b7b8 a4a6 g1f1 e1f1 h1g3 h2g3 e6e5 d4e5
  7	+5.95 	259062	0:00.23	a6f1 a8b7 c6b4 b7b8 a4a6 g1f2 a2f2 h1f2 e1f2
  6	+4.43 	120069	0:00.12	a6f1 a8b7 c6e7 b7b8 a2g2 g1g2 f1g2 c8e8 e7d5 e6d5 g2h1
  5	+3.45 	21191  	0:00.03	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  4	+3.45 	9862 	0:00.01	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  3	+0.97 	4301 	0:00.00	a6f1 a8b7 a4a6 b7c6 a2g2 g1g2 f1g2
  2	+0.14 	1122  	0:00.00	a6f1 a8b7 a2g2 b6b5 a4b5
  1	 -0.63 	158   	0:00.00	a6f1 a8b7 a2b2

That is with an evaluation that is little more than material and centralization. And a rudimentary move sorting that searches the hash move first, and then all other moves in move generation order.

Any public code on this?

Not in any Chess engine I know; for playing games it is not very useful. Unlike in Shogi, where it appears to be a worthwile method for finding very deep forced mates that one often has there, when there are many pieces in hand. I know SPEAR uses PNS for that, but I don't think that is public. But there must be other open-source Shogi programs.

Shogi is rather simple, all moves are check. I can usually find made in less than 2 or 3 seconds even at 22-ply with Shogi. However, I am at a loss on PNS or how it works. I can program anything if I knew how it works.

This is the link to the entry at chessprogramming: https://www.chessprogramming.org/Proof-Number_Search
There you can find a link to his publication "Searching for Solutions in Games and Artificial Intelligence".

[Joerg Oster]

Well, Wikipedia provides a pretty compact description. The search is somewhat like MCTS: you build a tree in memory, initially only the root node, by adding nodes to it one by one. To decide where to add, you walk the tree from the root, selecting a daughter each time based on proof and disprrof numbers. This makes you end up in a leaf, which you then 'expand' by creating all daughters, and evaluating those (i.e. test whether they are mate or definitely exclude mate, or are still undecided). And then update the proof/disproof numbers along the path that led you to the former leaf by backpropagating those towards the root in the described way.

In your case 'proven' would mean checkmate within N moves, disproven would be "more than N moves played, and no checkmate yet". An AND node would be where the stm is checkmated, an OR node where he can force checkmate.

I am not claiming that PNS would solve the problems you have; I just noticed that some Shogi engines use it, and then come up with extremely deep mates. It seems a good method for positions with a few very much forced lines.

Given that very simplistic chess programs seem to be much faster at finding the checkmate in the position you posted by simple alpha-beta search, it seems there could be a lot to improve for you there too. It is like the complex algorithm you use to order moves only slows you down, as programs without any move ordering at all are a thousand times faster.

I tried to put something together but there still seems to be some quirks.

For example

Code: Select all

position fen 8/8/8/5B2/6QN/3prp2/3r1p2/3bbk1K w - - 0 1
go mate 6
Root move h4g2   PN: 16   DN: 1
Root move h4f3   PN: 17   DN: 1
Root move h4g6   PN: 16   DN: 75
Root move f5d3   PN: 17   DN: 48
Root move f5e4   PN: 16   DN: 85
Root move f5e6   PN: 19   DN: 47
Root move f5g6   PN: 16   DN: 48
Root move f5d7   PN: 23   DN: 44
Root move f5h7   PN: 16   DN: 49
Root move f5c8   PN: 23   DN: 41
Root move g4g1   PN: 10000000   DN: 0
Root move g4g2   PN: 22   DN: 2
Root move g4f3   PN: 16   DN: 1
Root move g4g3   PN: 18   DN: 79
Root move g4h3   PN: 0   DN: 10000000
Root move g4a4   PN: 15   DN: 1
Root move g4b4   PN: 15   DN: 1
Root move g4c4   PN: 15   DN: 1
Root move g4d4   PN: 15   DN: 1
Root move g4e4   PN: 19   DN: 27
Root move g4f4   PN: 15   DN: 1
Root move g4g5   PN: 15   DN: 1
Root move g4h5   PN: 15   DN: 1
Root move g4g6   PN: 15   DN: 1
Root move g4g7   PN: 15   DN: 1
Root move g4g8   PN: 15   DN: 1
Root move h1h2   PN: 15   DN: 1
info depth 11 seldepth 11 multipv 1 score mate 6 nodes 9531 nps 1588500 tbhits 0 time 6 pv g4h3 f1e2 h3f1 e2f1 f5h3 f1e2 h3f1 e2f1 h4f5 d1c2 f5g3
bestmove g4h3 ponder f1e2

this mate in 6 looks ok.

But here

Code: Select all

position fen k1r2q2/ppp5/6Qp/2P5/B7/5n2/5P2/1R5K w - -
go mate 4
Root move c5c6   PN: 32   DN: 1
Root move a4d1   PN: 30   DN: 1
Root move a4c2   PN: 30   DN: 1
Root move a4b3   PN: 30   DN: 1
Root move a4b5   PN: 55   DN: 37
Root move a4c6   PN: 30   DN: 75
Root move a4d7   PN: 30   DN: 1
Root move a4e8   PN: 54   DN: 35
Root move b1a1   PN: 30   DN: 1
Root move b1c1   PN: 30   DN: 1
Root move b1d1   PN: 30   DN: 1
Root move b1e1   PN: 30   DN: 1
Root move b1f1   PN: 30   DN: 1
Root move b1g1   PN: 30   DN: 1
Root move b1b2   PN: 30   DN: 1
Root move b1b3   PN: 30   DN: 1
Root move b1b4   PN: 30   DN: 1
Root move b1b5   PN: 48   DN: 30
Root move b1b6   PN: 30   DN: 1
Root move b1b7   PN: 30   DN: 37
Root move g6g1   PN: 30   DN: 1
Root move g6c2   PN: 30   DN: 1
Root move g6g2   PN: 30   DN: 1
Root move g6d3   PN: 30   DN: 1
Root move g6g3   PN: 30   DN: 1
Root move g6e4   PN: 50   DN: 39
Root move g6g4   PN: 30   DN: 1
Root move g6f5   PN: 65   DN: 21
Root move g6g5   PN: 31   DN: 1
Root move g6h5   PN: 30   DN: 30
Root move g6a6   PN: 0   DN: 10000000
Root move g6b6   PN: 30   DN: 1
Root move g6c6   PN: 29   DN: 461
Root move g6d6   PN: 30   DN: 1
Root move g6e6   PN: 30   DN: 1
Root move g6f6   PN: 65   DN: 21
Root move g6h6   PN: 30   DN: 1
Root move g6f7   PN: 61   DN: 21
Root move g6g7   PN: 30   DN: 1
Root move g6h7   PN: 30   DN: 1
Root move g6e8   PN: 29   DN: 1
Root move g6g8   PN: 29   DN: 1
Root move h1g2   PN: 30   DN: 1
info depth 7 seldepth 7 multipv 1 score mate 2 nodes 10266 nps 1711000 tbhits 0 time 6 pv g6a6 h6h5 a6b7
bestmove g6a6 ponder h6h5

I get a mate in 2 instead of the correct mate in 4. (The correct response to Qg6-a6 is Rc8-b8 to avoid the mate on b7.)
So either the search is still buggy, or the way I collect the PV is wrong.

[Chessnut1071]

Well, Wikipedia provides a pretty compact description. The search is somewhat like MCTS: you build a tree in memory, initially only the root node, by adding nodes to it one by one. To decide where to add, you walk the tree from the root, selecting a daughter each time based on proof and disprrof numbers. This makes you end up in a leaf, which you then 'expand' by creating all daughters, and evaluating those (i.e. test whether they are mate or definitely exclude mate, or are still undecided). And then update the proof/disproof numbers along the path that led you to the former leaf by backpropagating those towards the root in the described way.

In your case 'proven' would mean checkmate within N moves, disproven would be "more than N moves played, and no checkmate yet". An AND node would be where the stm is checkmated, an OR node where he can force checkmate.

I am not claiming that PNS would solve the problems you have; I just noticed that some Shogi engines use it, and then come up with extremely deep mates. It seems a good method for positions with a few very much forced lines.

Given that very simplistic chess programs seem to be much faster at finding the checkmate in the position you posted by simple alpha-beta search, it seems there could be a lot to improve for you there too. It is like the complex algorithm you use to order moves only slows you down, as programs without any move ordering at all are a thousand times faster.

The time I referenced was for a 20-ply search, which Chess.com gave as a solution to the problem, When I did a generic optimized search on 14-ply with the same metrics I previously used, my solution 10,619,826 nodes for 14.96 seconds. There are approximately 10^15 movers for that 20-ply search.

I'm still far slower when I compare my 14-ply solution to other programs; however, without the ordering my solution time increases by a factor of 9.

I assume everyone uses alpha/beta and a TT. Previous move and history are generic and almost always useful, with very little computation time. Check is a forced move and maybe the most important metric, especially in late moves. Gain or loss of material is vital in some cases yet worthless in sacrificial line. Piece type is practically worthless in generic solutions. My other metrics, distance to enemy king, number of enemy king moves reduce solution time in most cases, but not a significant amount.

So, what gets thrown out? The most computational demanding is gain or loss of material.

I'm looking into PNS to learn it better, but, it may be my PEXT is less efficiently programmed. Compare my 10,619,826 nodes for the 14-ply solution and if it is similar to the other faster solutions it's probably an issue with my PEXT or my older i-7 chip.

btw, thanks for your correction to my TT, I'm up to 24-ply without issues.

[Chessnut1071]

Fairy-Max 4.8 takes 2.29sec to settle on mate in 7 (i7 3.2GHz, single core):

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 17	    #7 	22.8M  	0:15.00	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2e1 g7g5 a4a6 b7b8 b4c6
 16	    #7 	14.6M  	0:09.95	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 15	    #7 	9.90M  	0:06.97	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 14	    #7 	6.93M  	0:05.07	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 13	    #7 	5.01M  	0:03.80	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 12	    #7 	3.56M  	0:02.79	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #7 	2.85M  	0:02.29	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #8 	2.58M  	0:02.10	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a4c6 b8c8 c6c7
 10	+11.57 	2.14M  	0:01.76	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a5c6 b8c8 a4a8 c8d7 a8h8
  9	+9.19 	1.01M  	0:00.84	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 h8c8 a4c6 a8b8 c6b6
  9	+9.10 	646678	0:00.54	a6f1 a8b7 c6b4 b7b8 a4a6 g1e3 f4e3 c7c5 a6b6 b8a8 b6a6 a8b8 d4c5
  8	+8.10 	428438	0:00.37	a6f1 a8b7 c6b4 b7b8 a4a6 g1f1 e1f1 h1g3 h2g3 e6e5 d4e5
  7	+5.95 	259062	0:00.23	a6f1 a8b7 c6b4 b7b8 a4a6 g1f2 a2f2 h1f2 e1f2
  6	+4.43 	120069	0:00.12	a6f1 a8b7 c6e7 b7b8 a2g2 g1g2 f1g2 c8e8 e7d5 e6d5 g2h1
  5	+3.45 	21191  	0:00.03	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  4	+3.45 	9862 	0:00.01	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  3	+0.97 	4301 	0:00.00	a6f1 a8b7 a4a6 b7c6 a2g2 g1g2 f1g2
  2	+0.14 	1122  	0:00.00	a6f1 a8b7 a2g2 b6b5 a4b5
  1	 -0.63 	158   	0:00.00	a6f1 a8b7 a2b2

That is with an evaluation that is little more than material and centralization. And a rudimentary move sorting that searches the hash move first, and then all other moves in move generation order.

Any public code on this?

Not in any Chess engine I know; for playing games it is not very useful. Unlike in Shogi, where it appears to be a worthwile method for finding very deep forced mates that one often has there, when there are many pieces in hand. I know SPEAR uses PNS for that, but I don't think that is public. But there must be other open-source Shogi programs.

Shogi is rather simple, all moves are check. I can usually find made in less than 2 or 3 seconds even at 22-ply with Shogi. However, I am at a loss on PNS or how it works. I can program anything if I knew how it works.

This is the link to the entry at chessprogramming: https://www.chessprogramming.org/Proof-Number_Search
There you can find a link to his publication "Searching for Solutions in Games and Artificial Intelligence".

Thanks for the link. The time I referenced originally was for a 20-ply search, which Chess.com gave as a solution to the problem, When I did a generic optimized search on 14-ply with the same metrics I previously used, my solution 10,619,826 nodes for 14.96 seconds. i7 2.6 GHz 1 core 1 thread. It looks like Fairly-Max searches fewer nodes, 10.6M vs. 2.85 if I read that right.

[Dann Corbit]

Shogi is rather simple, all moves are check. I can usually find made in less than 2 or 3 seconds even at 22-ply with Shogi. However, I am at a loss on PNS or how it works. I can program anything if I knew how it works.

https://minimax.dev/docs/ultimate/pn-search/dfpn/
https://www.chessprogramming.org/Proof-Number_Search
https://proceedings.neurips.cc/paper_fi ... -Paper.pdf

[hgm]

I'm still far slower when I compare my 14-ply solution to other programs; however, without the ordering my solution time increases by a factor of 9.

I assume everyone uses alpha/beta and a TT. Previous move and history are generic and almost always useful, with very little computation time. Check is a forced move and maybe the most important metric, especially in late moves. Gain or loss of material is vital in some cases yet worthless in sacrificial line. Piece type is practically worthless in generic solutions. My other metrics, distance to enemy king, number of enemy king moves reduce solution time in most cases, but not a significant amount.

So, what gets thrown out? The most computational demanding is gain or loss of material.

I'm looking into PNS to learn it better, but, it may be my PEXT is less efficiently programmed. Compare my 10,619,826 nodes for the 14-ply solution and if it is similar to the other faster solutions it's probably an issue with my PEXT or my older i-7 chip.

Well, Fairy-Max is very inefficient: it uses a mailbox board without piece list, so it has to scan the entire board in each position to find its own pieces.

I think you are stuck because you expect miracles from move ordering by static criteria alone, and don't consider anything else. While the programs that find the mate quickly in fact do so not because of their move ordering (Fairy-Max practically has none...), but because of well-chosen extensions and reductions, and Internal Iterative Deepening to avoid wasting many nodes on unpromising lines that resulted from inperfect static ordering.

It is also strange that your 20-ply search would take very much longer than a 14-ply search for a position where there is mate in 7. It should have stumbled on that mate long before it completed the search, and after that no line should have been allowed to go deeper than 14 ply by mate-distance pruning. This is also an indication there is something wrong with your search algorithm.

[Joerg Oster]

Shogi is rather simple, all moves are check. I can usually find made in less than 2 or 3 seconds even at 22-ply with Shogi. However, I am at a loss on PNS or how it works. I can program anything if I knew how it works.

https://minimax.dev/docs/ultimate/pn-search/dfpn/
https://www.chessprogramming.org/Proof-Number_Search
https://proceedings.neurips.cc/paper_fi ... -Paper.pdf

Thank you for the links, Dann.
Never heard of IDA* before.

[Chessnut1071]

I'm still far slower when I compare my 14-ply solution to other programs; however, without the ordering my solution time increases by a factor of 9.

I assume everyone uses alpha/beta and a TT. Previous move and history are generic and almost always useful, with very little computation time. Check is a forced move and maybe the most important metric, especially in late moves. Gain or loss of material is vital in some cases yet worthless in sacrificial line. Piece type is practically worthless in generic solutions. My other metrics, distance to enemy king, number of enemy king moves reduce solution time in most cases, but not a significant amount.

So, what gets thrown out? The most computational demanding is gain or loss of material.

I'm looking into PNS to learn it better, but, it may be my PEXT is less efficiently programmed. Compare my 10,619,826 nodes for the 14-ply solution and if it is similar to the other faster solutions it's probably an issue with my PEXT or my older i-7 chip.

Well, Fairy-Max is very inefficient: it uses a mailbox board without piece list, so it has to scan the entire board in each position to find its own pieces.

I think you are stuck because you expect miracles from move ordering by static criteria alone, and don't consider anything else. While the programs that find the mate quickly in fact do so not because of their move ordering (Fairy-Max practically has none...), but because of well-chosen extensions and reductions, and Internal Iterative Deepening to avoid wasting many nodes on unpromising lines that resulted from inperfect static ordering.

It is also strange that your 20-ply search would take very much longer than a 14-ply search for a position where there is mate in 7. It should have stumbled on that mate long before it completed the search, and after that no line should have been allowed to go deeper than 14 ply by mate-distance pruning. This is also an indication there is something wrong with your search algorithm.

This is also an indication there is something wrong with your search algorithm.????

When Chess.com gave the solution as a 10-move mate, or 20-ply, I only looked at the 20-ply thread. With an average of 30 elements per ply that's an extra 730,000,000 branches. Although there is a 14-ply solution buried in that tree, it's going to take a lot longer to find it than if you only have to look at a 14-ply tree.

As far as reductions. I know you can significantly increase speed by ignoring unpromising lines; however, there are puzzles out there specifically written to befuddle computers, and unless your algorithm is perfect you'll never find it. Rather than throwing a line away, I sort it to the bottom of the list. Yes, it slows things down, but, if there is a mate I find it.

Interesting side objective: write a puzzle which are hard to solve by a compute; i.e., computer proof.