int vs Board: Move generator

[JohnWoe]

Somebody told that int is a much faster way to generate moves.
So I tested int movegen in Sapeli: 6 bits for from/to + 4 bits for type. Fits in int.
And produces correct perft.

The results. It's actually much slower. Yes it's stronger in search. But it doesn't generate any faster.

int (copy/make):

Code: Select all

16 warnings generated.
depth 0 nodes 1 time 0.000 mnps 0.001
depth 1 nodes 20 time 0.000 mnps 0.020
depth 2 nodes 400 time 0.000 mnps 0.400
depth 3 nodes 8902 time 0.000 mnps 8.902
depth 4 nodes 197281 time 0.006 mnps 28.183
depth 5 nodes 4865609 time 0.211 mnps 22.951
depth 6 nodes 119060324 time 4.553 mnps 26.144

Board (just make):

Code: Select all

sapeli -perft 6
depth 0 nodes 1 time 0.000 mnps 0.001
depth 1 nodes 20 time 0.000 mnps 0.020
depth 2 nodes 400 time 0.000 mnps 0.400
depth 3 nodes 8902 time 0.000 mnps 8.902
depth 4 nodes 197281 time 0.005 mnps 32.880
depth 5 nodes 4865609 time 0.126 mnps 38.312
depth 6 nodes 119060324 time 3.020 mnps 39.411

[Sven]

What exactly is "Board (just make)"? I get the impression that, despite your description, the difference is not just how a move is stored (in 16 bit vs. in a struct of three or more integers) but also what the strategy for unmake is (restore board from stack vs. explicit unmake). If that is the case then I suggest to also measure both differences separately.

In general I do not think that storing a move in 16 bit and dealing efficiently with it should slow down perft or search. In contrast to that, a copy/make vs. make/unmake comparison depends on the engine and its data structures.

[syzygy]

Somebody told that int is a much faster way to generate moves.
So I tested int movegen in Sapeli: 6 bits for from/to + 4 bits for type. Fits in int.

What are you comparing to?

int (copy/make):

Board (just make):

Are you comparing two move representations, one of which fits in an int and the other maybe not, or are you comparing copy/make with make?

[JohnWoe]

Somebody told that int is a much faster way to generate moves.
So I tested int movegen in Sapeli: 6 bits for from/to + 4 bits for type. Fits in int.

What are you comparing to?

int (copy/make):

Board (just make):

Are you comparing two move representations, one of which fits in an int and the other maybe not, or are you comparing copy/make with make?

Just perft tests. I'm always looking for speedups.
ints were pseudo legal moves. Boards are legal. You only need from+to+type for int.
I have 1 global board. I MakeMove(move) and if legal proceed. Then copy board back. Those extra operations cost time.

Board is copied and move applied. So kinda copy/make too. UnmakeMove() would be faster but a lot harder to implement.
But the results were so disappointing I didn't proceed. I know that when you get a cut-off, then you save time. Plus other tricks.

[hgm]

I don't think you can make such general statements. It depends entirely on how you do it. I always use a move representation that fits in an int, but a struct of four char (fromSqr, toSqr, promoType, sortKey) fits in an int too. The compiler would often treat one or the other, e.g. if I write to = moveStack[nr] >> 8 & 255 it would compile to a simple memory load of a byte, and there would be no shift or AND operation at all. It would behave exactly as if it was just loading one field of the four-char struct.

By storing the sort key in the MSB of the int, I can do very fast comparison and swapping of moves during sorting. Perft presumably does no sorting at all.

It also depends on how you exactly you generate the moves. If you would really need to shift the fromSqr and toSquare to a location in the int for every move that would be slower than just doing a one-time shift of the fromSqr when you start generating for that piece, and then just add the toSqr to it for every move, because you put that in the lowest bits.

[syzygy]

Somebody told that int is a much faster way to generate moves.
So I tested int movegen in Sapeli: 6 bits for from/to + 4 bits for type. Fits in int.

What are you comparing to?

int (copy/make):

Board (just make):

Are you comparing two move representations, one of which fits in an int and the other maybe not, or are you comparing copy/make with make?

Just perft tests. I'm always looking for speedups.
ints were pseudo legal moves. Boards are legal. You only need from+to+type for int.
I have 1 global board. I MakeMove(move) and if legal proceed. Then copy board back. Those extra operations cost time.

Board is copied and move applied. So kinda copy/make too. UnmakeMove() would be faster but a lot harder to implement.
But the results were so disappointing I didn't proceed. I know that when you get a cut-off, then you save time. Plus other tricks.

Aren't you using a jargon here that is specific to your engine?
Do you expect us to understand that ints are pseudolegal moves and Boards are legal moves?

So now I am guessing that you are comparing:
1. checking move legality before making the move; and
2. checking move legality by making the move and testing if the king is in check.

An engine like Stockfish uses method 1. It is a bit more complicated to implement but it is faster.