bob wrote:This is not so much about finding Kb1 as getting to depth 30. If you have optimal move ordering, this will take to depth 26 or so to find Kb1. If your move ordering is worse, then you will actually find it at a shallower depth due to search grafting. I can explain how if you are interested. But John now gets to depth 30 in 1 second or so which seems reasonable...
Ok, since Myrddin finds Rb1 at depth 21, I'm now very curious to know why this is possibly a bad thing.
Move ordering in Myrddin is, like the rest of the engine, fairly primitive. But it does use history and killers, plus has the normal move-type ordering:
PV move
Hash move
Capture (MVV/LVA), with killers after good captures and before bad captures
Checks
Quiet moves
jm
OK, here is how you find the solution.
I assume you have looked at the position and PV carefully and understand that with best play by both sides, this position requires 13 non-capturing/non-checking moves by each side, and on the 27th ply (first ply of q-search) white finally captures a pawn. I think this is covered in Newborn's book on computer chess where he talks about his endgame-specific program called "peasant"...
In 21 plies you can't possibly win a pawn, so how does the search see it?
Suppose your move ordering for black is really bad, so that at each ply white makes a good move and black makes a lousy move. By the time you get to (say) depth 19, which discovers it can win a pawn. But that is not so useful, since black gets opportunities at each ply to find better moves to improve it's score, right? But along comes the hash table and along that PV you store the result that says "if I can reach this position, I win a pawn". And while with best play by both sides, you can't force the win of a pawn, you will discover that with best play by both sides you _can_ reach one of those positions where you found you win a pawn if black had played poorly. You graft that score onto the current position. Suppose we are at ply=21 for white, and from this position it takes another 6 plies to win the pawn. With a depth=21 search, you can't see this. But if black played like a patzer, you might have reached this position at depth=12 and saw "aha, I win a pawn." Now with best play you force that position (that you saw at ply=12) to happen, and remember you were still doing a 21 ply search, so that you searched 9 plies further and spotted the pawn win. Now at depth=21, you forced the game to reach that position you previously encountered at depth=12, and use that hash entry. Which, by the way, has a "draft" of 9 plies don't forget. You graft that onto the current 21 ply search, and actually pull off a 30 ply search on iteration 21, and spot the win.
If you had not first searched lousy moves for black, then you would not know that position is won, and your 21 ply search would still show Kb2 as the best move and white simply a single pawn ahead, as in the starting position.
bob wrote:This is not so much about finding Kb1 as getting to depth 30. If you have optimal move ordering, this will take to depth 26 or so to find Kb1. If your move ordering is worse, then you will actually find it at a shallower depth due to search grafting. I can explain how if you are interested. But John now gets to depth 30 in 1 second or so which seems reasonable...
Ok, since Myrddin finds Rb1 at depth 21, I'm now very curious to know why this is possibly a bad thing.
Move ordering in Myrddin is, like the rest of the engine, fairly primitive. But it does use history and killers, plus has the normal move-type ordering:
PV move
Hash move
Capture (MVV/LVA), with killers after good captures and before bad captures
Checks
Quiet moves
jm
OK, here is how you find the solution.
I assume you have looked at the position and PV carefully and understand that with best play by both sides, this position requires 13 non-capturing/non-checking moves by each side, and on the 27th ply (first ply of q-search) white finally captures a pawn. I think this is covered in Newborn's book on computer chess where he talks about his endgame-specific program called "peasant"...
In 21 plies you can't possibly win a pawn, so how does the search see it?
Suppose your move ordering for black is really bad, so that at each ply white makes a good move and black makes a lousy move. By the time you get to (say) depth 19, which discovers it can win a pawn. But that is not so useful, since black gets opportunities at each ply to find better moves to improve it's score, right? But along comes the hash table and along that PV you store the result that says "if I can reach this position, I win a pawn". And while with best play by both sides, you can't force the win of a pawn, you will discover that with best play by both sides you _can_ reach one of those positions where you found you win a pawn if black had played poorly. You graft that score onto the current position. Suppose we are at ply=21 for white, and from this position it takes another 6 plies to win the pawn. With a depth=21 search, you can't see this. But if black played like a patzer, you might have reached this position at depth=12 and saw "aha, I win a pawn." Now with best play you force that position (that you saw at ply=12) to happen, and remember you were still doing a 21 ply search, so that you searched 9 plies further and spotted the pawn win. Now at depth=21, you forced the game to reach that position you previously encountered at depth=12, and use that hash entry. Which, by the way, has a "draft" of 9 plies don't forget. You graft that onto the current 21 ply search, and actually pull off a 30 ply search on iteration 21, and spot the win.
If you had not first searched lousy moves for black, then you would not know that position is won, and your 21 ply search would still show Kb2 as the best move and white simply a single pawn ahead, as in the starting position.
Ugly, but effective.
Bob
Ok, I understand that explanation. Thanks, Bob!
jm
The bad thing is, the worse your ordering sucks, the shallower the depth needed to solve problems like this. However, bad ordering hurts everything overall. So the plies go by slower, but for this particular type of position where transpositions are incredibly common (pawns are locked so nothing but king moves until white breaks thru and wins a pawn to open things up) you see the right answer at a shallower depth. But in a longer time.
Crafty finds this at depth=24, for example, but uses < 0.01 seconds to get there. Reductions hurt. Pruning hurts. But 24 plies in < 0.01 is way better than finding it at depth=18 but needing much more time...
The depth is irrelevant, only the time matters in chess...
bob wrote:This is not so much about finding Kb1 as getting to depth 30. If you have optimal move ordering, this will take to depth 26 or so to find Kb1. If your move ordering is worse, then you will actually find it at a shallower depth due to search grafting. I can explain how if you are interested. But John now gets to depth 30 in 1 second or so which seems reasonable...
Ok, since Myrddin finds Rb1 at depth 21, I'm now very curious to know why this is possibly a bad thing.
Move ordering in Myrddin is, like the rest of the engine, fairly primitive. But it does use history and killers, plus has the normal move-type ordering:
PV move
Hash move
Capture (MVV/LVA), with killers after good captures and before bad captures
Checks
Quiet moves
jm
OK, here is how you find the solution.
I assume you have looked at the position and PV carefully and understand that with best play by both sides, this position requires 13 non-capturing/non-checking moves by each side, and on the 27th ply (first ply of q-search) white finally captures a pawn. I think this is covered in Newborn's book on computer chess where he talks about his endgame-specific program called "peasant"...
In 21 plies you can't possibly win a pawn, so how does the search see it?
Suppose your move ordering for black is really bad, so that at each ply white makes a good move and black makes a lousy move. By the time you get to (say) depth 19, which discovers it can win a pawn. But that is not so useful, since black gets opportunities at each ply to find better moves to improve it's score, right? But along comes the hash table and along that PV you store the result that says "if I can reach this position, I win a pawn". And while with best play by both sides, you can't force the win of a pawn, you will discover that with best play by both sides you _can_ reach one of those positions where you found you win a pawn if black had played poorly. You graft that score onto the current position. Suppose we are at ply=21 for white, and from this position it takes another 6 plies to win the pawn. With a depth=21 search, you can't see this. But if black played like a patzer, you might have reached this position at depth=12 and saw "aha, I win a pawn." Now with best play you force that position (that you saw at ply=12) to happen, and remember you were still doing a 21 ply search, so that you searched 9 plies further and spotted the pawn win. Now at depth=21, you forced the game to reach that position you previously encountered at depth=12, and use that hash entry. Which, by the way, has a "draft" of 9 plies don't forget. You graft that onto the current 21 ply search, and actually pull off a 30 ply search on iteration 21, and spot the win.
If you had not first searched lousy moves for black, then you would not know that position is won, and your 21 ply search would still show Kb2 as the best move and white simply a single pawn ahead, as in the starting position.
Ugly, but effective.
Bob
Ok, I understand that explanation. Thanks, Bob!
jm
The bad thing is, the worse your ordering sucks, the shallower the depth needed to solve problems like this. However, bad ordering hurts everything overall. So the plies go by slower, but for this particular type of position where transpositions are incredibly common (pawns are locked so nothing but king moves until white breaks thru and wins a pawn to open things up) you see the right answer at a shallower depth. But in a longer time.
Crafty finds this at depth=24, for example, but uses < 0.01 seconds to get there. Reductions hurt. Pruning hurts. But 24 plies in < 0.01 is way better than finding it at depth=18 but needing much more time...
The depth is irrelevant, only the time matters in chess...
How many nodes is that? That will be easier to normalize the comparison.
My program sees Kb1 in 54k nodes (ply17). 100k nodes (ply23) if I use material only in eval (64Mb of hash, but I think it is very relevant since only 2.8% is filled).
Unlike Fine 70 (which is also a good test), the key move cannot be found by accident (i.e. it looks like a bad move unless you see the full line).
As an aside this position was used in the sales literature of the Fidelity Mach III back in ~1988. Basically, without a hash table it is almost impossible to find. Nowadays it's trivial. The good programs even see announce mate in 21.
Steve Maughan wrote:I like this position. The key move is c7
[d]2k5/8/1pP1K3/1P6/8/8/8/8 w - -
Unlike Fine 70 (which is also a good test), the key move cannot be found by accident (i.e. it looks like a bad move unless you see the full line).
As an aside this position was used in the sales literature of the Fidelity Mach III back in ~1988. Basically, without a hash table it is almost impossible to find. Nowadays it's trivial. The good programs even see announce mate in 21.
Steve
Yep, a good one. After turning off tablebases, of course, Myrddin gets this:
Steve Maughan wrote:I like this position. The key move is c7
[d]2k5/8/1pP1K3/1P6/8/8/8/8 w - -
Unlike Fine 70 (which is also a good test), the key move cannot be found by accident (i.e. it looks like a bad move unless you see the full line).
As an aside this position was used in the sales literature of the Fidelity Mach III back in ~1988. Basically, without a hash table it is almost impossible to find. Nowadays it's trivial. The good programs even see announce mate in 21.
Steve
Wow, took me 19 ply and about 5 minutes to find... Good test position, thanks!
Mark wrote:Wow, took me 19 ply and about 5 minutes to find... Good test position, thanks!
If your engine takes 19 ply and 5 minutes without hash then that is really quite good. If it has hash then I suspect there is a problem. On modern hardware the key move and win (score > 8 pawns) should be found in seconds if the hash is working correctly.
Mark wrote:Wow, took me 19 ply and about 5 minutes to find... Good test position, thanks!
If your engine takes 19 ply and 5 minutes without hash then that is really quite good. If it has hash then I suspect there is a problem. On modern hardware the key move and win (score > 8 pawns) should be found in seconds if the hash is working correctly.
Steve
Unfortunately, that was with hash (and null move off):
I currently don't have any draw by repetition detection and no quiese search (I just extend one ply on a capture or promotion). Maybe that has something to do with it?
It takes Fairy-Max less then half a second, on my 1.3GHz Celeron M with 48MB hash.
Fairy-Max has no rep-draw detection, only for positions that have occured in the game before, which are none in this case, since it was a virgin start. And should have switched null-move and LMR off in this position.
