Code of Chiron for Detection of Pawn Blockages

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
uaf
Posts: 98
Joined: Sat Jul 31, 2010 6:48 pm
Full name: Ubaldo Andrea Farina
Contact:

Code of Chiron for Detection of Pawn Blockages

Post by uaf » Thu Oct 13, 2011 7:55 pm

Hello, this is part of the code used in Chiron for detecting static and dynamic pawn blockages.
This code was written several years ago, it's not optimized at all and it is redundant for black and white. But that doesn't matter because the result is stored in the hash table so this function is called rarely.
It's called when only pawns are left.
It was written following the code example and the rules described by Omid David in his paper: (2006). Blockage Detection in Pawn Endgames.

Perhaps it could be interesting for someone.
Sorry it's not commented but can be easily understood reading the paper.

Code: Select all


int FormsFence(int f, int r, int marked[8][8], int fence[8][8], int processed[8][8])
{
	processed[f][r] = 1;

	if (f == FILE_H) {
		fence[f][r] = 1;
		return(1);
	}

	if (marked[f][r + 1] && !processed[f][r + 1] && FormsFence(f, r + 1, marked, fence, processed)) {
		fence[f][r] = 1;
		return(1);
	}

	if (marked[f + 1][r] && !processed[f + 1][r] && FormsFence(f + 1, r, marked, fence, processed)) {
		fence[f][r] = 1;
		return(1);
	}

	if (marked[f][r - 1] && !processed[f][r - 1] && FormsFence(f, r - 1, marked, fence, processed)) {
		fence[f][r] = 1;
		return(1);
	}

	return(0);
}

int Blockage(SEARCH_INFO *search)
{
	int f, r, sq;
	int fixed_pawn[8][8] = {0};
	int fence_rank[8];
	int dynamic_pawns[8];
	int i, n_dyn = 0;
	int fence_formed = 0;
	int blockage = 0;
	int marked[8][8] = {0};
	int fence[8][8] = {0};
	int processed[8][8] = {0};

	if (search->pos.side == WHITE) {
		for (r = RANK_7; r > RANK_1; r--) {
			for &#40;f = FILE_A; f <= FILE_H; f++) &#123;
				sq = r * 8 + f;
				if &#40;search->pos.board&#91;sq&#93; == WPAWN&#41; &#123;
					if (   &#40;r < RANK_7 && &#40;search->pos.board&#91;sq + 8&#93; == BPAWN || fixed_pawn&#91;f&#93;&#91;r + 1&#93;))
						&& &#40;f == FILE_A || search->pos.board&#91;sq + 7&#93; != BPAWN&#41;
						&& &#40;f == FILE_H || search->pos.board&#91;sq + 9&#93; != BPAWN&#41;) &#123;
						fixed_pawn&#91;f&#93;&#91;r&#93; = 1;
						marked&#91;f&#93;&#91;r&#93; = 1;
					&#125;
					else
						dynamic_pawns&#91;n_dyn++&#93; = sq;
				&#125;
				else if &#40;search->pos.board&#91;sq&#93; == BPAWN&#41; &#123;
					if &#40;f != FILE_A&#41;
						marked&#91;f - 1&#93;&#91;r - 1&#93; = 1;
					if &#40;f != FILE_H&#41;
						marked&#91;f + 1&#93;&#91;r - 1&#93; = 1;
				&#125;
			&#125;
		&#125;

		for &#40;r = RANK_7; r > RANK_1; r--) &#123;
			if &#40;marked&#91;FILE_A&#93;&#91;r&#93; && FormsFence&#40;FILE_A, r, marked, fence, processed&#41;) &#123;
				fence_formed = 1;
				break;
			&#125;
		&#125;

		if (!fence_formed&#41;
			goto end;

		for &#40;f = FILE_A; f <= FILE_H; f++) &#123;
			for &#40;r = RANK_2; r < RANK_8; r++) &#123;
				if &#40;fence&#91;f&#93;&#91;r&#93;) &#123;
					fence_rank&#91;f&#93; = r;
					break;
				&#125;
			&#125;
		&#125;

		if &#40;RANK&#40;search->pos.king_sq&#91;WHITE&#93;) > fence_rank&#91;FILE&#40;search->pos.king_sq&#91;WHITE&#93;)&#93;)
			goto end;

		for &#40;f = FILE_A; f <= FILE_H; f++) &#123;
			sq = fence_rank&#91;f&#93; * 8 + f - 8;
			for (; sq > H1; sq -= 8&#41; &#123;
				if &#40;search->pos.board&#91;sq&#93; == BPAWN && search->pos.board&#91;sq - 8&#93; == WPAWN&#41;
					dynamic_pawns&#91;n_dyn++&#93; = sq - 8;
			&#125;
		&#125;

		for &#40;i = 0; i < n_dyn; i++) &#123;
			sq = dynamic_pawns&#91;i&#93;;
			f = FILE&#40;sq&#41;;
			r = RANK&#40;sq&#41;;
			if &#40;r > fence_rank&#91;f&#93;) &#123;
				if (!&#40;search->pos.piece_bb&#91;BPAWN&#93; & passed_mask&#91;WHITE&#93;&#91;sq&#93;)) &#123;
					if &#40;FILE&#40;search->pos.king_sq&#91;BLACK&#93;) != f || RANK&#40;search->pos.king_sq&#91;BLACK&#93;) < r&#41;
						goto end;
				&#125;
			&#125;
			else if &#40;fence&#91;f&#93;&#91;r&#93;) &#123;
				if &#40;r >= RANK_6&#41;
					goto end;
				if &#40;search->pos.board&#91;sq + 16&#93; != BPAWN&#41; &#123;
					if &#40;FILE&#40;search->pos.king_sq&#91;BLACK&#93;) != f&#41;
						goto end;
					if &#40;RANK&#40;search->pos.king_sq&#91;BLACK&#93;) < r&#41;
						goto end;
					if (   &#40;f != FILE_A && search->pos.board&#91;sq - 1&#93; != WPAWN&#41;
						|| POPCNT&#40;search->pos.piece_bb&#91;WPAWN&#93; & file_mask&#91;f - 1&#93;) > 1
						|| !fixed_pawn&#91;f - 1&#93;&#91;r&#93;
					    || !fence&#91;f - 1&#93;&#91;r&#93;)
						goto end;
					if (   &#40;f != FILE_H && search->pos.board&#91;sq + 1&#93; != WPAWN&#41;
						|| POPCNT&#40;search->pos.piece_bb&#91;WPAWN&#93; & file_mask&#91;f + 1&#93;) > 1
						|| !fixed_pawn&#91;f + 1&#93;&#91;r&#93;
					    || !fence&#91;f + 1&#93;&#91;r&#93;)
						goto end;
				&#125;
				if &#40;f != FILE_A && search->pos.board&#91;sq + 15&#93; == BPAWN&#41;
					goto end;
				if &#40;f != FILE_H && search->pos.board&#91;sq + 17&#93; == BPAWN&#41;
					goto end;
				if&#40;POPCNT&#40;search->pos.piece_bb&#91;WPAWN&#93; & file_mask&#91;f&#93;) > 1&#41;
					goto end;
			&#125;
			else if &#40;r < fence_rank&#91;f&#93;) &#123;
				sq += 8;
				f = FILE&#40;sq&#41;;
				r = RANK&#40;sq&#41;;
				while (!fence&#91;f&#93;&#91;r&#93;) &#123;
					if &#40;f != FILE_A && search->pos.board&#91;sq + 7&#93; == BPAWN&#41;
						goto end;
					if &#40;f != FILE_H && search->pos.board&#91;sq + 9&#93; == BPAWN&#41;
						goto end;
					if &#40;search->pos.board&#91;sq&#93; == WPAWN&#41;
						break;
					sq += 8;
					f = FILE&#40;sq&#41;;
					r = RANK&#40;sq&#41;;
				&#125;
				if &#40;fence&#91;f&#93;&#91;r&#93; && search->pos.board&#91;sq&#93; == EMPTY&#41; &#123;
					if &#40;r >= RANK_6&#41;
						goto end;
					if &#40;search->pos.board&#91;sq + 16&#93; != BPAWN&#41; &#123;
						if &#40;FILE&#40;search->pos.king_sq&#91;BLACK&#93;) != f&#41;
							goto end;
						if &#40;RANK&#40;search->pos.king_sq&#91;BLACK&#93;) < r&#41;
							goto end;
						if (   &#40;f != FILE_A && search->pos.board&#91;sq - 1&#93; != WPAWN&#41;
							|| POPCNT&#40;search->pos.piece_bb&#91;WPAWN&#93; & file_mask&#91;f - 1&#93;) > 1
							|| !fixed_pawn&#91;f - 1&#93;&#91;r&#93;
						    || !fence&#91;f - 1&#93;&#91;r&#93;)
							goto end;
						if (   &#40;f != FILE_H && search->pos.board&#91;sq + 1&#93; != WPAWN&#41;
							|| POPCNT&#40;search->pos.piece_bb&#91;WPAWN&#93; & file_mask&#91;f + 1&#93;) > 1
							|| !fixed_pawn&#91;f + 1&#93;&#91;r&#93;
						    || !fence&#91;f + 1&#93;&#91;r&#93;)
							goto end;
					&#125;
					if &#40;f != FILE_A && search->pos.board&#91;sq + 15&#93; == BPAWN&#41;
						goto end;
					if &#40;f != FILE_H && search->pos.board&#91;sq + 17&#93; == BPAWN&#41;
						goto end;
					if&#40;POPCNT&#40;search->pos.piece_bb&#91;WPAWN&#93; & file_mask&#91;f&#93;) > 1&#41;
						goto end;
				&#125;
			&#125;
		&#125;
	&#125;
	else &#123;
		for &#40;r = RANK_1; r < RANK_8; r++) &#123;
			for &#40;f = FILE_A; f<= FILE_H; f++) &#123;
				sq = r * 8 + f;
				if &#40;search->pos.board&#91;sq&#93; == BPAWN&#41; &#123;
					if (   &#40;r > RANK_1 && &#40;search->pos.board&#91;sq - 8&#93; == WPAWN || fixed_pawn&#91;f&#93;&#91;r - 1&#93;))
						&& &#40;f == FILE_A || search->pos.board&#91;sq - 9&#93; != WPAWN&#41;
						&& &#40;f == FILE_H || search->pos.board&#91;sq - 7&#93; != WPAWN&#41;) &#123;
						fixed_pawn&#91;f&#93;&#91;r&#93; = 1;
						marked&#91;f&#93;&#91;r&#93; = 1;
					&#125;
					else
						dynamic_pawns&#91;n_dyn++&#93; = sq;
				&#125;
				else if &#40;search->pos.board&#91;sq&#93; == WPAWN&#41; &#123;
					if &#40;f != FILE_A&#41;
						marked&#91;f - 1&#93;&#91;r + 1&#93; = 1;
					if &#40;f != FILE_H&#41;
						marked&#91;f + 1&#93;&#91;r + 1&#93; = 1;
				&#125;
			&#125;
		&#125;

		for &#40;r = RANK_7; r > RANK_1; r--) &#123;
			if &#40;marked&#91;FILE_A&#93;&#91;r&#93; && FormsFence&#40;FILE_A, r, marked, fence, processed&#41;) &#123;
				fence_formed = 1;
				break;
			&#125;
		&#125;

		if (!fence_formed&#41;
			goto end;

		for &#40;f = FILE_A; f <= FILE_H; f++) &#123;
			for &#40;r = RANK_7; r > RANK_1; r--) &#123;
				if &#40;fence&#91;f&#93;&#91;r&#93;) &#123;
					fence_rank&#91;f&#93; = r;
					break;
				&#125;
			&#125;
		&#125;

		if &#40;RANK&#40;search->pos.king_sq&#91;BLACK&#93;) < fence_rank&#91;FILE&#40;search->pos.king_sq&#91;BLACK&#93;)&#93;)
			goto end;

		for &#40;f = FILE_A; f <= FILE_H; f++) &#123;
			sq = fence_rank&#91;f&#93; * 8 + f + 8;
			for (; sq < A8; sq += 8&#41; &#123;
				if &#40;search->pos.board&#91;sq&#93; == WPAWN && search->pos.board&#91;sq + 8&#93; == BPAWN&#41;
					dynamic_pawns&#91;n_dyn++&#93; = sq + 8;
			&#125;
		&#125;

		for &#40;i = 0; i < n_dyn; i++) &#123;
			sq = dynamic_pawns&#91;i&#93;;
			f = FILE&#40;sq&#41;;
			r = RANK&#40;sq&#41;;
			if &#40;r < fence_rank&#91;f&#93;) &#123;
				if (!&#40;search->pos.piece_bb&#91;WPAWN&#93; & passed_mask&#91;BLACK&#93;&#91;sq&#93;)) &#123;
					if &#40;FILE&#40;search->pos.king_sq&#91;WHITE&#93;) != f || RANK&#40;search->pos.king_sq&#91;WHITE&#93;) > r&#41;
						goto end;
				&#125;
			&#125;
			else if &#40;fence&#91;f&#93;&#91;r&#93;) &#123;
				if &#40;r <= RANK_3&#41;
					goto end;
				if &#40;search->pos.board&#91;sq - 16&#93; != WPAWN&#41; &#123;
					if &#40;FILE&#40;search->pos.king_sq&#91;WHITE&#93;) != f&#41;
						goto end;
					if &#40;RANK&#40;search->pos.king_sq&#91;WHITE&#93;) > r&#41;
						goto end;
					if (   &#40;f != FILE_A && search->pos.board&#91;sq - 1&#93; != BPAWN&#41;
 					    || POPCNT&#40;search->pos.piece_bb&#91;BPAWN&#93; & file_mask&#91;f - 1&#93;) > 1
						|| !fixed_pawn&#91;f - 1&#93;&#91;r&#93;
					    || !fence&#91;f - 1&#93;&#91;r&#93;)
						goto end;
					if (   &#40;f != FILE_H && search->pos.board&#91;sq + 1&#93; != BPAWN&#41;
					    || POPCNT&#40;search->pos.piece_bb&#91;BPAWN&#93; & file_mask&#91;f + 1&#93;) > 1
						|| !fixed_pawn&#91;f + 1&#93;&#91;r&#93;
					    || !fence&#91;f + 1&#93;&#91;r&#93;)
						goto end;
				&#125;
				if &#40;f != FILE_A && search->pos.board&#91;sq - 17&#93; == WPAWN&#41;
					goto end;
				if &#40;f != FILE_H && search->pos.board&#91;sq - 15&#93; == WPAWN&#41;
					goto end;
				if &#40;POPCNT&#40;search->pos.piece_bb&#91;BPAWN&#93; & file_mask&#91;f&#93;) > 1&#41;
					goto end;
			&#125;
			else if &#40;r > fence_rank&#91;f&#93;) &#123;
				sq = sq - 8;
				f = FILE&#40;sq&#41;;
				r = RANK&#40;sq&#41;;
				while (!fence&#91;f&#93;&#91;r&#93;) &#123;
					if &#40;f != FILE_A && search->pos.board&#91;sq - 9&#93; == WPAWN&#41;
						goto end;
					if &#40;f != FILE_H && search->pos.board&#91;sq - 7&#93; == WPAWN&#41;
						goto end;
					if &#40;search->pos.board&#91;sq&#93; == BPAWN&#41;
						break;
					sq -= 8;
					f = FILE&#40;sq&#41;;
					r = RANK&#40;sq&#41;;
				&#125;
				if &#40;fence&#91;f&#93;&#91;r&#93; && search->pos.board&#91;sq&#93; == EMPTY&#41; &#123;
					if &#40;r <= RANK_3&#41;
						goto end;
					if &#40;search->pos.board&#91;sq - 16&#93; != WPAWN&#41; &#123;
						if &#40;FILE&#40;search->pos.king_sq&#91;WHITE&#93;) != f&#41;
							goto end;
						if &#40;RANK&#40;search->pos.king_sq&#91;WHITE&#93;) > r&#41;
							goto end;
						if (   &#40;f != FILE_A && search->pos.board&#91;sq - 1&#93; != BPAWN&#41;
							|| POPCNT&#40;search->pos.piece_bb&#91;BPAWN&#93; & file_mask&#91;f - 1&#93;) > 1
							|| !fixed_pawn&#91;f - 1&#93;&#91;r&#93;
						    || !fence&#91;f - 1&#93;&#91;r&#93;)
							goto end;
						if (   &#40;f != FILE_H && search->pos.board&#91;sq + 1&#93; != BPAWN&#41;
							|| POPCNT&#40;search->pos.piece_bb&#91;BPAWN&#93; & file_mask&#91;f + 1&#93;) > 1
							|| !fixed_pawn&#91;f + 1&#93;&#91;r&#93;
						    || !fence&#91;f + 1&#93;&#91;r&#93;)
						    goto end;
					&#125;
					if &#40;f != FILE_A && search->pos.board&#91;sq - 17&#93; == WPAWN&#41;
						goto end;
					if &#40;f != FILE_H && search->pos.board&#91;sq - 15&#93; == WPAWN&#41;
						goto end;
					if &#40;POPCNT&#40;search->pos.piece_bb&#91;BPAWN&#93; & file_mask&#91;f&#93;) > 1&#41;
						goto end;
				&#125;
			&#125;
		&#125;
	&#125;

	blockage = 1;
	
end&#58;
	
	return&#40;blockage&#41;;
&#125;

uaf
Posts: 98
Joined: Sat Jul 31, 2010 6:48 pm
Full name: Ubaldo Andrea Farina
Contact:

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf » Thu Oct 13, 2011 8:08 pm

Sorry, I've just noticed I wrote in the wrong forum. Can a mod please move the thread to the Programming forum?

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Code of Chiron for Detection of Pawn Blockages

Post by rvida » Thu Oct 13, 2011 8:28 pm

Hi,

Thank you for sharing. For comparison there is my (yet unfinished) implementation for Critter using bitboards. Not sure if it works correctly - I wrote this about 2 months ago and did not finish. It does not deal with dynamic pawns yet.

Code: Select all

template <Side side> bool Evaluator&#58;&#58;detect_fence&#40;Bitboard sqmask&#41; &#123;
  
  fence_flag |= sqmask;
  if &#40;sqmask & BB_FileH&#41; &#123;
    fence |= sqmask;
    return true;
  &#125;

  Bitboard f = forward_one<side>&#40;sqmask&#41;;
  if (&#40;blocked & f&#41; && !&#40;fence_flag & f&#41; && detect_fence<side>&#40;f&#41;) &#123;
    fence |= sqmask;
    return true;
  &#125;

  f = sqmask << 1;
  if (&#40;blocked & f&#41; && !&#40;fence_flag & f&#41; && detect_fence<side>&#40;f&#41;) &#123;
    fence |= sqmask;
    return true;
  &#125;

  f = forward_one<Side&#40;side^1&#41;>&#40;sqmask&#41;;
  if (&#40;blocked & f&#41; && !&#40;fence_flag & f&#41; && detect_fence<side>&#40;f&#41;) &#123;
    fence |= sqmask;
    return true;
  &#125;

  return false;
&#125;

template <Side side> bool Evaluator&#58;&#58;pawn_blockade&#40;) &#123;
  const Side xside = Side&#40;side^1&#41;;

  if &#40;attacks&#40;PAWN, side&#41; & board->pawns&#40;xside&#41;)
    return false;

  Bitboard b, fixed;
  fixed = forward_one<xside>&#40;board->pawns&#40;xside&#41;) & board->pawns&#40;side&#41;;
  do &#123;
    b = forward_one<xside>&#40;fixed&#41; & board->pawns&#40;side&#41; & ~fixed;
    fixed |= b;
  &#125; while &#40;b&#41;;

  blocked = fixed | attacks&#40;PAWN, xside&#41;;
  b = blocked & BB_FileA;
  if (!b&#41; return false;
    
  fence = fence_flag = 0;
  do &#123;
    Bitboard p = sq_mask&#40;most_advanced<side>&#40;b&#41;);
    b ^= p;
    if &#40;detect_fence<side>&#40;p&#41;) &#123;
      Bitboard backward = forward_fill<xside>&#40;fence&#41; & ~fence;
      if (!&#40;board->king&#40;side&#41; & backward&#41; || &#40;board->pawns&#40;xside&#41; & backward&#41;) 
        return false;
      Bitboard dynamic = board->pawns&#40;side&#41; & ~fixed;
      return (!dynamic && attacks&#40;KING, side&#41;);
    &#125;
  &#125; while &#40;b&#41;;

  return false;
&#125;


rodolfoleoni
Posts: 263
Joined: Mon Nov 29, 2010 8:16 pm

Re: Code of Chiron for Detection of Pawn Blockages

Post by rodolfoleoni » Thu Oct 13, 2011 10:36 pm

A clear answer to those who thought Chiron could be a derivative...

Bravo Ubaldo!
Rodolfo (The Baron Team)

Ralph Stoesser
Posts: 408
Joined: Sat Mar 06, 2010 8:28 am

Re: Code of Chiron for Detection of Pawn Blockages

Post by Ralph Stoesser » Thu Oct 13, 2011 11:05 pm

An sacrificial offering to soothe the witch hunting deities.;)

Does pawn blockade detection+evaluation increase ELO for a 3000+ engine or is it rather a human's analysis supporting feature?

User avatar
kranium
Posts: 2050
Joined: Thu May 29, 2008 8:43 am

Re: Code of Chiron for Detection of Pawn Blockages

Post by kranium » Fri Oct 14, 2011 12:18 am

Interesting to see that you both use the term 'fence'...
and in a somewhat similar (recursive) fashion to boot!

Thanks for sharing it...

uaf
Posts: 98
Joined: Sat Jul 31, 2010 6:48 pm
Full name: Ubaldo Andrea Farina
Contact:

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf » Fri Oct 14, 2011 4:35 am

rvida wrote:Hi,

Thank you for sharing. For comparison there is my (yet unfinished) implementation for Critter using bitboards. Not sure if it works correctly - I wrote this about 2 months ago and did not finish. It does not deal with dynamic pawns yet.
Thanks. My code for dynamic rules should be ok, I remember I tested it with some other positions besides those of the paper, but I can't be sure 100%.
When I implemented parallel search I had some nice crashes because marked, fence and processed were global :)

uaf
Posts: 98
Joined: Sat Jul 31, 2010 6:48 pm
Full name: Ubaldo Andrea Farina
Contact:

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf » Fri Oct 14, 2011 4:40 am

Ralph Stoesser wrote:An sacrificial offering to soothe the witch hunting deities.;)

Does pawn blockade detection+evaluation increase ELO for a 3000+ engine or is it rather a human's analysis supporting feature?
That's not the reason. I just wanted to make a little contribute. This code doesn't increase engine strength, it's more useful for analysis to make engines look less stupid :)
However, for example, had had Fritz this code back in the 2002 match against Kramnik it would have avoided entering a draw endgame by playing 25. h4 in the first game.

uaf
Posts: 98
Joined: Sat Jul 31, 2010 6:48 pm
Full name: Ubaldo Andrea Farina
Contact:

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf » Fri Oct 14, 2011 4:43 am

kranium wrote:Interesting to see that you both use the term 'fence'...
and in a somewhat similar (recursive) fashion to boot!

Thanks for sharing it...
The reason is that Omid used the word "fence" throughout the paper and the recursive forms_fence() comes from his example code.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Code of Chiron for Detection of Pawn Blockages

Post by stegemma » Fri Oct 14, 2011 7:07 am

Code: Select all

int fixed_pawn&#91;8&#93;&#91;8&#93; = &#123;0&#125;;
This syntax seems very strange to me. Does this instruction just initialize the very first item in the array or does it initialize the whole array to zeroes? I think that this istruction is not correct, maybe a memset should be more portable or i'm wrong?

Post Reply