Help Finding X

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
mjlef
Posts: 1420
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Help Finding X

Post by mjlef » Fri Jun 08, 2007 5:15 pm

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

CRoberson
Posts: 1989
Joined: Mon Mar 13, 2006 1:31 am
Location: North Carolina, USA
Contact:

Re: Help Finding X

Post by CRoberson » Fri Jun 08, 2007 6:30 pm

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

mjlef
Posts: 1420
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Help Finding X

Post by mjlef » Fri Jun 08, 2007 7:14 pm

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
Thanks for the suggestions.

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

Post by Tony » Fri Jun 08, 2007 7:31 pm

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
You can use the .tbs files for this. ( See Crafty site)

Tony

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Help Finding X

Post by jwes » Fri Jun 08, 2007 8:45 pm

Tony wrote:
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
You can use the .tbs files for this. ( See Crafty site)

Tony
Crafty has DTM. He needs DTC, try http://chess.jaet.org/endings/docs/Resu ... ximals.xls

bob
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Help Finding X

Post by bob » Sat Jun 09, 2007 1:40 am

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
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)...

Tony

Re: Help Finding X

Post by Tony » Sat Jun 09, 2007 6:52 am

jwes wrote:
Tony wrote:
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
You can use the .tbs files for this. ( See Crafty site)

Tony
Crafty has DTM. He needs DTC, try http://chess.jaet.org/endings/docs/Resu ... ximals.xls
It's not relevant what Crafty uses.

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

User avatar
hgm
Posts: 23474
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Help Finding X

Post by hgm » Sat Jun 09, 2007 7:11 am

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

Re: Help Finding X

Post by Tony » Sat Jun 09, 2007 7:39 am

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.
Ah, yes. Didn't think about dtc being more efficient.

Tony

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Help Finding X

Post by Chan Rasjid » Sat Jun 09, 2007 9:20 am

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.

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&#40;m&#41; ? PIECE&#40; board->brd&#91;TO&#40;m&#41;&#93;.sq&#41; &#58; Pawn;
	int p_color = (&#40;pS + 1&#41;->matHashkey & MatHashkeyBP&#41; != 0;//at most 1 p after make&#40;) 
	int xp_color = p_color ^ 1;
	int p_sq =  board->pawn&#91;p_color&#93;->sq;
	int	promote_sq =  PROMOTE_SQ&#40;p_sq, p_color&#41;;
	//diagonal sq next to a corner promote-sq
	int virtualPromoteSq = FILE&#40;promote_sq&#41; == 0 || FILE&#40;promote_sq&#41; == 7
		? NEXT_DIAGONAL_PROMOTE_SQ_CORNER&#40;promote_sq, p_color&#41; &#58; promote_sq;
	int frontPawn = FRONT_SQ&#40;p_sq, p_color&#41;;
	int pOnMove = &#40;p_color == side&#41; ^ 1;
	int score, i, j, k;
	u64 bb;
	assert&#40;&#40;pS + 1&#41;->matHashkey == DRAW_KPK_WP
		|| &#40;pS + 1&#41;->matHashkey == DRAW_KPK_BP&#41;;
	assert&#40;pcCapture&#41;;
	assert&#40;	board->nPawn&#91;0&#93; + board->nPawn&#91;1&#93; - &#40;pcCapture == Pawn&#41; == 1&#41;;
	assert&#40;bitCount&#40;&#40;pS + 1&#41;->matHashkey&#41; == 1&#41;;//p

	if (!pOnMove&#41;&#123; 
		//draw if lone-k on move and can safe capt pawn
		//get bb,  pos of pawn after do&#40;)
		if &#40;IS_MOVE_PAWN&#40;m&#41;)&#123; 
			if (!IS_MOVE_EP&#40;m&#41;)&#123;//pawn at to-sq
				bb = board->brd&#91;TO&#40;m&#41;&#93;.bb;
			&#125;else&#123;//pawn at ep-sq
				bb = board->brd&#91;EP_CAPTURE_SQ&#40;m&#41;&#93;.bb;
			&#125;
		&#125;else&#123;//pawn not moved
			bb = pS->bits&#91;p_color&#93;&#91;Pawn&#93;;
		&#125;
		assert&#40;bb && !&#40;bb & bb - 1&#41;);
		//bb == pos of pawn after do&#40;)
		if &#40;bb & pS->attackBB&#91;xp_color&#93;&#91;King&#93; & ~pS->attackBB&#91;p_color&#93;&#91;King&#93;)&#123;
			//hash node after do&#40;)
			hash&#40;MaxDepth, EX, 0, &#40;pS+1&#41;->matHashkey, 100, 0&#41;;
			return 0;
		&#125;
	&#125;

	/*
	1&#41; stalemate if lone-k can occupy any of 4 corners of promote-sq if  promote-sq is corner
	2&#41; stalemate if lone-k can occupy the frontsq of promote sq  
	3&#41; k-k race to prom_sq must add + 1 step for p-king as it may need to avoid attack-sq of pawn  
  */
	if &#40;board->king&#91;xp_color&#93;->sq == frontPawn
		 || board->king&#91;xp_color&#93;->sq == virtualPromoteSq&#41;&#123;//ok
		//hash node after do&#40;)
		hash&#40;MaxDepth, EX, 0, &#40;pS+1&#41;->matHashkey, 100, 0&#41;;
		return 0;
	&#125;
	
	if &#40;FILE&#40;promote_sq&#41; == 0 || FILE&#40;promote_sq&#41; == 7&#41;&#123;
		u64 bbCorners4;
		switch&#40;promote_sq&#41;&#123;
		case	A1&#58;
			bbCorners4 = bbA1 | bbA2 | bbB1 | bbB2;
			break;
		case	A8&#58;
			bbCorners4 = bbA8 | bbA7 | bbB8 | bbB7;
			break;
		case	H1&#58;
			bbCorners4 = bbH1 | bbH2 | bbG1 | bbG2;
			break;
		case	H8&#58;
			bbCorners4 = bbH8 | bbH7 | bbG8 | bbG7;
		&#125;
		if &#40;board->king&#91;xp_color&#93;->bb && bbCorners4&#41;&#123;
			//hash node after do&#40;)
			hash&#40;MaxDepth, EX, 0, &#40;pS+1&#41;->matHashkey, 100, 0&#41;;
			return 0;//ok
		&#125;
	&#125;

	j = k = 0;
	if (&#40;i = 8 - ROW_RANK&#40;p_sq, p_color&#41;)
		< pOnMove + DIST64&#40;board->king&#91;xp_color&#93;->sq, promote_sq&#41;
		//is single king outrace pawn to prom-sq	
		|| ( j = DIST64&#40;board->king&#91;p_color&#93;->sq, virtualPromoteSq&#41;) 	
			< 1 + pOnMove 
			+ DIST64&#40;board->king&#91;xp_color&#93;->sq, virtualPromoteSq&#41;
			//is single king outrace  pawn-side king to prom-sq
		|| ( k = DIST64&#40;board->king&#91;p_color&#93;->sq, p_sq&#41;) 	
			 < 2 + pOnMove + DIST64&#40;board->king&#91;xp_color&#93;->sq, p_sq&#41;
			 //is single king nears pawn ahead of side king; extra step needed&#40;dist + 3&#41; 
			//as single king must avoid attack sq of pawn  
			 )&#123;
		//pawn side wins all 3 races
		 //!!!! codes may be bad here
		i -= pOnMove;
		//get an estimate score&#40;ub/lb&#41; relative to a queen 
		score = vQueen - vPawn - &#40;j << 3&#41; - &#40;i + k&#41;
			- &#40;DIST64&#40;board->king&#91;xp_color&#93;->sq, promote_sq&#41; <= 2&#41; * v2Pawn;
		score *= &#40;1 - &#40;p_color != side&#41; * 2&#41;;//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 + &#40;p_color == side&#41;;
		//depth to hash = i;
		assert&#40;i > 0 && i < 64&#41;;
		//hash node after move, i == depth
		hash&#40;i, score < 0 ? LB &#58; UB, -score , &#40;pS+1&#41;->matHashkey, 100, 0&#41;;
	&#125;else&#123;
		//pawn side lost all 3 races
		//hash node after do&#40;)
		hash&#40;MaxDepth, EX, 0 , &#40;pS+1&#41;->matHashkey, 100, 0&#41;;
		score = 0;
	&#125;
	return score;
&#125;
Best Regards,
Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

Post Reply