4

I am working on my chess engine in C++ and I went for bitboards to represent the board. It is basically a 64-bit number for which I use the bitset library. I feel the most crucial part in performance comes through the move generation. Earlier I encoded moves as std::string's in a std::vector which would perform moves on a 2-D array. A move has to include at the most basic, A start location, and an end location. That means for my purpose, two numbers would be enough. However, it shall also include two more attributes which are, castling rights(if any) en-passant squares.

One choice is to use a struct to represent two coordinates and the additional two attributes. And then create an array of those moves.

Another choice is to use a 16-bit number to represent a move. For example: 6-bits for the first number, 6-bits for the second. And the remaining for the additional values. And then store them in an array/vector/any container.

Even a std::vector<int> can work.

The main purpose is to be able to iterate through the container efficiently as it will happen multiple times.

What is the best way to encode the move?

Improve this question
4
  • Why are you using a library for a 64 bit number? Use uint64_t. Then measure the difference in time. Commented Sep 9, 2020 at 7:06
  • 2
    Oh really. What can it do that a uint64_t cannot do? Commented Sep 9, 2020 at 7:12
  • 16-bit move solution sounds really tight to me but with more processing required, and it wouldn't let you jump back and forth at random points in the move history without processing all the individual moves. If that latter one is a common case, I really like Kain0_0's 256-bit solution which represents the entire board. Commented Oct 22, 2020 at 2:21
  • @DemonCode We'll I didn't go with the 16-bit solution, I didn't see any clear advantage. I went for a struct Commented Oct 22, 2020 at 5:05

3 Answers 3

Reset to default
3

Questions like this usually boil down to a trade-off between memory usage and speed. A program which uses a highly packed representation for keeping boards in memory will always require some time to unpack the data into a form where it can evaluate and apply the game's semantics. This is especially true when this "unpacking" is done implicitly, by the accessor functions. Keeping boards and moves directly in an unpacked representation hence saves these CPU cycles.

However, in reality, the situation becomes more complex: if your program has to manage lots of boards and moves, and it is going to process millions of them, small-size representations may increase speed, since more boards and moves can be kept in main memory or CPU cache.

As a compromise for such scenarios, it is not uncommon to keep boards in a highly packed representation, unpack them explicitly when they are pulled from the queue or lookup-table (or whatever container your program uses for a tree search), process the unpacked representation to generate new boards and pack the results again to put them into the containers.

As you see, this is going to depend on the gory details of the algorithms of your program, and it may sometimes depend on the hardware on which the program is executed. Hence, if you want maximum speed, there is no way around

  • implementing different approaches, and
  • benchmark them!
Improve this answer
2

Best way?

No clue. It depends on what you are using this encoding for.

For example the best way would for a human would be column/row to column/row.

For a computer? Considering that you have a 64bit board it takes exactly 6 bits to identify a location. Even then extra information such the piece being white/black bishop reduces that to 5 bits. 12bit moves, don't pack them in shorts though, more efficient to pack them into a 64bit/128bit (5moves/10moves respectively).

Alternately it might make more sense to step back and consider the board itself. A move is a state transition from one board-layout to another board layout.

  • 64 locations
  • 6 piece kinds
    • You can encode castling rights by having two rook types, so make that 7 piece kinds.
  • and empty.

That makes 15 unique types. Simplistic 4 bit packing gives a 256 bits for the board.

A game could be described by a list of such boards, which makes resuming a game, or even undoing moves a snap.

If this were a chess playing service (playing many opponents) this can even help with caching decisions.

Is that best? Not sure depends on what you want the move information for.

Improve this answer
3
  • Nice answer as it addresses the need to algorithm optimization over micro-optimization. Commented Sep 10, 2020 at 1:48
  • Shouldn't you also have two King types (also for castling)? Commented Sep 11, 2020 at 19:36
  • @user58697 Why? If the king moves, then both rooks lose their castling ability. If a Rook moves it loses its castling ability. Commented Sep 14, 2020 at 0:57
1

You want to store enough information to make the move and to undo the move. So that is start position, end position, piece taken, and piece converted to at the very least. 6 bit + 6 bit + 3 bit + 2 bit.

If you want to take it to 16 bit at most, store 1 bit for "conversion" set if a pawn moves to the last row, and you can leave out either the 2 bit what the pawn was converted to, or you leave out 3 bits of the "end position" because it must be on the last row.

Improve this answer
1
  • How can I store these moves? Does a std::vector sound like a good choice? Commented Sep 9, 2020 at 7:13