Move Tables - explain as if I'm five.

[ZirconiumX]

From what I can tell (I may be wrong), there are two schools of thought on Move Tables:

• Those that use the Table to lookup to squares directly - Gerd Isenberg's CLL, Bruce Moreland's approach.
• Those that use the Table to lookup to squares indirectly - Vincent Diepeveen's vector of squares (from what I can tell).

I've attempted to implement the first one, and it either (with a dense index list) produced incorrect results or (with a conditional linked list) wouldn't compile.

Vincent's generator skeleton is rather vague - so I can't quite tell what all the arrays do. (I initially thought that ipiecepos[][] was a vector of piece moves - and then it appeared in pawn generation)

So, could someone at least show me how a correct generator would look like for either of those methods?

FWIW, here's my move table initialization routine (called twice)

Code: Select all

int init_move_table()
{
	int i, j, k, l;

	for (i = 0; i < 64; i++) board_main[i] = NP;

	i = 0;
	for (j = 0; j < 64; j++) {
		mt_head[0][j] = (mt_node *)mt_table[i];
		k = j + 7;
		while (k < 64 && k >= 0 && (k&7) != 7) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = *mt_table[move_dirs[NW][j]];
			k += 7;
			i++;
		}
		move_dirs[NW][i] = i;
		k = j + 9;
		while (k < 64 && k >= 0 && (k&7) != 0) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = *mt_table[move_dirs[NE][j]];
			k += 9;
			i++;
		}
		move_dirs[NE][i] = i;
		k = j - 7;
		while (k < 64 && k >= 0 && (k&7) != 7) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = *mt_table[move_dirs[SW][j]];
			k -= 7;
			i++;
		}
		move_dirs[SW][i] = i;
		k = j - 9;
		while (k < 64 && k >= 0 && (k&7) != 0) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = NULL;
			k -= 9;
			i++;
		}
		move_dirs[SE][i] = i;

		move_head[1][j] = i;
		l = j - (j>>3);
		k = j + 8;
		while (k < 64 && k >= 0 && k >= l) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = *mt_table[move_dirs[N][j]];
			k += 8;
			i++;
		}
		move_dirs[N][i] = i;
		k = j + 1;
		while (k < 64 && k >= 0 && k <= l) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = *mt_table[move_dirs[W][j]];
			k += 1;
			i++;
		}
		move_dirs[W][i] = i;
		k = j - 8;
		while (k < 64 && k >= 0) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = *mt_table[move_dirs[S][j]];
			k -= 8;
			i++;
		}
		move_dirs[S][i] = i;
		k = j - 1;
		while (k < 64 && k >= 0 && (k >> 3) < 7) {
			mt_table[i].sq = k;
			mt_table[i].next[0] = *mt_table[i + 1];
			mt_table[i].next[1] = NULL;
			k -= 1;
			i++;
		}
		move_dirs[E][i] = i;
	}
	return i;
}

Any help would be appreciated.

(I won't be convinced to try bitboards or an array type)

Matthew:out

[ZirconiumX]

Fail - it usually helps to show how it's being probed.

Code: Select all

int gen_moves(int is_rook, uint32_t * stack, int offset, int from)
{
	mt_node node;
	int piece;
	int side;
	int to;
	int x;

	x = offset;
	side = WHITE;

	node = move_head[is_rook][from];
	do {
		to = node->to;
		stack[x] = from | to << 6;
		x       += !(board[to] & side);
		node     = node->next[board[to] != NP];
	} while (node);

	return x;
}

Matthew:out

[mar]

Hi Matthew,

Not sure whether it helps, I believe the table idea comes from old GNUChess, some scandinavian guy (I think - don't remember) described it as he wanted to build a hardware movegenerator.
The (naive) idea behind it (as I understand it - [shameless plug] I implemented it in Heretic - an experimental engine to play Capablanca chess), is that you have a table for each piece type.
You store indices to next square to examine, for sliders you also store index to skip to the next ray.
So whenever you encounter a blocked square you either generate a capture and skip or ignore it and skip (or use next for non-sliders). For empty square you simply go to next square in chain.
In case you would be interested, the actual implementation (tables.cpp and tables.h) is here: http://www.mediafire.com/download.php?ohxab35ckj84dsy (no guarantee that the implementation is very clean and readable)
I'm sure Vincent came up with something much better though.
Hope it helps.

Martin

[hgm]

In Vincent's code the moves are put into a branched linked list (so a tree, actually), where each node has pointer links to two successors (node->next[0] and node->next[1]). The idea is that next[0] is the link to the next square the piece must try to move to when the current square is empty (for sliders this is usually the next square on the current ray), while next[1] is the next to try when the current square is occupied (the first square of the next ray). By doing this (and making separate lists for every starting square) you can anticipate whether the piece will hit the edge, and thus won't waste time on testing for that. The lists are constructed such that it will never happen, and you go automatically to the next ray when the current one reaches is an edge square.

Vincent's code is aimed at using no branch instructions (which could give costly CPU pipe-line stalls on mis-prediction). So he always pushes the move on the (move) stack, even if it is an invalid one because the to-square was occupied by an own piece. But he only increments the stack-pointer when it was valid, by adding a 0 or 1 to it depending on the nature of the obstacle. The idea is that i386 compilers would translate expressions like !(board[to]&side) by conditional set instructions, which copy condition codes (in this case the one that flags an ALU result as zero) to an 8-bit CPU register as 0 or 1, thus not using a branch instruction.

I must admit that I tried these techniques in my perft utility, and was never able to achieve a speedup with them. Using linked lists always gave me a slowdown. Probably because the critical path of the code stepping through the list is very long, and contains memory fetches, which are of comparatively long latency.

[mar]

A long time ago I tried to write a generator which did the same but generated many C functions,
unrolling everything for each piece and square (thus skipping table fetches) - old 386 habit.
I have doubts that it was wise as it would wreck the instruction cache, so hard to say.

[mar]

Code: Select all

.
.
.
		while (k < 64 && k >= 0 && (k&7) != 7) {
}

Although it's pointless in this particular case as it's a table init routine, a little trick:
whenever you need an interval (integer) like 0 <= i < n,
you can use a single unsigned comparison instead (unsigned)i < (unsigned)n.
Or simply use unsigned ints if possible.

[Gerd Isenberg]

Fail - it usually helps to show how it's being probed.

Code: Select all

int gen_moves(int is_rook, uint32_t * stack, int offset, int from)
{
	mt_node node;
	int piece;
	int side;
	int to;
	int x;

	x = offset;
	side = WHITE;

	node = move_head[is_rook][from];
	do {
		to = node->to;
		stack[x] = from | to << 6;
		x       += !(board[to] & side);
		node     = node->next[board[to] != NP];
	} while (node);

	return x;
}

Matthew:out

Probe code looks fine to me. Despite your init code looks quite nice, I guess the error is inside the initialization, but I am too lazy and short on time to check it for you. You may print out moves and variables inside the loop, to find the errors.

Good luck,
Gerd

[Sven]

Any help would be appreciated.

Fix your directions. If NW is +7 (which is +8-1) then SW must be -9 (-8-1) and W must be -1, and so on. I think your init code has that wrong.

EDIT: The following "canonical" definitions might help to avoid this type of bugs:

Code: Select all

int const JumpN  = +8;
int const JumpE  = +1;
int const JumpS  = -JumpN;
int const JumpW  = -JumpE;
int const JumpNW = JumpN+JumpW;
int const JumpNE = JumpN+JumpE;
int const JumpSW = JumpS+JumpW;
int const JumpSE = JumpS+JumpE;

plus always using these constants instead of the hard-coded integers, of course.

Sven

[hgm]

Isn't jumpN = +16 in Fruit?

[Sven]

Isn't jumpN = +16 in Fruit?

Yes, in Fruit, but that is currently not the base for Matthew AFAIK. At least I can say that his move table implementation shown above is using square numbers 0..63.

Sven