Twisted Logic bug

[rvida]

Really not. Took me about 30 min and a bit of testing time to implement a KQKP evaluation function for both sides and it does practically not reduce the speed of normal evaluation. It does probably not really raise the strength because the endgame occurs very infrequently and other engines also play Kb6 because it's the only move which does not lose the pawn within the horizon.

If you want I can post some pseudo code but it's really easy to implement. No big deal.

Please post, I'm curious how you did it. The only kqkp code I have seen so far is from fruit and I dont like it very much.

[michiguel]

Really not. Took me about 30 min and a bit of testing time to implement a KQKP evaluation function for both sides and it does practically not reduce the speed of normal evaluation. It does probably not really raise the strength because the endgame occurs very infrequently and other engines also play Kb6 because it's the only move which does not lose the pawn within the horizon.

If you want I can post some pseudo code but it's really easy to implement. No big deal.

Please post, I'm curious how you did it. The only kqkp code I have seen so far is from fruit and I dont like it very much.

Is this so difficult? I had that too in Gaviota. In fact I posted about it in some other thread I cannot find right now.

Miguel

[michiguel]

Really not. Took me about 30 min and a bit of testing time to implement a KQKP evaluation function for both sides and it does practically not reduce the speed of normal evaluation. It does probably not really raise the strength because the endgame occurs very infrequently and other engines also play Kb6 because it's the only move which does not lose the pawn within the horizon.

If you want I can post some pseudo code but it's really easy to implement. No big deal.

Please post, I'm curious how you did it. The only kqkp code I have seen so far is from fruit and I dont like it very much.

This is my version (I had a bug in kingdist I posted about it, where is that thread? I thought I posted it in this one)

Miguel
PS: This is an old version I had in my office, it may be slighlty different in the latest version (I do not know). I hope it is readable.

Code: Select all

static eval_t
eval_QvsP (POSITION *po, unsigned int ownside)
{

	BITBOARD a;
	BITBOARD p;
	SQUARE list[17];
	SQUARE ksq, qsq, ksq_, psq_;
	unsigned int co, turn_color, Qcolor;	
	int defensive_ply;
	
	eval_t score, whitebonus, Qturn;	
	bool_t winning, drawing;
	
	ASSERT (isQvsP(po));
	
	turn_color = PO_TURN(po);
	turn_color = Cidx (turn_color);
	
	Qcolor = BL;
	if (po->bi.occ[WH].n[QUEEN] == 1) {
		Qcolor = WH;
	}
	Qturn = (Qcolor == turn_color);
	
	co = Qcolor;	

	ksq = po->bi.occ[co].king;
	a   = po->bi.occ[co].all;
	p   = po->bi.occ[co].pc[PAWN];
	p = ~p;
	a &= p;					/* do not include pawns on the list */
	bb_setbitoff(&a, ksq);	/* do not include king on the list */
	sqlist_frombb (list, a);
	ASSERT (sqlist_len(list) == 1);
	ASSERT (((po->brd[list[0]]) & PIECE_MASK) == QUEEN);
	qsq = list[0];
		
	co   = Opp(co);
	ksq_ = po->bi.occ[co].king;
	a    = po->bi.occ[co].pc[PAWN];
	sqlist_frombb (list, a);
	ASSERT (sqlist_len(list) == 1);	
	ASSERT (((po->brd[list[0]]) & PIECE_MASK) == PAWN);	
	psq_ = list[0];
	
	if (Qcolor == BL) { /* "invert" board */
		ksq ^= 070; ksq_ ^= 070; qsq ^= 070; psq_ ^= 070;
	}
	
	if ((psq_ & 07) > 3) { /*/ invert to queen side */
		ksq ^= 07; ksq_ ^= 07; qsq ^= 07; psq_ ^= 07;		
	}
	
	#if defined (SHOW_EVAL)
	printf ("ksq, qsq, ksq_, psq_: %d %d %d %d\n", ksq, qsq, ksq_, psq_);	
	#endif
	
	/* calculate scores */
	score = eval_regular (po, ownside,-INFINITY_VALUE,INFINITY_VALUE);
		
	/* increase winning chances */
	/* queen in pawns way */
	winning = 	(SQ_GETCOL(qsq) == SQ_GETCOL (psq_)) 
				&& (SQ_GETROW (qsq) < SQ_GETROW (psq_));
				
	#if defined (SHOW_EVAL)
	printf ("winning: %d\n", winning);	
	#endif

	whitebonus = 0;
	
	if (winning) {
		if (WH == Qcolor) {
 			whitebonus += PAWN_VALUE/2;
		} else {
 			whitebonus -= PAWN_VALUE/2;		
		}		
		if (ownside == WH) {
			score += whitebonus;
		} else {
			score -= whitebonus;
		}	
		
		return score;
	}

	defensive_ply = 0;
	if (!Qturn)
		defensive_ply++;

	drawing = 	psq_ == A2 
				&& (ksq_ == B1 || ksq_ == B2 || ksq_ == A1)
				&& (defensive_ply + kingdist (B3, ksq )) > 2;
				
	#if defined (SHOW_EVAL)
	printf ("drawing: %d\n", drawing);	
	#endif

	drawing = drawing ||
		(	
				psq_ == C2 
				&& (ksq_ == B1 || ksq_ == B2 || ksq_ == A1)
				&& (defensive_ply + kingdist (B3, ksq )) > 1
		);
		
	#if defined (SHOW_EVAL)
	printf ("drawing: %d\n", drawing);	
	#endif	

	drawing = drawing ||
		(	
				psq_ == C2 
				&& (ksq_ == C1 || ksq_ == D1 || ksq_ == D2)
				&& (defensive_ply + kingdist(B3, ksq )) > 2
				&& (defensive_ply + kingdist(D3, ksq )) > 2
		);		
		
	#if defined (SHOW_EVAL)
	printf ("drawing: %d", drawing);	
	#endif		

	if (drawing) {
		score = score / 16;
	}
	
	return score;
	
} /*function*/

[metax]

Well, my code is actually _very_ simple as I leave the cases to search where the side with the queen can still win because his king is close enough to the pawn. Here is my minimalistic approach (but it may be buggy although I tested it with a number of positions):

Code: Select all

int EvaluateKQKP()
{
    int pawnSquare = GetPawnSquare(),
    queenSquare = GetQueenSquare();

    if (pawnSquare == A2 &&
    (blackKing == A1 ||
    blackKing == B1 ||
    blackKing == B2))
    {
        return SCORE_DRAW;
    }
    if (pawnSquare == H2 &&
    (blackKing == H1 ||
    blackKing == G1 ||
    blackKing == G2))
    {
        return SCORE_DRAW;
    }
    if (pawnSquare == C2 &&
    (blackKing == A1 ||
    blackKing == A2 ||
    blackKing == B1 ||
    blackKing == B2 ||
    blackKing == D1 ||
    blackKing == D2 ||
    blackKing == E1 ||
    blackKing == E2 ||
    blackKing == C1))
    {
        return SCORE_DRAW;
    }
    if (pawnSquare == F2 &&
    (blackKing == H1 ||
    blackKing == H2 ||
    blackKing == G1 ||
    blackKing == G2 ||
    blackKing == D1 ||
    blackKing == D2 ||
    blackKing == E2 ||
    blackKing == E1 ||
    blackKing == F1))
    {
        return SCORE_DRAW;
    }

    return (QueenValue - PawnValue - ChebyshevDistance(whiteKing, blackKing)) * toMove;
}

'Chebyshev distance' is the diagonal distance between two squares according to the wiki. I have a similar function for black but that should be easy to figure out. Note that this can be only used as evaluation function for KQKP endgames, not as Interior Node Recognizer because there are positions where it fails:


[d]2K5/2P5/8/8/2k5/8/8/4q3 b - - 0 1

Analysis by ChessMind 0.72:

1...Qd2 2.Kb7 Qe1 3.c8Q+ Kd3 4.Kc6 Kc2
= (0.00) Depth: 6/13 00:00:00
1...Qd2 2.Kb7 Qe1 3.c8Q+ Kd3 4.Kc6 Kc2
= (0.00) Depth: 7/13 00:00:00 34kN
1...Qd2 2.Kb7 Qe1 3.c8Q+ Kd3 4.Kc6 Kc2 5.Kd5+
= (0.00) Depth: 8/16 00:00:00 89kN
1...Qd2 2.Kb7 Qe1 3.c8Q+ Kd3 4.Kc6 Kc2 5.Kd5+ Kd1
= (0.00) Depth: 9/17 00:00:00 202kN
1...Kc5
-/+ (-1.01 ++) Depth: 9/20 00:00:00 202kN
1...Kc5
-+ (-2.67 ++) Depth: 9/20 00:00:00 202kN
1...Kc5
-+ (-5.43 ++) Depth: 9/20 00:00:00 202kN
1...Kc5 2.Kd7 Qd1+ 3.Ke6 Qb3+ 4.Kf5 Qf7+ 5.Kg4 Qxc7 6.Kf5 Qc8+ 7.Ke4 Qe6+
-+ (-10.33) Depth: 10/25 00:00:02 935kN
1...Kc5 2.Kd7 Qd1+ 3.Ke6 Qd5+ 4.Kf6 Qc6+ 5.Kg5 Kd4 6.Kf5 Qxc7 7.Ke6 Qe5+
-+ (-10.58) Depth: 11/27 00:00:03 1583kN
1...Kc5 2.Kd7 Qd1+ 3.Ke6 Qd5+ 4.Kf6 Qc6+ 5.Kg5 Qxc7 6.Kf5 Kd5 7.Kg4 Ke4 8.Kg5
-+ (-10.82) Depth: 12/30 00:00:06 2708kN
1...Kc5 2.Kd7 Qd1+ 3.Ke6 Qd5+ 4.Kf6 Qc6+ 5.Kg5 Qxc7 6.Kf5 Kd5 7.Kg4 Ke4 8.Kg5 Qg7+
-+ (-10.83) Depth: 13/33 00:00:08 3822kN
1...Qe7
-+ (-#13 ++) Depth: 13/33 00:00:09 4435kN
1...Qe7
-+ (-#10) Depth: 13/33 00:00:11 5166kN

(The position is mate in 8 of course but scores after a research of a fail-high are never really reliable in ChessMind.)
My simple evaluation function will evaluate this as a draw because in my opinion the search has to take care of this (black can win the pawn). Nevertheless I post it here as an alternative to Miguel's which seems a bit more complicated. Of course the conditions can be optimized a bit, but this is the raw idea. The position recognizes all theoretical draws I know but sometimes evaluates won positions as a draw as pointed out before, but the search can take care of that. If you don't mind having an imperfect evaluation function for this endgame, it may be an alternative.

[metax]

Another example of a position where the above evaluation function fails:

[d]K7/P7/8/8/8/1k6/8/4q3 b - - 0 1

Analysis by ChessMind 0.72:

1...Qd2 2.Kb7 Qe1 3.a8Q Qd2 4.Ka6
= (0.00) Depth: 6/10 00:00:00
1...Qd2 2.Kb7 Qe1 3.a8Q Qd2 4.Ka6 Kc2
= (0.00) Depth: 7/13 00:00:00 38kN
1...Qd2 2.Kb7 Qe1 3.a8Q Qd2 4.Ka6 Kc2 5.Kb7
= (0.00) Depth: 8/15 00:00:00 82kN
1...Qd2 2.Kb7 Qe1 3.a8Q Qd2 4.Ka6 Kc2 5.Kb7 Kd1
= (0.00) Depth: 9/17 00:00:00 145kN
1...Qd2 2.Kb7 Qe1 3.a8Q Qd2 4.Ka6 Kc2 5.Kb7 Kd1 6.Ka6
= (0.00) Depth: 10/20 00:00:00 249kN
1...Qd2 2.Kb7 Qe1 3.a8Q Qd2 4.Ka6 Kc2 5.Kb7 Kd1 6.Ka6 Ke2
= (0.00) Depth: 11/22 00:00:00 392kN
1...Ka4
-/+ (-1.01 ++) Depth: 11/25 00:00:00 527kN
1...Ka4
-+ (-2.67 ++) Depth: 11/25 00:00:00 527kN
1...Ka4
-+ (-5.43 ++) Depth: 11/25 00:00:00 528kN
1...Ka4
-+ (-10.03 ++) Depth: 11/27 00:00:01 595kN
1...Ka4
-+ (-10.07) Depth: 11/28 00:00:01 888kN
1...Kc4 2.Kb7 Qe7+ 3.Kb6 Qe4 4.Kc7 Qa8 5.Kd6 Qxa7 6.Ke5 Qd4+
-+ (-10.08) Depth: 11/28 00:00:02 1116kN
1...Kc4 2.Kb7 Qe7+ 3.Kb6 Qe4 4.Kc7 Qa8 5.Kd6 Qxa7 6.Ke5 Qd4+ 7.Kf5
-+ (-10.32) Depth: 12/30 00:00:02 1356kN
1...Kb4 2.Kb7 Qe7+ 3.Kb6 Qf6+ 4.Kc7 Qf7+ 5.Kd6 Qxa7 6.Ke5 Kc3 7.Kf5 Kd3
-+ (-10.33) Depth: 12/32 00:00:03 1826kN
1...Kb4 2.Kb7 Kc5 3.a8Q Qe7+ 4.Kc8 Qe8+ 5.Kc7 Qxa8 6.Kd7 Qe4 7.Kc8 Qe7
-+ (-11.33) Depth: 13/32 00:00:05 2999kN

[metax]

Did you delete your post now? Why that?

Your code seems to simple. ...

But then the wKc1 will immediately capture the Pc2 anyway. As I said, there are a few positions where it fails which then require a search. It could be improved so that it evaluates these endgames perfectly but I think these special cases are best left to search or the evaluation function becomes very complicated. Maybe a slight improvement for practical play would be to not return a draw score but instead a very small score (~0.1) for the queen's side so that a technical draw (three-fold repetition, 50-move rule etc.) would be worth more than a likely KQKP draw. I have tested the evaluation function on a number of KQKP positions and it always gave the right score within a second and 12 plies maximum.

[hgm]

I decided it was OK in the evaluation after all, only a few seconds after I posted it...

[Edsel Apostol]

OK, so I haven't experienced a bug but only a heavlily pruning search, as TL has always had.
The test position hasn't any practical relevance anyway, because I noticed Twisted Logic to solve other tactics problems much faster than before.

One question may be allowed: I have seen the latest Twisted Logic perform much better in tactical test positions than the previous version and you also wrote that you switched to a more conservative pruning method. Why doesn't that help in this position?

The pruning method in the latest TL is more conservative compared to previous versions but if compared with other engines it is still very aggressive. Note that I don't have depth limits with pruning in TL so it can prune a very big subtree for faster search but in expense of accuracy. This may be one of those positions that it is inaccurate.

[zamar]

The pruning method in the latest TL is more conservative compared to previous versions but if compared with other engines it is still very aggressive. Note that I don't have depth limits with pruning in TL so it can prune a very big subtree for faster search but in expense of accuracy. This may be one of those positions that it is inaccurate.

Interesting decision! My intuition says that in high depths it could be better to do huge reductions (fx. 6 plies) instead of completely pruning subtree. This way one could guarantee minimum accurary at very low cost. Have you thought about this?

[hgm]

The question that puzzled me, is: what exactly did you prune, and whyever did you do that? Not seeing that Kd4 is losing seems to require you to prune the only obvious move in various positions, such as Kf4 (securing the promotion of your passer) or Qd1+ (starting checking when the opponent still has an undefended Queen on the board directly after promotion).