Move-Finding, The Engine Way
Finding moves never seemed so difficult. .(Cropped; https://www.flickr.com/photos/striatic/58687301, https://creativecommons.org/licenses/by/2.0/)

Move-Finding, The Engine Way

the_real_greco
the_real_greco
|
11

In a previous post I looked at how engines represent positions with bitboards. (If you haven't read that, you should!). Having a full set of 12 bitboards lets you know where all the pieces are... but that isn't the end of the story. The next step is figuring out what moves are legal in a given position. Hopefully this process will give you a deeper understanding not only of chess engines, but also of the pieces themselves.

You might not have realized it, but there are three types of chess pieces. Kings and knights move independently of the opponents' pieces (checks notwithstanding); they cannot be blocked, and if they encounter a hostile piece they simply capture it. Queens, rooks, and bishops are what we call sliders- their movement can be blocked by friendly pieces, and must halt upon capturing a hostile piece. Pawns are a bizarre combination of the first two types.

In this post I'll look first at how modern engines find king and knight moves. That process is fairly simple. Then I'll look at how they handle sliders using magic bitboards; that process is more involved.


Sometimes there's just too much information to memorize. (Pixabay)

One thing to keep in mind is that engines constantly make a trade-off between time (how long it takes the CPU to complete a task) and space (how much memory the engine would need to skip that computation). A good analogy is with opening books: It saves a lot of time to have the first few moves of the game memorized; at a certain point, however, it stops being worthwhile to memorize every line and you must begin to think.

Engines do the same thing with calculating all moves in a position. Pay attention to when they're looking something up in a table or index (space and memory) and when they're doing logical operations (time and computation). In recent years memory has become extremely inexpensive; for that reason modern engines are designed to memorize more (and calculate less) during move generation. 


Now, onto the pieces! Hopefully it makes sense when I said that king and knight moves are very similar. Since their sets of attacked squares depends only on their location (and nothing else), an engine generates  64 king attack-sets and 64 knight attack-sets. This is done only once, when your engine starts; after that, the attack-sets are stored for later access.

For brevity's sake, I'll work only with knights. The attack-sets for knights on d3 and a2, respectively:

Stored attack-sets for knights on d3 and a2.
When your engine runs across a knight, it simply looks up the corresponding attack-set for that knight on its specific square (remember, there are only 64 of them!). It then uses a simple logical function with the collection of friendly-piece bitboards (hostile pieces are ignored, since they can be captured anyway). For the knight on d3 in the following position...

... we use the functions AND and NOT, to check which squares have a '1' in the first bitboard (possible knight moves) and a '0' in the second (locations of friendly pieces):

Success! The last bitboard above is the set of pseudolegal knight moves in the given position. Eventually we'll need to see if any of those leaves the friendly king in check, which is the difference between a legal move and a psuedolegal move. But that's easy- just make each move and test the resulting position!


Sliders are much more complicated. To handle them you need magic bitboards!

As one Stockfish developer told me (Hi Viz!), "You need to know one thing about magic bitboards: They are black magics. And they work. The end."

Another told me, "Magic bitmaps give me and many people headaches. Once you get them working they are just left alone. I have not looked at that code for many years."

In any case, magic bitboards are used for all sliders. Let's take rooks as our example, since they are the simplest slider. We'll use the position below, with the rook on e3:

Since there are only 64 squares for the rook, we store in memory a list of all 64 possible attack-sets (as bitboards!) it might have. The attack-set we access in memory is shown below, with reference coloring; it does not yet take blockers into consideration. So far, this is working just like knights did.

Unblocked attack-set for a rook on e3. This is stored in memory, along with every other square's rook attack-set bitboard. 

The next bitboard we need is one that contains only the blockers on the e-file and the third rank. A little more processing is needed to get this bitboard, but we can just use our initial position and the Re3 attack-set. This is still a lot like what we did for knights. A nice simplification is that the four 'edge' squares can be ignored, since they never block anything. I've therefore colored them grey:

Converting a full-position bitboard into a bitboard that only includes blockers on the e-file and third rank. Only squares marked '1' in both of the first two bitboards are marked'1' in the third bitboard.

The next step is where the bitboards become 'magic.' Remember from my previous post  that bitboards can be expressed as strings of bits in memory. This is the string for the Re3-blocker set that we just made:

0000000000010000000100000000000000000000001000000000000000000000

But this string also expresses a unique binary number. We can multiply that number by a magic number (a different binary string, or visualized as another bitboard) that is specific to rooks on e3, like so:

We multiply our Re3-blocker bitboard by our magic number bitboard.. The result is another string of bits, the index bitboard. In this case we only care about the first 10 bits of the index bitboard (the yellow squares), and toss out the rest (the grey squares).

The first several bits of the index bitboard (the yellow squares) are called an index key. In this case the key needs to be 10 bits long. (Can you find the squares where a rook would need a 12-bit key?)

Each index key is associated with exactly one bitboard describing a set of rook moves. So, we take our specific key and search the index until we find a match.

That index key is guaranteed (by math or magic) to be associated with the bitboard appropriate for our position! Magic depicted below:

Using our index key to find the Re3 blocker-specific attack-set.

Finding magic numbers that give a unique index string for each combination of blockers is a difficult problem. Stockfish (for example) is designed to generate its own set at startup, but it's an open question of whether a set of smaller magic numbers can be efficiently found. Currently trial-and-error is our best method of finding new magic numbers. 

Since we never differentiated between friendly and hostile blockers, we need one last step. The rook-moves bitboard from the index needs to be filtered with a friendly-blockers bitboard:

We only keep squares that are '1' in the first bitboard and '0' in the second bitboard. This only changes the e6 square: There was already a friendly bishop on e6!
Success! We have all the pseudolegal rook moves for our example position. Now we only need to do the same thing for every other slider on the board...

The third piece-type, pawns, are really just a combination of knight-type moves and slider-type moves. (Somehow, they also manage to be the worst piece as well.) But I'm sure you've had enough move-finding for today, so I'll leave pawns alone.

Thanks for reading! Please let me know what you think in the comments.