TalkChess.com

Computer Chess Club
https://talkchess.com/

Code of Chiron for Detection of Pawn Blockages

https://talkchess.com/viewtopic.php?t=40748

Page 1 of 2

Code of Chiron for Detection of Pawn Blockages

Posted: Thu Oct 13, 2011 9:55 pm
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;

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Thu Oct 13, 2011 10:08 pm
by uaf
Sorry, I've just noticed I wrote in the wrong forum. Can a mod please move the thread to the Programming forum?

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Thu Oct 13, 2011 10:28 pm
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;

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 12:36 am
by rodolfoleoni
A clear answer to those who thought Chiron could be a derivative...

Bravo Ubaldo!

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 1:05 am
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?

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 2:18 am
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...

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 6:35 am
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 :)

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 6:40 am
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.

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 6:43 am
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.

Re: Code of Chiron for Detection of Pawn Blockages

Posted: Fri Oct 14, 2011 9:07 am
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?
All times are UTC+02:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited