Direction of travel

[Robert Pope]

I am creating a new program based on 0x88, trying for a bit faster and code this time around.

Question #1:
I want to be able to determine the direction of travel from A to B (e.g. +1,-15,-16,etc). B is always reachable from A via one of the 8 queen rays. Right now I have the following awful code, but there's got to be a better way!

Code: Select all

        xchange=COL(square)-COL(src);
        ychange=ROW(square)-ROW(src);
        if(xchange>0) xchange=1;
        else if&#40;xchange<0&#41; xchange=-1;
        else xchange=0;
        if&#40;ychange>0&#41; ychange=1;
        else if&#40;ychange<0&#41; ychange=-1;
        else ychange=0;
            path=xchange+ychange*16;

Question #2: I used to use a "typedef struct" to hold an array of moves, and then I can pass it easily to functions. Now I've condensed the move down to a single unsigned int. How can I typedef an array of ints so I can declare them like: "movelist moves" instead of "unsigned int moves[200]"?

[Aleks Peshkov]

#1 Table lookup will be faster. dir[from][to] or dir[from-to+0x77]
#2 C-array is just a pointer to the first element. You need extra information to detect the end of array somehow.

[hgm]

The whole idea of 0x88 is that you can use the difference between 'square' and 'src' as a unique indicator for the direction and distance of travel. So you typically use two arrays to tabulate the board step (your 'direction of travel'), and some packed bit flags that allow you to quickly test which piece types can go from src to square.

To your other question, isn't that simply:

typedef unsigned int movelist[200];

[bob]

I am creating a new program based on 0x88, trying for a bit faster and code this time around.

Question #1:
I want to be able to determine the direction of travel from A to B (e.g. +1,-15,-16,etc). B is always reachable from A via one of the 8 queen rays. Right now I have the following awful code, but there's got to be a better way!

Code: Select all

        xchange=COL(square)-COL(src);
        ychange=ROW(square)-ROW(src);
        if(xchange>0) xchange=1;
        else if&#40;xchange<0&#41; xchange=-1;
        else xchange=0;
        if&#40;ychange>0&#41; ychange=1;
        else if&#40;ychange<0&#41; ychange=-1;
        else ychange=0;
            path=xchange+ychange*16;

Question #2: I used to use a "typedef struct" to hold an array of moves, and then I can pass it easily to functions. Now I've condensed the move down to a single unsigned int. How can I typedef an array of ints so I can declare them like: "movelist moves" instead of "unsigned int moves[200]"?

The first issue is why do you care? The final result will be exactly the same...

[Robert Pope]

Maybe I shouldn't care. It just seems cleaner than having to explicitly size the array each time.

[Guetti]

To number 1:

You can do that with a table lookup. Just create and array[256] indexed by
targetSq - fromSq + 128. Then you store the direction of travel there.

Code: Select all

i.e. assuming that for 0x88
a1 ... a8 : 0     1    2     3    4     5    6     7   
h1 ... h8 : 112 113 114 115 116 117 118 119 

a1 -h8 : targetSq (119) - fromSq (0)  + 128 = 247 
so table[247] = 17
h8 - a1: 0 - 119 + 128 = 9
table[9] = -17
etc.

With this, you get the following table:
// vector of movement for captures targetSQ - fromSQ + 128
const signed char attackstep[256] = {0,  0,  0,  0,  0,  0,  0,  0,		// 0 - 7
	 0,-17,  0,  0,  0,  0,  0,  0,-16,  0,  0,  0,  0,  0,  0,-15,		// 8 - 23
	 0,  0,-17,  0,  0,  0,  0,  0,-16,  0,  0,  0,  0,  0,-15,  0,		// 24 - 39
	 0,  0,  0,-17,  0,  0,  0,  0,-16,  0,  0,  0,  0,-15,  0,  0,		// 40
	 0,  0,  0,  0,-17,  0,  0,  0,-16,  0,  0,  0,-15,  0,  0,  0,		// 56
	 0,  0,  0,  0,  0,-17,  0,  0,-16,  0,  0,-15,  0,  0,  0,  0,		// 72
	 0,  0,  0,  0,  0,  0,-17,-33,-16,-31,-15,  0,  0,  0,  0,  0, 	// 88
	 0,  0,  0,  0,  0,  0,-18,-17,-16,-15,-14,  0,  0,  0,  0,  0,		// 104
	 0 ,-1, -1, -1, -1, -1, -1, -1,  0,  1,  1,  1,  1,  1,  1,  1,		// 120
	 0,  0,  0,  0,  0,  0, 14, 15, 16, 17, 18,  0,  0,  0,  0,  0, 	// 136
	 0,  0,  0,  0,  0,  0, 15, 31, 16, 33, 17,  0,  0,  0,  0,  0,		// 152
	 0,  0,  0,  0,  0, 15,  0,  0, 16,  0,  0, 17,  0,  0,  0,  0, 	// 168
	 0,  0,  0,  0, 15,  0,  0,  0, 16,  0,  0,  0, 17,  0,  0,  0, 	// 184
	 0,  0,  0, 15,  0,  0,  0,  0, 16,  0,  0,  0,  0, 17,  0,  0, 	// 200
	 0,  0, 15,  0,  0,  0,  0,  0, 16,  0,  0,  0,  0,  0, 17,  0, 	// 216
	 0, 15,  0,  0,  0,  0,  0,  0, 16,  0,  0,  0,  0,  0,  0, 17,		// 232 - 247
	 0,  0,  0,  0,  0,  0,  0,  0	};									// 248 - 255

Now you can the look up
int track = targetsq-fromsq+128;
direction_of_travel=attackstep[track];

You can also do an additional table attackmove[track] that contains the bits set of the pieces that can reach a targetsq from a fromsq by storeing bitcombinations in it:

Code: Select all

king		= 	100000	=	32
queen		=	010000	=	16
rook		=	001000	=	8
bishop		=	000100	=	4
knight		=	000010	=	2
whitepawn	=	000001	=	1
blackpawn	 = 1000000 	= 	64

example:
--------
pieces that can capture to +1 = K/R/Q = 111000 = 32+16+8 = 56

const char attackmove[256] = {
	 0, 0, 0, 0, 0, 0, 0, 0, 0,20, 0, 0, 0, 0, 0, 0,		//  0 - 15
	24, 0, 0, 0, 0, 0, 0,20, 0, 0,20, 0, 0, 0, 0, 0,		// 16 - 31
	24, 0, 0, 0, 0, 0,20, 0, 0, 0, 0,20, 0, 0, 0, 0,		// 32 - 47
	24, 0, 0, 0, 0,20, 0, 0, 0, 0, 0, 0,20, 0, 0, 0,		// 48 - 63
	24, 0, 0, 0,20, 0, 0, 0, 0, 0, 0, 0, 0,20, 0, 0,		// 64 - 79
	24, 0, 0,20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,20, 2,		// 80 - 95
	24, 2,20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2,116,		// 96 - 111
	56,116, 2, 0, 0, 0, 0, 0, 0,24,24,24,24,24,24,56,		// 112 - 127	
	 0,56,24,24,24,24,24,24, 0, 0, 0, 0, 0, 0, 2,53,		// 128 - 143
	56,53, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,20, 2,		// 144 - 159
	24, 2,20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,20, 0, 0,		// 160 - 175
	24, 0, 0,20, 0, 0, 0, 0, 0, 0, 0, 0,20, 0, 0, 0,		// 176 - 191
	24, 0, 0, 0,20, 0, 0, 0, 0, 0, 0,20, 0, 0, 0, 0,		// 192 - 207
	24, 0, 0, 0, 0,20, 0, 0, 0, 0,20, 0, 0, 0, 0, 0,		// 208 - 223	
	24, 0, 0, 0, 0, 0,20, 0, 0,20, 0, 0, 0, 0, 0, 0,		// 224 - 239
	24, 0, 0, 0, 0, 0, 0,20, 0, 0, 0, 0, 0, 0, 0, 0	};		// 240 - 255	

an then you can probe with
if(attackmove[track] & piece) == piece

thus, to simply see if piece on square fromSq can reach toSq I used the following function in 0x88:

Code: Select all

const char fig_table[13] = {32, 16, 8, 4, 2, 64, 0, 1, 2, 4, 8, 16, 32};

// sliding pieces
const char sliding_mask[13] = {0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0};

bool can_reach(const position* ppos, const int fromSq, const int targetSq)
{
	int way = targetSq - fromSq + 128;
	int piece = fig_table[ppos->board[fromSq]+6];
	int step = attackstep[way];

	if ((attackmove[way] & piece) == piece)
	{
		int iFrom = fromSq;
		for &#40;int i = 0; i < 8; i++)
		&#123;
			iFrom += step;
			if &#40;iFrom == targetSq&#41;
			&#123;
				// Made it to the target
				return true;
			&#125;
                        
			if &#40;ppos->board&#91;iFrom&#93; != 0&#41;
				return false;		// path is blocked
		&#125;
	&#125;
	return false;
&#125;

[hgm]

An alternative, which I use in Joker, is not devote a separate bit to each piece type, but let the bits specify for moves of a certain kind. So I have one bit for distant diagonal moves, one for distant orthogonal moves, one for a single diagonal step forward, one for a single diagonal step backward, etc.

To test if a Bishop can make the move, the bit mask for the Bishop piece type then has all bits set of moves of a kind that a Bishop can make, i.e. diagonal distant, and diagonal contact forward and backward. A Rook has orthogonal distant, and orthogonal contact. And a Queen has all of those together, while a King only has the diagonal and orthogonal single-step bits set.

This way you can also easily limit the test to a subset of the moves, by ANDing with a fixed mask. I use this to test if, e.g. a check is a contact check or a distant check, and only in the latter case you would have to start looking for pieces that you can interpose.

[bob]

Maybe I shouldn't care. It just seems cleaner than having to explicitly size the array each time.

Don't do it that way. Declare one large array. then for each ply, have a pointer into the list to point to the last move for that ply. The next ply will start at that point +1 and have a pointer to the end of it's move list. move_list[5000] will cover any case you can hope to search. And it will be a bit more efficient as well...

[Guetti]

Maybe I shouldn't care. It just seems cleaner than having to explicitly size the array each time.

Don't do it that way. Declare one large array. then for each ply, have a pointer into the list to point to the last move for that ply. The next ply will start at that point +1 and have a pointer to the end of it's move list. move_list[5000] will cover any case you can hope to search. And it will be a bit more efficient as well...

I'm wondering whether there is an advantage of this method except speed? i.e. Does one need to access the movelist of ply x-1 at ply x? Or can I just keep a local movelist in the search for every ply?

[Gerd Isenberg]

I'm wondering whether there is an advantage of this method except speed? i.e. Does one need to access the movelist of ply x-1 at ply x?

It might be interesting to know, whether the move about to make, was already tried two plies before, but obviously failed to cut. Probably considering some "connections" of the two moves played instead with this move about to make. Another late pruning measure?

Or can I just keep a local movelist in the search for every ply?

Since we have ...-cut-all-cut-all... and rarely more than maxmoves/2 at all- and pv-nodes, we'll have some gaps or "defragmentation" of pages and cachelines with two dimensional maxply * maxmovesPerPly arrays. IIRC Dieter Buerssner used local arrays on the stack.