Code of Chiron for Detection of Pawn Blockages

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

Moderators: hgm, Rebel, chrisw

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

Code of Chiron for Detection of Pawn Blockages

Post by uaf »

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;
Top
uaf
Posts: 98
Joined: Sat Jul 31, 2010 8:48 pm
Full name: Ubaldo Andrea Farina

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf »

Sorry, I've just noticed I wrote in the wrong forum. Can a mod please move the thread to the Programming forum?
Top
User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 12:00 pm
Location: Slovakia, EU

Re: Code of Chiron for Detection of Pawn Blockages

Post by rvida »

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;
Top
rodolfoleoni
Posts: 263
Joined: Mon Nov 29, 2010 9:16 pm

Re: Code of Chiron for Detection of Pawn Blockages

Post by rodolfoleoni »

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

Bravo Ubaldo!
Rodolfo (The Baron Team)
Top
Ralph Stoesser
Posts: 408
Joined: Sat Mar 06, 2010 9:28 am

Re: Code of Chiron for Detection of Pawn Blockages

Post by Ralph Stoesser »

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?
Top
kranium
Posts: 2129
Joined: Thu May 29, 2008 10:43 am

Re: Code of Chiron for Detection of Pawn Blockages

Post by kranium »

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

Thanks for sharing it...
Top
uaf
Posts: 98
Joined: Sat Jul 31, 2010 8:48 pm
Full name: Ubaldo Andrea Farina

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf »

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 :)
Top
uaf
Posts: 98
Joined: Sat Jul 31, 2010 8:48 pm
Full name: Ubaldo Andrea Farina

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf »

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.
Top
uaf
Posts: 98
Joined: Sat Jul 31, 2010 8:48 pm
Full name: Ubaldo Andrea Farina

Re: Code of Chiron for Detection of Pawn Blockages

Post by uaf »

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.
Top
User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 10:05 pm
Location: Italy
Full name: Stefano Gemma

Re: Code of Chiron for Detection of Pawn Blockages

Post by stegemma »

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?
Top

Return to “Computer Chess Club: General Topics”