In the endgame, many positions are hopeless draws which can almost be determined via static analysis, after a certain depth of conversion. For example. lets say we get down to K&R vs K&R. Unless one side has a K and R along the same file or column, apart a bit, the other side can only get a draw (in this example, a check of the king might force it to move, and one rook could eat another, or some nearly immediate mate). It seems safe to me to assume a draw in this case as long as you are X half moves from conversion. I do not have ready access to a database to figure out what a safe "X" is after conversion. I think a lot of wasted search effort could be saved terminating the search along a know draw line.
So, does anyone have good access to databases where you can quickly serach for maximum non-capture moves to a win versus a draw? There are a lot of endgames where this could apply (like KBB vs KNB, etc). AT one point can you be certain the endagame is a draw? What tools would you use to find my X? Is there a tool that can do this easily for me?
Mark
Help Finding X
Moderators: hgm, Rebel, chrisw
-
CRoberson
- Posts: 2055
- Joined: Mon Mar 13, 2006 2:31 am
- Location: North Carolina, USA
Re: Help Finding X
Hi Mark,
First thing that comes to mind is the 50 move rule. That certainly sets a
maximum. Other than that, SCID and the Chessbase database that
comes with all their programs.
Charles
First thing that comes to mind is the 50 move rule. That certainly sets a
maximum. Other than that, SCID and the Chessbase database that
comes with all their programs.
Charles
-
mjlef
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
Re: Help Finding X
Thanks for the suggestions.CRoberson wrote:Hi Mark,
First thing that comes to mind is the 50 move rule. That certainly sets a
maximum. Other than that, SCID and the Chessbase database that
comes with all their programs.
Charles
Of course, pretty much all programs already have the 50 move rule in them (as does mine). What I am looking for is a way to totally, and safely prune the entire tree say 3 moves (or whatever works for a given endgame) fron conversion. This could save a lot of nodes during a search when material gets traded down to something drawn in the search. Already I find things like this helpful:
if (material=KRvsK) and (FiftyMoveRule-movenumber)>2 and not rootmatematerial then exact:=true;
In this case, if we are in a KR vs K endgame, the last move that was "one way" was more than 2 half moves ago, and there was not a mating material situation at the root, then I consdier the score exact, and stop searching. I know it wil be mate eventually, but why search deeper unless we had a lone king at the root and are looking for mate. I just want to expand this for other situations.
Although I can use some database search utlities, I do not know of one that can go through a given piece endgame and look at all positions to verify the minimum number of moves to safely call a draw (or even a win). Does anyone make a set of tools like that? I can "roll my own" but prefer to be lazy and use something that can already do this.
Does Freezer have this capability? I did not think SCID has databeses in it. Maybe I should check if there is a new version.
Mark
-
Tony
Re: Help Finding X
You can use the .tbs files for this. ( See Crafty site)mjlef wrote:In the endgame, many positions are hopeless draws which can almost be determined via static analysis, after a certain depth of conversion. For example. lets say we get down to K&R vs K&R. Unless one side has a K and R along the same file or column, apart a bit, the other side can only get a draw (in this example, a check of the king might force it to move, and one rook could eat another, or some nearly immediate mate). It seems safe to me to assume a draw in this case as long as you are X half moves from conversion. I do not have ready access to a database to figure out what a safe "X" is after conversion. I think a lot of wasted search effort could be saved terminating the search along a know draw line.
So, does anyone have good access to databases where you can quickly serach for maximum non-capture moves to a win versus a draw? There are a lot of endgames where this could apply (like KBB vs KNB, etc). AT one point can you be certain the endagame is a draw? What tools would you use to find my X? Is there a tool that can do this easily for me?
Mark
Tony
-
jwes
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Help Finding X
Crafty has DTM. He needs DTC, try http://chess.jaet.org/endings/docs/Resu ... ximals.xlsTony wrote:You can use the .tbs files for this. ( See Crafty site)mjlef wrote:In the endgame, many positions are hopeless draws which can almost be determined via static analysis, after a certain depth of conversion. For example. lets say we get down to K&R vs K&R. Unless one side has a K and R along the same file or column, apart a bit, the other side can only get a draw (in this example, a check of the king might force it to move, and one rook could eat another, or some nearly immediate mate). It seems safe to me to assume a draw in this case as long as you are X half moves from conversion. I do not have ready access to a database to figure out what a safe "X" is after conversion. I think a lot of wasted search effort could be saved terminating the search along a know draw line.
So, does anyone have good access to databases where you can quickly serach for maximum non-capture moves to a win versus a draw? There are a lot of endgames where this could apply (like KBB vs KNB, etc). AT one point can you be certain the endagame is a draw? What tools would you use to find my X? Is there a tool that can do this easily for me?
Mark
Tony
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Help Finding X
I think you have to do this case-by-case. For example, KBR vs KR is a draw, except for some rare cases where the weaker side's king is already on the edge of the board. That's pretty easy to fix. These were the "interior node recognizers" mentioned way back in the Dark Thought chess program development (among others)...mjlef wrote:In the endgame, many positions are hopeless draws which can almost be determined via static analysis, after a certain depth of conversion. For example. lets say we get down to K&R vs K&R. Unless one side has a K and R along the same file or column, apart a bit, the other side can only get a draw (in this example, a check of the king might force it to move, and one rook could eat another, or some nearly immediate mate). It seems safe to me to assume a draw in this case as long as you are X half moves from conversion. I do not have ready access to a database to figure out what a safe "X" is after conversion. I think a lot of wasted search effort could be saved terminating the search along a know draw line.
So, does anyone have good access to databases where you can quickly serach for maximum non-capture moves to a win versus a draw? There are a lot of endgames where this could apply (like KBB vs KNB, etc). AT one point can you be certain the endagame is a draw? What tools would you use to find my X? Is there a tool that can do this easily for me?
Mark
-
Tony
Re: Help Finding X
It's not relevant what Crafty uses.jwes wrote:Crafty has DTM. He needs DTC, try http://chess.jaet.org/endings/docs/Resu ... ximals.xlsTony wrote:You can use the .tbs files for this. ( See Crafty site)mjlef wrote:In the endgame, many positions are hopeless draws which can almost be determined via static analysis, after a certain depth of conversion. For example. lets say we get down to K&R vs K&R. Unless one side has a K and R along the same file or column, apart a bit, the other side can only get a draw (in this example, a check of the king might force it to move, and one rook could eat another, or some nearly immediate mate). It seems safe to me to assume a draw in this case as long as you are X half moves from conversion. I do not have ready access to a database to figure out what a safe "X" is after conversion. I think a lot of wasted search effort could be saved terminating the search along a know draw line.
So, does anyone have good access to databases where you can quickly serach for maximum non-capture moves to a win versus a draw? There are a lot of endgames where this could apply (like KBB vs KNB, etc). AT one point can you be certain the endagame is a draw? What tools would you use to find my X? Is there a tool that can do this easily for me?
Mark
Tony
The .tbs have the statistics of the egtb files. If you see that a certain endgame has an mate in at most x ply, and you are already x+1 ply in that endgame, you can return an "at most draw" flag.
Tony
-
hgm
- Posts: 27788
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Help Finding X
This is far from optimal: in KRKR, for instance, the largest DTM is 19, so based on that you could declare draw only after 20 moves.
The maximum DTC, however, is 7 ply. (King on the edge, driven by a check in line with its Rook, so that with a second check it exposes the Rook to capture)
So if a 7-ply search in KRKR does not show the gain of a Rook, you don't have to deepen any further, but can return a draw score with infinite draft.
As 7 is a reasonable number, the DTC metric is useful. Knowing the DTM of 19 would be quite useless in practice.
The maximum DTC, however, is 7 ply. (King on the edge, driven by a check in line with its Rook, so that with a second check it exposes the Rook to capture)
So if a 7-ply search in KRKR does not show the gain of a Rook, you don't have to deepen any further, but can return a draw score with infinite draft.
As 7 is a reasonable number, the DTC metric is useful. Knowing the DTM of 19 would be quite useless in practice.
-
Tony
Re: Help Finding X
Ah, yes. Didn't think about dtc being more efficient.hgm wrote:This is far from optimal: in KRKR, for instance, the largest DTM is 19, so based on that you could declare draw only after 20 moves.
The maximum DTC, however, is 7 ply. (King on the edge, driven by a check in line with its Rook, so that with a second check it exposes the Rook to capture)
So if a 7-ply search in KRKR does not show the gain of a Rook, you don't have to deepen any further, but can return a draw score with infinite draft.
As 7 is a reasonable number, the DTC metric is useful. Knowing the DTM of 19 would be quite useless in practice.
Tony
-
Chan Rasjid
- Posts: 588
- Joined: Thu Mar 09, 2006 4:47 pm
- Location: Singapore
Re: Help Finding X
Hello,
[D]4k3/8/8/8/8/8/4P3/4K3 w - - 0
I did some internal nodes recognizer stuff for
node after a move:-
1) draw basics - when mat == 0 or single n/b
2) draw kpk;
If the above are disabled, Snailchess will lose this game.If enabled, will mate in about 20 moves.
I think if these are not implemented, a program may concede a stalemate/draw here.
Strelka has a bug in playing these at 60 moves/ 40sec.
It may win the first time and if replayed (with hash filled), it may blunder.
Best Regards,
Rasjid
[D]4k3/8/8/8/8/8/4P3/4K3 w - - 0
I did some internal nodes recognizer stuff for
node after a move:-
1) draw basics - when mat == 0 or single n/b
2) draw kpk;
If the above are disabled, Snailchess will lose this game.If enabled, will mate in about 20 moves.
I think if these are not implemented, a program may concede a stalemate/draw here.
Strelka has a bug in playing these at 60 moves/ 40sec.
It may win the first time and if replayed (with hash filled), it may blunder.
Code: Select all
[Event "Computer chess game"]
[Site "AAA-2A681BDBB73"]
[Date "2007.06.09"]
[Round "-"]
[White "Strelka v.1.0.beta"]
[Black "SnailChessV3"]
[Result "1/2-1/2"]
[TimeControl "60/40"]
[FEN "4k3/8/8/8/8/8/4P3/4K3 w - - 0 1"]
[SetUp "1"]
1. Kf2 Kf8 2. Ke3 Ke7 3. Kd4 Kd6 4. e4 Ke6 5. e5 Ke7 6. Ke3 Ke6 7. Ke4 Kd7
8. Kf5 Ke7 9. Kg5 Ke6 10. Kf4 Kd7 11. e6+ Kxe6
{SnailChess draws - insufficient material} 1/2-1/2
Code: Select all
...in search(), before make()
using matHashkey to determine basic board configuration after a move
if (!(SINGLE_PIECE(pS + 1) && PAWN(pS + 1) && IS_MOVE_CAPTURE_EP(*pS->pCurrentMove)));
else{
//edit
score = score_kpk(board, pS, side, *pS->pCurrentMove);
assert(!IS_MOVE_PROMOTE(*pS->pCurrentMove)); ...
}
//search end
int score_kpk(const board_t * board, stack_t * pS, const int side, const move_t m){
/*
will return :-
0 == draw
> 0 == side will safely promote
< 0 == oppn will safely promote
*/
//never promote
int pcCapture = !IS_MOVE_EP(m) ? PIECE( board->brd[TO(m)].sq) : Pawn;
int p_color = ((pS + 1)->matHashkey & MatHashkeyBP) != 0;//at most 1 p after make()
int xp_color = p_color ^ 1;
int p_sq = board->pawn[p_color]->sq;
int promote_sq = PROMOTE_SQ(p_sq, p_color);
//diagonal sq next to a corner promote-sq
int virtualPromoteSq = FILE(promote_sq) == 0 || FILE(promote_sq) == 7
? NEXT_DIAGONAL_PROMOTE_SQ_CORNER(promote_sq, p_color) : promote_sq;
int frontPawn = FRONT_SQ(p_sq, p_color);
int pOnMove = (p_color == side) ^ 1;
int score, i, j, k;
u64 bb;
assert((pS + 1)->matHashkey == DRAW_KPK_WP
|| (pS + 1)->matHashkey == DRAW_KPK_BP);
assert(pcCapture);
assert( board->nPawn[0] + board->nPawn[1] - (pcCapture == Pawn) == 1);
assert(bitCount((pS + 1)->matHashkey) == 1);//p
if (!pOnMove){
//draw if lone-k on move and can safe capt pawn
//get bb, pos of pawn after do()
if (IS_MOVE_PAWN(m)){
if (!IS_MOVE_EP(m)){//pawn at to-sq
bb = board->brd[TO(m)].bb;
}else{//pawn at ep-sq
bb = board->brd[EP_CAPTURE_SQ(m)].bb;
}
}else{//pawn not moved
bb = pS->bits[p_color][Pawn];
}
assert(bb && !(bb & bb - 1));
//bb == pos of pawn after do()
if (bb & pS->attackBB[xp_color][King] & ~pS->attackBB[p_color][King]){
//hash node after do()
hash(MaxDepth, EX, 0, (pS+1)->matHashkey, 100, 0);
return 0;
}
}
/*
1) stalemate if lone-k can occupy any of 4 corners of promote-sq if promote-sq is corner
2) stalemate if lone-k can occupy the frontsq of promote sq
3) k-k race to prom_sq must add + 1 step for p-king as it may need to avoid attack-sq of pawn
*/
if (board->king[xp_color]->sq == frontPawn
|| board->king[xp_color]->sq == virtualPromoteSq){//ok
//hash node after do()
hash(MaxDepth, EX, 0, (pS+1)->matHashkey, 100, 0);
return 0;
}
if (FILE(promote_sq) == 0 || FILE(promote_sq) == 7){
u64 bbCorners4;
switch(promote_sq){
case A1:
bbCorners4 = bbA1 | bbA2 | bbB1 | bbB2;
break;
case A8:
bbCorners4 = bbA8 | bbA7 | bbB8 | bbB7;
break;
case H1:
bbCorners4 = bbH1 | bbH2 | bbG1 | bbG2;
break;
case H8:
bbCorners4 = bbH8 | bbH7 | bbG8 | bbG7;
}
if (board->king[xp_color]->bb && bbCorners4){
//hash node after do()
hash(MaxDepth, EX, 0, (pS+1)->matHashkey, 100, 0);
return 0;//ok
}
}
j = k = 0;
if ((i = 8 - ROW_RANK(p_sq, p_color))
< pOnMove + DIST64(board->king[xp_color]->sq, promote_sq)
//is single king outrace pawn to prom-sq
|| ( j = DIST64(board->king[p_color]->sq, virtualPromoteSq))
< 1 + pOnMove
+ DIST64(board->king[xp_color]->sq, virtualPromoteSq)
//is single king outrace pawn-side king to prom-sq
|| ( k = DIST64(board->king[p_color]->sq, p_sq))
< 2 + pOnMove + DIST64(board->king[xp_color]->sq, p_sq)
//is single king nears pawn ahead of side king; extra step needed(dist + 3)
//as single king must avoid attack sq of pawn
){
//pawn side wins all 3 races
//!!!! codes may be bad here
i -= pOnMove;
//get an estimate score(ub/lb) relative to a queen
score = vQueen - vPawn - (j << 3) - (i + k)
- (DIST64(board->king[xp_color]->sq, promote_sq) <= 2) * v2Pawn;
score *= (1 - (p_color != side) * 2);//get score for proper side on move
i += j + k;//step to queen + king races to prot,etc
//i == num move to queen; depth to hash == i * 2 + p_color == side
i = i * 2 + (p_color == side);
//depth to hash = i;
assert(i > 0 && i < 64);
//hash node after move, i == depth
hash(i, score < 0 ? LB : UB, -score , (pS+1)->matHashkey, 100, 0);
}else{
//pawn side lost all 3 races
//hash node after do()
hash(MaxDepth, EX, 0 , (pS+1)->matHashkey, 100, 0);
score = 0;
}
return score;
}
Rasjid