Faster Movelist in Mailslot Engines?

[Ras]

You know connor_mcmonigle told me that all sorting algorithms are O(1)

No, he didn't. It just seems that way to you because you fail to understand elementary math.

[dangi12012]

I guess you are missing that to make alpha-beta pruning work effectively, the order in which the moves are searched is crucial. So the moves along the ray are unlikely to be searched sequentially. This is the main reason for putting them in a move list, and not search them immediately as they get out of the move generator. You can then first sort the list by suspected quality of the moves, and then search them starting with the suspected best.

So if there is a capture at the end of the ray you would first want to search that, and all other captures, before you get to playing any of the other moves along the ray. And the latter would probably be sorted by their history score, which could be completely different. So that the 2nd move along the ray most be searched 12th, the 4th move 20th and the first move 28th.

Yes I see. But I still remove half of the algorithm?

Because in one I have one loop to generate - and one move to sort.
In the other one I just memcpy everything over (which is a faster loop i guess because its static and preprepared) - and one move to sort?

[leanchess]

I'm not sure if this is relevant, but do your make/unmake contain ifs?

I believe I just created branchless make/unmake using 64-bit moves.

[dangi12012]

I'm not sure if this is relevant, but do your make/unmake contain ifs?

I believe I just created branchless make/unmake using 64-bit moves.

The code in my signature does not - there the callstack itself is the unmake machinery.
My mailslot code needs unmake.

I am very interested can you show your branchless unmake?
How would that work with special move like castling? Surely you would have an if there. (or a cool jumptable)

[leanchess]

I'm not sure if this is relevant, but do your make/unmake contain ifs?

I believe I just created branchless make/unmake using 64-bit moves.

The code in my signature does not - there the callstack itself is the unmake machinery.
My mailslot code needs unmake.

I'm not sure if out mailslots are compatible
My implementation is 0x88 with 2x16 piece lists.

How would that work with special move like castling? Surely you would have an if there. (or a cool jumptable)

Nope. There is one ternary, which shouldn't compile into a branch (or otherwise could be transformed into a multiply).

Castling should be fine. I'm currently having trouble with one edge case, namely capture combined with promotion, but that seems solvable.

Edit: I am assuming that the move generator is the source of knowledge for all the squares/indices.

[dangi12012]

I'm not sure if this is relevant, but do your make/unmake contain ifs?

I believe I just created branchless make/unmake using 64-bit moves.

The code in my signature does not - there the callstack itself is the unmake machinery.
My mailslot code needs unmake.

I'm not sure if out mailslots are compatible
My implementation is 0x88 with 2x16 piece lists.

How would that work with special move like castling? Surely you would have an if there. (or a cool jumptable)

Nope. There is one ternary, which shouldn't compile into a branch (or otherwise could be transformed into a multiply).

Castling should be fine. I'm currently having trouble with one edge case, namely capture combined with promotion, but that seems solvable.

Edit: I am assuming that the move generator is the source of knowledge for all the squares/indices.

Can you show the code? The format of moves is independent of board formats so it should be fine
Yes. From/To as integer should be known.

[leanchess]

I still need to fix some bugs. In the meantime, here's move_t (which I believe is more or less final):

Code: Select all

typedef union {
	struct {
		uint8_t file:    3;
		uint8_t invalid: 1;
		uint8_t rank:    3;
		uint8_t moved:   1;
		uint8_t index:   4;
		uint8_t ep_file: 4;
	};
	uint16_t value;
} move_prim_from_t;

typedef union {
	struct {
		uint8_t file:    3;
		uint8_t invalid: 1;
		uint8_t rank:    3;
		uint8_t nep:     1; //1 if no e.p. square
		uint8_t index:   4;
		uint8_t type:    3;
		uint8_t moved:   1;
	};
	uint16_t value;
} move_prim_to_t;

typedef union {
	struct {
		uint8_t file:    3;
		uint8_t invalid: 1;
		uint8_t rank:    3;
		uint8_t capture: 1;
		uint8_t index:   4;
		uint8_t type:    3;
		uint8_t moved:   1;
	};
	uint16_t value;
} move_sec_item_t;

typedef struct {
	struct {
		move_prim_from_t from;
		move_prim_to_t   to;
	} prim;
	struct {
		move_sec_item_t from;
		move_sec_item_t to;
	} sec;
} move_t;

[dangi12012]

You want to fix some bugs in the actual make/unmake move. I understand - please show it when its done im very interested!
From the structs I cant see the interesting part yet

What I can add that file/rank maybe dont need to be saved at all?
They can be very very cheaply be calculated by index >> 3 and index & 7
which is faster than the two operations a bitfield uses internally (shift + mask)

Greetings!

[leanchess]

You want to fix some bugs in the actual make/unmake move. I understand - please show it when its done im very interested!
From the structs I cant see the interesting part yet

What I can add that file/rank maybe dont need to be saved at all?
They can be very very cheaply be calculated by index >> 3 and index & 7
which is faster than the two operations a bitfield uses internally (shift + mask)

Greetings!

1. Those are indices into the piecelists.
2. The bitfields are largely for information; I'm mostly working directly with the .value fields.

[dangi12012]

You want to fix some bugs in the actual make/unmake move. I understand - please show it when its done im very interested!
From the structs I cant see the interesting part yet

What I can add that file/rank maybe dont need to be saved at all?
They can be very very cheaply be calculated by index >> 3 and index & 7
which is faster than the two operations a bitfield uses internally (shift + mask)

Greetings!

1. Those are indices into the piecelists.
2. The bitfields are largely for information; I'm mostly working directly with the .value fields.

Ahhh I may get it now. You are not using the bitfields inside if statements. You are using the 16 bit value table as a direct jumptable?
Thats nice.

There are so many possibilities there. You can write your code normally - but replace all if with constexpr if statements and then you have a template generate all 2^16 possibilities and put them into a function pointer table (i think a few bits are not needed)

That would make castling, enpessant, promotion an instant inlineable operation without branches.