Mating with two bishops

[oakstair]

Hi!

I am developing a java chess engine and have some problem getting it to play accurate when mating with two bishops.

fen: 8/8/8/7B/5k1B/8/8/K7 w - - 0 1

My evaluator gives credits if weak king is near the edge (Mating score) plus it gives score if stronger king is near the waker king.

My problem is that the the engine plays real bad ... i.e. it plays far from optimal.

E.g.: (Search depth = 7)

Failed to solve position: 8/8/8/7B/5k1B/8/8/K7 w - - 0 1 Mate in 30 moves.

1.Ka2 Kf5 2.Kb3 Kf4 3.Kb4 Kf5 4.Kb5 Kf4 5.Bf6 Kf5
6.Bd8 Kf4 7.Bg6 Kg4 8.Kc5 Kg3 9.Bc7+ Kg4 10.Kd5 Kg5
11.Be4 Kh6 12.Bf4+ Kh5 13.Bf3+ Kh4 14.Be2 Kh3 15.Bf3 Kh4
16.Be2 Kh3 17.Ke4 Kh4 18.Bd3 Kh5 19.Kf3 Kh4 20.Bc4 Kh5
21.Bf7+ Kh4 22.Be3 Kh3 23.Be6+ Kh4 24.Bf7 Kh3 25.Bf2 Kh2
26.Bg3+ Kh1 27.Kf4 Kg1 28.Kf3 Kh1 29.Bf4 Kg1 30.Ke2 Kg2
31.Be6

The only answer that I can come up with is that since only the leaf nodes are evaluated the engine gets the same score for moves even if they are worse.

I.e., Ka2 instead of Kb2 as the starting move.

[oakstair]

When increasing the search depth to 9 it solves the problem ...

Solved 8/8/8/7B/5k1B/8/8/K7 w - - 0 1 : Mate in 30 moves.
1.Kb2 Kf5 2.Kb3 Kf4 3.Kc4 Ke4 4.Bg3 Kf5 5.Bd6 Kf6
6.Kc5 Kg5 7.Bf7 Kh4 8.Kd5 Kh3 9.Ke4 Kh4 10.Kf4 Kh3
11.Kf3 Kh4 12.Be7+ Kh3 13.Be6+ Kh2 14.Kf2 Kh1 15.Kf1 Kh2
16.Bd6+ Kh1 17.Bd5# 1-0

.. but my question is why the engine plays so bad with a search depth of 7.

Code: Select all

public class KX_K implements Evaluator {

	// Drive defending king towards the edge of the board

	// @formatter:off
	private static final int MateTable[] = { 
		100, 90, 80, 70, 70, 80, 90, 100,
		 90, 70, 60, 50, 50, 60, 70,  90, 
		 80, 60, 40, 30, 30, 40, 60,  80, 
		 70, 50, 30, 20, 20, 30, 50,  70, 
		 70, 50, 30, 20, 20, 30, 50,  70, 
		 80, 60, 40, 30, 30, 40, 60,  80, 
		 90, 70, 60, 50, 50, 60, 70,  90, 
		100, 90, 80, 70, 70, 80, 90, 100
	};
	// @formatter:on

	// The attacking side is given a descending bonus based on distance between
	// the two kings in basic endgames.
	private static final int DistanceBonus[] = { 0, 0, 100, 80, 60, 40, 20, 10 };


	public boolean matches(ChessBoard pos) {
		ChessPieceCount pc = pos.pieceCount();
		if (pc.totalPieceValue() < 5 || (pc.totalPieceValue(WHITE) != 0 && pc.totalPieceValue(BLACK) != 0))
			return false;

		if (pc.totalPieceValue() == 6) {
			String pattern = pc.toString();
			if (pattern.equals("k2n-k") || pattern.equals("k-k2n"))
				return false;
		}
		return true;
	}

	public int evaluate(ChessBoard pos) {

		ChessPieceCount pc = pos.pieceCount();
		ChessColor stronger = pc.stronger();
		ChessColor weaker = stronger.opponent();

		assert (Material.computeMaterialNoPawns(pos, weaker) == 0);
		assert (pc.count(PAWN, weaker) == 0);
	
		// Stalemate detection with lone king
		if ((pos.whosTurn() == weaker) && !pos.isInCheck() && (0 == pos.getMoves().size())) {
			return VALUE_DRAW;
		}
	
		ChessSquare winnerKSq = pos.kingSquare(stronger);
		ChessSquare loserKSq = pos.kingSquare(weaker);
	
		int result = Material.computeMaterialNoPawns(pos, stronger) + pc.count(PAWN, stronger)
				* PawnValueEg + MateTable[loserKSq.ordinal()] + DistanceBonus[winnerKSq.distance(loserKSq)];
	
		if ((pc.count(QUEEN, stronger) > 0) || (pc.count(ROOK, stronger) > 0) || pos.hasBishopPair(stronger)) {
			result += VALUE_KNOWN_WIN;
		}
	
		return stronger == pos.whosTurn() ? result : -result;
	}
}

[User923005]

Here is a very nice explanation of the algorithm (best I have seen).
It probably is not optimal to simply follow the cone constriction, but I guess that it will never fail unless you are running out of irreversible moves.

http://www.rockfordchess.org/instructio ... eBBvsK.PDF

If you want minimal steps to mate, the tablebase solution is obviously optimal.

The nalimov files are pretty small:
Directory of C:\chess\nalimov
2003-06-19 04:00 PM 205,549 kbbk.nbb.emd
2003-06-19 04:00 PM 249,216 kbbk.nbw.emd

The syzygy files even smaller (and will always solve but not always with the shortest possible mate if you care about such things):
Directory of C:\chess\syzygy
2013-04-11 04:00 PM 58,000 KBBvK.rtbw
2013-04-11 04:00 PM 136,272 KBBvK.rtbz

The gaviota file is between the two, but it offers perfect mate like the nalimov:
Directory of C:\chess\gtb
2010-08-17 10:50 AM 303,495 kbbk.gtb.cp4

If you just want to code the algorithm, then I think that the pdf file shows a beautifully clear way to do it in a short (but not necessarily optimal) number of steps.

[H.G.Muller]

Are there any terms in the Bishop evaluation that could interfere with the goal of driving the bare King to the corner (e.g. PST awards for centralizing the Bishops)? If so, you should perhaps increase the award for driving the bare King to the corner. If proximity to the corner is the dominant evaluation term, I would expect that 7 ply search depth is more than enough to always find a way to force the bare King at least one step closer to the corner. (If 7 ply is truly 7 ply, and not subject to all kind of reductions.)

Perhaps you can get an indication what is wrong by examining the PV when it does a silly move with a good score. What was the position it hoped to reach by this move, and why does it think it deserved such a good score?