Determining From squares

[Edmund]

SAN was never meant as an encoding easy to read for machines ..
having said that, below you find my san to internal representation converter. I use bitwise instructions to find the possible target squares. Maybe it helps:

Code: Select all

int algeb_san(char * a, U16 * moves) {

	int from, to, prom;
	int counter = -1;
	U64 orig;

	for (;;) {

		for (;;a++) {
			if (!(*a) || (*a == ';')) return counter + 1;
			if (strchr("O0KQRBNabcdefgh", a[0])) break;
		}

		counter++;

		if (strstr(a, "O-O-O") || strstr(a, "0-0-0")) {
			if (b_global.d.stm == WHITE) 	moves[counter] = MOVE_SET(E1, C1, 0);
			else							moves[counter] = MOVE_SET(E8, C8, 0);
			continue;
		}
		else if (strstr(a, "O-O") || strstr(a, "0-0")) {
			if (b_global.d.stm == WHITE)	moves[counter] = MOVE_SET(E1, G1, 0);
			else							moves[counter] = MOVE_SET(E8, G8, 0);
			continue;
		}

		from = 0;
		to	 = 0;
		prom = 0;

		if (strchr("abcdefgh", a[0])) {
			if (a[1] == 'x') {
				to = algeb_conv_a1_64(a + 2);
				from = 7 - a[0] + 'a';
				from = bitScanForward(mgen_att_P(!b_global.d.stm, bbSQ[to]) & bbCOL[from]);
				if (a[4] == '=') prom = a[5];
				a+=3;
			} else {
				to = algeb_conv_a1_64(a);
				if (b_global.d.stm == WHITE) {
					if		(shift_S (bbSQ[to]) & b_global.bbPC[b_global.d.stm][PIECE_P]) from = to - 8;
					else if (shift_SS(bbSQ[to]) & b_global.bbPC[b_global.d.stm][PIECE_P]) from = to - 16;
					else	return -1;
				} else {
					if		(shift_N (bbSQ[to]) & b_global.bbPC[b_global.d.stm][PIECE_P]) from = to + 8;
					else if (shift_NN(bbSQ[to]) & b_global.bbPC[b_global.d.stm][PIECE_P]) from = to + 16;
					else	return -1;
				}
				if (a[2] == '=') prom = a[3];
				a+=2;
			}

			switch (prom) {
			case 0:		moves[counter] = MOVE_SET(from, to, 0); break;
			case 'Q':	moves[counter] = MOVE_SET(from, to, PIECE_Q); break;
			case 'R':	moves[counter] = MOVE_SET(from, to, PIECE_R); break;
			case 'B':	moves[counter] = MOVE_SET(from, to, PIECE_B); break;
			case 'N':	moves[counter] = MOVE_SET(from, to, PIECE_N); break;
			}

			if (prom) a+=2;

			continue;
		}

		if (strchr("KQRBN", a[0])) {
			int piece = 0;
			switch (a[0]) {
			case 'K':	piece = PIECE_K; break;
			case 'Q':	piece = PIECE_Q; break;
			case 'R':	piece = PIECE_R; break;
			case 'B':	piece = PIECE_B; break;
			case 'N':	piece = PIECE_N; break;
			}

			a++;
			if (a[0] == 'x') a++;

			orig = bbFULL;

			if (strchr("12345678", a[0])) {
				orig &= bbROW[a[0]-'1'];
				a++;
			}

			if (strchr("abcdefgh", a[0])) {
				if (strchr("12345678", a[1])) {
					if (a[2] && strchr("abcdefgh", a[2])) {
						from = algeb_conv_a1_64(a);
						to   = algeb_conv_a1_64(a+2);
						moves[counter] = MOVE_SET(from, to, 0);
						a+=4;
						continue;
					}
					to = algeb_conv_a1_64(a);
					a+=2;
				}
				else if (strchr("abcdefgh", a[1])) {
					orig &= bbCOL[7 - a[0] + 'a'];
					to    = algeb_conv_a1_64(a+1);
					a+=3;
				}
				else return -1;

				switch (piece) {
				case PIECE_K:	orig &= b_global.bbPC[b_global.d.stm][piece] & bbATT[piece][to]; break;
				case PIECE_Q:	orig &= b_global.bbPC[b_global.d.stm][piece] & mgen_att_Q(to, b_global.bbCO[0] | b_global.bbCO[1]); break;
				case PIECE_R:	orig &= b_global.bbPC[b_global.d.stm][piece] & mgen_att_R(to, b_global.bbCO[0] | b_global.bbCO[1]); break;
				case PIECE_B:	orig &= b_global.bbPC[b_global.d.stm][piece] & mgen_att_B(to, b_global.bbCO[0] | b_global.bbCO[1]); break;
				case PIECE_N:	orig &= b_global.bbPC[b_global.d.stm][piece] & bbATT[piece][to]; break;
				}

				if (piece == PIECE_K) {
					if (!orig) return -1;
					from = bitScanForward(orig);
					moves[counter] = MOVE_SET(from, to, 0);
					continue;
				}

				while (orig) {
					from = bitScanForward(orig);
					orig ^= bbSQ[from];

					if (mgen_att_R(getKing(&b_global, b_global.d.stm), (b_global.bbCO[0] | b_global.bbCO[1]) ^ bbSQ[from] ^ bbSQ[to]) & (b_global.bbPC[!b_global.d.stm][PIECE_R] | b_global.bbPC[!b_global.d.stm][PIECE_Q])) continue;
					if (mgen_att_B(getKing(&b_global, b_global.d.stm), (b_global.bbCO[0] | b_global.bbCO[1]) ^ bbSQ[from] ^ bbSQ[to]) & (b_global.bbPC[!b_global.d.stm][PIECE_B] | b_global.bbPC[!b_global.d.stm][PIECE_Q])) continue;
					moves[counter] = MOVE_SET(from, to, 0);
					continue;
				}
			}
		}
	}
}

[sje]

Let me add that to get the Move->SAN encoder working

Anyhow, in case you really need a "move to SAN" encoder then take a look at move_to_san() function in:

https://github.com/mcostalba/Stockfish/ ... c/move.cpp

This is by far the best you can find around

Oh really? That code has a disambiguation bug. Can you see it? Hint: It is related to pins.

[mcostalba]

Oh really? That code has a disambiguation bug. Can you see it? Hint: It is related to pins.

I knew my post would have gathered some useful feedback, but never hoped for a bug report !

Thanks, it is fixed now. (just click again on the above link)

[hgm]

I'm looking for an efficient algorithm to determine the "from" square given a move such as "Rc3".

Usually this is done by maintaining a piece list, recording the squares each piece is currently on. Then when you ecounter Rc3 you only have to run through the Rook section of the piece lists to see which Rook is aligned with c3 ('0x88 test'). To efficiently update the list on piece capture, you can store piece numbers rather than piece types on the board.

It depends a little on your goal: do you just want to interpret PGN that can beassumed to be OK, or do you want to test it for legality. Only in the latter case you would always have to check if the path is unblocked. Otherwise, ifthere is only a single Rook, or the second Rook is not aligned, you can immediatey assume it must be the aligned Rook which is moved. If both Rooks are aligneda have an unblocked path, one could still be pinned, so you would have to test for checks.

This is the strategy I use for position search in WinBoard: just do quick and dirty parsing of the PGN of all games in the file, never minding illegal moves except in the very rare case where this is needed for disambiguation, to select games that could contain the sought position. Then,when the user actually selects one of these games, the game is pedantically parsed, and only then illegal moves will produce an error message.

[sje]

Oh really? That code has a disambiguation bug. Can you see it? Hint: It is related to pins.

I knew my post would have gathered some useful feedback, but never hoped for a bug report !

Thanks, it is fixed now. (just click again on the above link)

Not having a copy of Stockfish handy, I'll leave it for you to test. Try this:
[d]
The moves are:

Code: Select all

Bd2 Be2 Be3 Bf4 Bg5 Bh6 Kd2 Ke2 Ne2 Nf3 Nh3 Qd2 Qe2 Qf3 Qg4 Qh5 Rb1 a3 a4 b3 d4 f3 f4 g3 g4 h3 h4

Note that it's Ne2 and not Nge2.

[mcostalba]

Code: Select all

a3, b3, f3, g3, h3, d4, a4, f4, g4, h4, Ke2, Kd2, Qh5, Qg4, Qf3, Ne2, Nf3, Nh3, Bd2, Be3, Bf4, Bg5, Bh6, Be2, Rb1, Qd2, Qe2, 

[whittenizer]

Morning,

I really appreciate everyones comments. I'll reply here for all the other comments. After reading what everyone has to say, and I've taken a look at move.cpp(not a C++ person though), this has spawnd new ideas. I'm going to refactor my code a bit, and will come back to you all with my results when its somewhat stable.

This is such an awesome site to collaborate.

Thanks again all,

David

[whittenizer]

Ok, lets take this position:

__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __
R __ n __ __ P R __
__ __ __ __ __ __ __ __
__ __ __ __ __ __ __ __

Sorry for my crude board, couldn't upload an image for some reason, Anyways, just had this idea, still in theory mode mind ya, but lets say we have a pgn move such as "Rxc3". Ok, well there are two possible from squares here; a3 and g3. I'm going to be testing two paths here. Lets take the a3 path first. If we start at the top left and work our way to the right, a3 would be 41. So c3 would be 43, etc. The test would be something like this:

if ((41 + 43) == ((41 + 43) + all squares between 41 and 43)) { fromsq = 41 }

So, we can see that the only square between 41 and 43 is 42, and its blank so we dont count that, so they match, and we exit out with our square. So, let's tke the other path. The rook on g3 would be 47. So our test would be:

if ((43 + 47) == ((43 + 47) + 46)) { fromsq = 47 }

"46" in this case is the only square that has a value between 43 and 47. Obviously this check fails.

Given all of this, I would need to keep track of occupied squares total value for each path so the above code would be this:

if ((43 + 47) == (43 + 47 + totaloccupiedvalue)) { fromsq = 47 }

So, the loop would be something like this:

foreach(Square sq in posiblesquares)
{
if (IsFromSquare(sq)) { from = sq; break;}
}

Hopefully this makes sense. I'mgoing to see how this turns out.

Thanks for the ears,

David[/list]

[whittenizer]

Forgot about the pinned piece. I'll incorporate that into my checks.

Once again, thanks all.

David

[hgm]

People invented the 0x88 board for this: in stead of 8x8 you use 16x8, using only the left half. So the squares are not contiguously numbered, but as a raster scan in the direction of the 16-wide dimesion. You can then subtract the from and to-square numbers to get the move step,without any confusion for moves that cross the left and right board edge.
By using (to - from) as index in a prepared table, you can check for aligment or proximity (e.g. mark diagonalmoves with the 1 bit, orthogonalmoves with the 2 bit, etc.) In another table you can look up (also as function of to - from) the elementary step belonging to the direction (+1 or -1 in your example), and then scan over the board starting at the from-square using that step until you reach the to-square (or an obstruction).