Problems with this position

[Kempelen]

Well I continue with the problems. I have disabled all features except for pure alpha-beta, TT and a simple eval of material+PST.And so on the searh does not find promotion.

Code: Select all

 1    112      0        18 1. e4
 2    107      0        30 1. e4 Kd7
 3    112      0        74 1. e4 Kd7 2. Kd2
 4     97      0       201 1. e4 Kd7 2. Kd2 Kc6
 5    112      0       438 1. e4 Kd7 2. Kd2 Kc6 3. Kc3
 6     97      0      1174 1. e4 Kd7 2. Kd2 Kd6 3. Kc3 Ke5
 6    105      0      1632 1. Kd2 Kd7 2. Kc3 Kd6 3. Kd4 Kc6
 7    127      0      3218 1. Kd2 Kd7 2. Kc3 Kd6 3. Kd4 Kc6 4. e4
 8    127      0      8073 1. Kd2 Kd7 2. Kc3 Kc6 3. Kd4 Kb5 4. e4 Kc6
 9    131      1     18690 1. Kd2 Kd7 2. Kc3 Kc6 3. Kd4 Kd6 4. e4 Kc6 5. e5
10    131      3     45046 1. Kd2 Kd7 2. Kc3 Kc6 3. Kd4 Kd6 4. e4 Ke6 5. e5 Kf5

11    131      7     98634 1. Kd2 Kd7 2. e4 Kc6 3. Kc3 Kd6 4. Kd4 Ke6 5. e5 Kf5
6. Kd5
12    131     15    219006 1. Kd2 Kd7 2. e4 Kc6 3. Kc3 Kc5 4. Kd3 Kc6 5. Kd4 Kd6
 6. e5+ Ke6 7. Ke4
13    131     39    533302 1. Kd2 Kd7 2. e4 Kc6 3. Kc3 Kc5 4. Kd3 Kd6 5. Kd4 Ke6
 6. e5 Kf5 7. Kd5
14    125    125   1739152 1. Kd2 Ke7 2. Kc3 Kf6 3. Kd4 Ke6 4. e4 Kd6 5. e5+ Ke6
 6. Ke4 Kf7
15    131    300   4051615 1. Kd2 Ke7 2. e4 Kd7 3. Kc3 Ke6 4. Kd4 Kd6 5. e5+
16    131    859  10308918 1. Kd2 Ke7 2. e4 Kd7 3. Kc3 Kc6 4. Kd3 Kc5 5. Ke3 Kc6
 6. e5 Kd5 7. Kf4 Kc6 8. Ke4 Kc5
17    131   2039  23763949 1. Kd2 Ke7 2. e4 Kd7 3. Kc3 Kc6 4. Kd4 Kd6 5. e5+ Ke6
 6. Ke4 Ke7 7. Kd5 Kf7 8. Kd6 Kg6 9. Ke6 Kg5
18    131   7942  97059015 1. Kd2 Ke7 2. e4 Ke6 3. Kc3 Kd6 4. Kc4 Kc6 5. e5 Kd7
6. Kc3 Ke6 7. Kd4 Ke7 8. Kd5 Kf7 9. Ke4 Ke6
19    131  13187 162043307 1. Kd2 Ke7 2. e4 Ke6 3. Kc3 Kd6 4. Kc2 Ke5 5. Kd3 Ke6
 6. Kd4 Ke7 7. e5 Kd7 8. Kd5 Ke7 9. Ke4 Ke6 10. Kd4
20    127  31062 384308317 1. Kd2 Ke7 2. e4 Ke6 3. Kc3 Ke7 4. Kd3 Kf6 5. Ke3 Ke5
 6. Kf3 Ke6 7. Kf4 Kd6 8. Kf5 Kc6 9. Ke6 Kc5 10. Ke5 Kc6
21    131  70475 852645048 1. Kd2 Ke7 2. Kd3 Ke6 3. Ke4 Kf6 4. Kd5 Kf7 5. Kd6 Kf
6 6. e4 Kf7 7. e5 Ke8 8. Kc6 Kd8 9. Kc5 Kd7 10. Kc4 Ke6 11. Kd4

What is strange is that even with features on it does not find anything.

Ke8, Ke5, Pe4 find the solution very fast
Ke8, Ke4, Pe3 find the solution in 19 sec.
Ke8, Ke3, Pe2 find the solution in 269 sec.

I get around 11% hash_hits. I have seen one of you with 99% (Matt) and other with 8% (Paul). What's the usual?
What I have see is my tree is busher than others and maybe that's the reason why I dont find solutions
Something strange, but it find solutions with many time, also I get 2400 in CCRL, what point to a very specific problem.
I am a little tired about this.

[rvida]

Critter has some problems here too, although I'm not sure how bad it is. At ply 23 it found something but after 2x fail-high it returns with original score (??). At ply 24 it clearly sees the promotion though.

Code: Select all

setboard 4k3/8/8/8/8/8/4P3/4K3 w
go
 2  00:00         7       0 +1.21  e2e4 Ke8d7
 3  00:00        39       0 +1.54  e2e4 Ke8d7 e4e5
 4  00:00       144       0 +1.48  e2e4 Ke8d7 e4e5 Kd7e6
 5  00:00       390       0 +1.25  e2e4 Ke8d7 Ke1e2 Kd7e6 Ke2e3
 6  00:00       875       0 +1.19  e2e4 Ke8d7 Ke1e2 Kd7e6 Ke2e3 Ke6e5
 7  00:00      1774       0 +1.09  e2e4 Ke8d7 Ke1e2 Kd7e6 Ke2e3 Ke6e5 Ke3d3
 7  00:00      2467       0 +1.41  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6d6 e2e4
 8  00:00      3568       0 +1.51  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6d6 e2e4 Kd6e6
 9  00:00      5820       0 +1.84  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6d6 e2e4 Kd6e6 e4e5
10  00:00      8546       0 +1.84  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6f5 e2e4 Kf5e6 e4e5 Ke6f5 Kd4d5
11  00:00     12499       0 +1.94  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6f5 e2e4 Kf5e6 e4e5 Ke6f5 Kd4d5 Kf5f4
12  00:00     18337       0 +2.18  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6f5 e2e4 Kf5e6 e4e5 Ke6f5 Kd4d5 Kf5f4 e5e6
13  00:00     32988 2199200 +2.14  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6f5 e2e4 Kf5e6 e4e5 Ke6e7 Kd4d5 Ke7f7 e5e6 Kf7f6 Kd5d6
14  00:00     43425 2895000 +2.14  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3d4 Ke6f5 e2e4 Kf5e6 e4e5 Ke6d7 Kd4d5 Kd7e7 e5e6 Ke7f6 Kd5d6
15  00:00     89400 1943478 +2.18  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7c6 e2e4 Kc6d6 e4e5 Kd6e6 Kf4e4 Ke6f7 Ke4d5 Kf7g7 Kd5d4 Kg7f7
16  00:00    119324 1956131 +2.44  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7c6 e2e4 Kc6d6 Kf4f5 Kd6d7 e4e5 Kd7c7 e5e6 Kc7d8 Kf5e5 Kd8e7
17  00:00    142547 1827525 +2.48  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7c6 e2e4 Kc6d6 Kf4f5 Kd6d7 e4e5 Kd7e7 e5e6 Ke7e8 Kf5f6 Ke8d8 Kf6e5
18  00:00    176121 1893774 +2.48  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7c6 e2e4 Kc6d6 e4e5 Kd6d7 Kf4f5 Kd7e7 e5e6 Ke7e8 Kf5f6 Ke8f8 Kf6e5 Kf8e8 Ke5e4
19  00:00    217566 1754564 +2.48  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7c6 e2e4 Kc6d6 e4e5 Kd6d7 Kf4f3 Kd7e6 Kf3e4 Ke6e7 Ke4f5 Ke7f7 e5e6 Kf7e7 Kf5e5 Ke7e8 Ke5e4
20  00:00    269877 1729980 +2.48  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7c6 e2e4 Kc6d6 e4e5 Kd6d7 Kf4f3 Kd7e6 Kf3e4 Ke6e7 Ke4d5 Ke7f7 Kd5d4 Kf7e8 e5e6 Ke8d8 Kd4d5
21  00:00    376667 1727830 +2.48  Ke1d2 Ke8d7 Kd2e3 Kd7c7 Ke3f4 Kc7d6 e2e4 Kd6e6 e4e5 Ke6e7 Kf4e4 Ke7e8 Ke4d4 Ke8d7 Kd4d5 Kd7e7 e5e6 Ke7e8 Kd5d4 Ke8d8 Kd4d5
22  00:00    563833 1812967 +2.48  Ke1d2 Ke8d8 Kd2d3 Kd8d7 Kd3d4 Kd7d6 e2e4 Kd6e6 e4e5 Ke6e7 Kd4d5 Ke7d7 e5e6 Kd7e7 Kd5e5 Ke7e8 Ke5e4 Ke8d8 Ke4f4 Kd8e7 Kf4f5 Ke7e8 Kf5e5
23+ 00:00    661204 1841793 +2.89  Ke1d2
23+ 00:00    859553 1836651 +5.11  Ke1d2
23  00:01   2227369 1760766 +2.48  Ke1d2 Ke8d8 Kd2d3 Kd8d7 Kd3d4 Kd7d6 e2e4 Kd6e6 e4e5 Ke6e7 Kd4e4 Ke7e8 Ke4f5 Ke8e7 e5e6 Ke7e8 Kf5f6 Ke8f8 Kf6e5 Kf8e7 Ke5d5 Ke7e8 Kd5e5
24+ 00:01   2257676 1763809 +2.89  Ke1d2
24+ 00:01   2265522 1769939 +5.11  Ke1d2
24+ 00:01   2515916 1752030 +7.17  Ke1d2
24  00:03   5750211 1696727 +11.25  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3e4 Ke6e7 Ke4e5 Ke7e8 Ke5e6 Ke8d8 e2e4 Kd8c8 e4e5 Kc8c7 Ke6f7 Kc7c6 e5e6 Kc6c5 e6e7 Kc5c4 e7e8=Q Kc4d3 Qe8e5 Kd3d2 Kf7e6
25  00:05   9244191 1690907 +11.44  Ke1d2 Ke8d7 Kd2d3 Kd7e6 Kd3e4 Ke6e7 Ke4e5 Ke7e8 Ke5f6 Ke8f8 e2e4 Kf8g8 e4e5 Kg8f8 e5e6 Kf8e8 e6e7 Ke8d7 Kf6f7 Kd7c7 e7e8=Q Kc7b6 Qe8e5 Kb6b7 Kf7e6 Kb7c6
bestmove e1d2

time: 9859 nodes: 16502437 qnodes: 8295594 fh: 78.58%
extchk: 855841 ext1rep: 763 extpawn: 170341 evals: 0
tt.hit: 97.32% tt.exact: 0.57% tt.alpha: 7.67% tt.beta: 41.70%

[Desperado]

Hi again,

try this...

PENALTY the king the lower the rank distance between king and pawn is:

ex: king rank e2 pawn e4 -> -2 rank
if king is 1,2,3 in front penalty should switch to bonus!

important. weight this feature higher then pushing the passed pawn...

good luck again

[Desperado]

this little pseudo code is doing the job, also with selective search exceptionally nullm-prun.(used this for startup-evaluation for my last engine)

bdi is just the board-distance (squaredistance).
(this may be improved of course, but is simple and works...

Code: Select all

	 if(winner==WHITE)
		{
		 pwn = bsf64(brd->bb[wp12]);

		 //BAD RANK
		 //--------------------------------------

		 if&#40;RNK&#40;brd->pwk&#41; <= RNK&#40;pwn&#41;) PENALTY_WHITE&#40;score,&#40;RNK&#40;pwn&#41;-RNK&#40;brd->pwk&#41;)*50&#41;;

		 //GUIDE KING
		 //--------------------------------------

		 if&#40;FLE&#40;pwn&#41;==AF&#41;
			&#123;
			 PENALTY_WHITE&#40;score,bdi&#91;b7&#93;&#91;brd->pwk&#93;);
			 PENALTY_BLACK&#40;score,bdi&#91;b7&#93;&#91;brd->pbk&#93;*10&#41;;
			 PENALTY_BLACK&#40;score,bdi&#91;pwn+8&#93;&#91;brd->pbk&#93;*5&#41;;
			&#125;
		 else if&#40;FLE&#40;pwn&#41;==HF&#41;
			&#123;
			 PENALTY_WHITE&#40;score,bdi&#91;g7&#93;&#91;brd->pwk&#93;);
			 PENALTY_BLACK&#40;score,bdi&#91;g7&#93;&#91;brd->pbk&#93;*10&#41;;
			 PENALTY_BLACK&#40;score,bdi&#91;pwn+8&#93;&#91;brd->pbk&#93;*5&#41;;
			&#125;
		 else
			&#123;
			 if&#40;RNK&#40;pwn&#41;==R7&#41;
				&#123;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+9&#93;&#91;brd->pwk&#93;*5&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+7&#93;&#91;brd->pwk&#93;*5&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+1&#93;&#91;brd->pwk&#93;*5&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn-1&#93;&#91;brd->pwk&#93;*5&#41;;
				 PENALTY_BLACK&#40;score,bdi&#91;pwn+8&#93;&#91;brd->pbk&#93;*5&#41;;
				&#125;
			 else
				&#123;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+16&#93;&#91;brd->pwk&#93;*8&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+15&#93;&#91;brd->pwk&#93;*7&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+17&#93;&#91;brd->pwk&#93;*7&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+ 8&#93;&#91;brd->pwk&#93;*6&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+ 9&#93;&#91;brd->pwk&#93;*5&#41;;
				 PENALTY_WHITE&#40;score,bdi&#91;pwn+ 7&#93;&#91;brd->pwk&#93;*5&#41;;

				 PENALTY_BLACK&#40;score,bdi&#91;pwn+16&#93;&#91;brd->pbk&#93;*10&#41;;
				 PENALTY_BLACK&#40;score,bdi&#91;pwn+ 8&#93;&#91;brd->pbk&#93;* 5&#41;;
				&#125;
			&#125;
		&#125;

Neue Partie - Desperado SP32 0.1
4k3/8/8/8/8/8/4P3/4K3 w - - 0 1

Analysis by Desperado SP32 0.1 :

1.Kd2 Kd8 2.Ke3 Ke7 3.Ke4 Ke6 4.e3 Kf6 5.Kd5 Ke7 6.Ke5 Kd7 7.Kf6 Ke8 8.e4 Kd7 9.e5 Kc6 10.Ke6 Kc7 11.Kf7 Kc6 12.e6 Kd6 13.e7 Kd7 14.e8D+
+- (9.28) Tiefe: 26/30 00:00:11 10000kN
(Hoffmann, privat 30.05.2009)

[MattieShoes]

I'm counting hash hits as "hash table contains this zobrist key", not an actual cutoff. I don't know if others use the term differently. My hash transposition cutoffs are closer to 60%.

I have some futility pruning on as well as check extensions, but disabling them actually sped it up for this position. Hash hits are about the same, approaching 100%. Logically hash hits should be through the roof -- with the limited move options of kings and pawn each move, there are transpositions all over the place.

Branching factor with reasonable move ordering and hash cutoffs is below 2 at 20 ply. The tree should be quite slim. I think your problems are all related to the hash table though. Hash contains your best move, so if you aren't getting hash hits with best moves, perhaps you spend more time wandering down bad lines, branching factor goes up.

[rjgibert]

I found this position searching in the forum.

[D]4k3/8/8/8/8/8/4P3/4K3 w

It was posted in a thread about testing transposition table. OK I said, let's test it. What I found is that my engine does not find the solution even TT working fine. Then I give the position to other engines which I know TT work apparently fine. The conclusion is that there were engines which dont found the solution even in 30 depth or even passes 2 minutes:

I.e, Buzz engine:

Code: Select all

31 169 2268 12551036 Kd2 Kd7 Kd3 Kd6 Kd4 Ke6 Ke4 Ke7 Ke5 Kf7 Kd6 Kf6 e4 Kg5 e5 K
f4 e6 Ke3 Kd5 Kd3 Ke5 Kc4 Ke4 Kb3 Kd4 Ka2 Kd3 Ka3 Ke4 Kb3
31 169 2270 12557132 Kd2 Kd7 Kd3 Kd6 Kd4 Ke6 Ke4 Ke7 Ke5 Kf7 Kd6 Kf6 e4 Kg5 e5 K
f4 e6 Ke3 Kd5 Kd3 Ke5 Kc4 Ke4 Kb3 Kd4 Ka2 Kd3 Ka3 Ke4 Kb3

i.e2, Mizar:

Code: Select all

19 238 176 1560515 e1d2 e8e7 d2e3 e7d7 e3f4 d7e7 f4f5 e7f7 e2e4 f7e7 e4e5 e7f7 e
5e6 f7e8 f5f4 e8f8 f4e4 f8e8 e4e5 e8f8
20 238 198 1771848 e1d2 e8e7 d2e3 e7d7 e3f4 d7e7 f4f5 e7f7 e2e4 f7e7 e4e5 e7f8 e
5e6 f8e7 f5e5 e7f8 e5f6 f8e8 f6e5 e8f8

As I see, my search tend to fill with king moves or premature pawn push:

Code: Select all

19    197   1425   8622288 1. Kd2 Kd7 2. e4 Ke6 3. Kd3 Ke7 4. Ke3 Ke8 5. e5 Kf8
6. Kd4 Ke7 7. Kd5 Kd7 8. e6+ Kc7 9. Ke5 Kd8 10. Kf6 Kc7
20    197   2571  15915625 1. Kd2 Kd7 2. e4 Ke6 3. Kd3 Ke7 4. Ke3 Ke8 5. e5 Kf8
6. Kd4 Ke7 7. Kd5 Kd7 8. e6+ Ke7 9. Ke5 Ke8 10. Ke4 Kf8 11. Kd5

Of course, I add pawn passed bonus, pawn position bonus and all those things...

What is exactly needed here to correctly find the solution, a part from a correct TT implementation?

You should be able to see a queen very quickly. A simple piece of chess knowledge can help, but it is not necessary.

The simple rule for king and pawn vs king, pawn not a rookpawn, is that if the winning king is 2 squares in front of the pawn, and the pawn can't be taken by the opponent, then the position is won. If the king is one square in front of the pawn, the pawn can't be captured, and the winning king has the opposition, then the position is won.

If any of the above fail, the position is a draw. This position is trivially won since the king can reach a position that meets the above very quickly.

This is nowhere near being correct. I would guess that you are even misremembering what you have in crafty on this. For example, with the pawn on the 5th and your king one square in front of your pawn, it is a win with or without the opposition unless the pawn is a rook pawn. Another example, W: Kc5, Pf5; B: Kc7 wins with White to move. There are also all the square of the pawn winning positions, etc. There are many more examples.

[rjgibert]

You might also like to try W: Kd1, Pc3; B: Kf8 with White to move.

[hgm]

What is strange is that even with features on it does not find anything.

Note that it is not strange that you don't find the promotion at 21 ply. No one with specially encoded knowledge so far has reported it being found before 24 ply, and I suspect this is the theoretical minimum.

What is strange is the number of nodes to reach a certain depth. E.g. for 21 ply toy need 85M nodes. Micro-Max only needs 2M nodes to reach 21 ply. Micro-Max uses simple alpha-beta (no PVS), no killer or history heuristic, (so no move-ordering to speak off, just hash move, and then the remaining moves in move-generator order, even not bothering to prevent searching the hash move a second time), and an always-replace hash table.

There simply must be something wrong with your hash table.

[Kempelen]

What is strange is the number of nodes to reach a certain depth. E.g. for 21 ply toy need 85M nodes.

Yes, it is very strange, but more strange is the type of nodes which are stored in TT. With PVS and Aspiration (16depth):

Code: Select all

Empty entries: 4193033
Total entries: 4194303, Occupied: 1270 (0%)

Hash probes: 442953, Hash hits: 55447(12%)
H_EXACT:        3
H_ALPHA:      525
H_BETA :      742
With mov:      745

and without PVS and AW:

Code: Select all

Empty entries: 4190236
Total entries: 4194303, Occupied: 4067 (0%)

Hash probes: 5814659, Hash hits: 602191(10%)
H_EXACT:       61
H_ALPHA:     1545
H_BETA :     2461
With mov:     2479

As you can see, both has very few exact nodes. In first case, I have seen a lot of exact nodes are stored, but then they were replaced by upper or lower nodes. Do you think this means samething special? To me looks very strange to have so few exact nodes.

What I have seen is my TT work well (apparently), even I have 11% hash hits with means at lest there is not a major break,

[Desperado]

Well, perhaps the TT-mechanics are working well, but is the hashkey updated correctly, especially after the promotion ?

if this isnt the case i wouldnt be suprised that only about 4000 entries are used. Perhaps you can check this...