CODEWITHSUNDEEP
bit-manipulationchessbitboard
Shreyas
Shreyas

Reputation: 708

Generating individual moves from a bitboard of moves

In my chess engine, that uses bitboards for representing the board's state, generates a chunk of pseudo-legal moves in one go, a bitboard being the result. For example:

Pawns:

Pawns' state Pawns' state - bitboard

A little bitboard magic later:

Pawns' positions Pawns' positions - bitboard

The bitboard at the end is simply a chunk of possible moves. How do engines usually take this bitboard and generate individual moves from them? Do I have to iterate over every single bit to check if it's set? Iterating over a bitboard seems to defy the very purpose of using bitboards though, which is why I'm a bit skeptical.

Is there a better way?

Upvotes: 3

Views: 1586

Answers (2)

bloody
bloody

Reputation: 1168

You don't have to iterate over 64 single bits. You can prepare/pre-define for example a 256-sized lookup array with all possible move-lists where 8-bit indices represent attack-sets of a piece on a single rank. Then you can iterate only 8 times with bitwise shift operation (bitboard >> 8) to pass subsequent rank-attack-sets as an index to the array and extract the move-list. It will speed up roughly 8 times comparing to one-bit stepping loop. Maybe you should enhance this array to [8][256] actually to pass also a rank number itself and extract a final move-list (with x,y coordinates) depending on your needs. The memory cost is still insignificant.

Upvotes: 2

user555045
user555045

Reputation: 64904

Then, typically you apply some variant of the minimax algorithm to evaluate how good the moves are, so you can pick (what you estimate to be) the best move. A simple variant is, for example, alpha-beta.

The variants mainly deal with attempting to guide the search towards "probably useful moves" and away from useless areas of the search space, because the search tree is very wide and your ability to explore it deeply is extremely important for a good chess AI - exploring it shallowly makes the AI easy to "trap" because it will make choices that look good short-term even though they work out badly later on.

So yes, you will iterate over the bitboards. That doesn't really defy their purpose - you've still (probably) computed the moves much faster than if you hadn't used bitboards. For the simplest AI you could just take "the first" move using standard bitboard techniques, but an AI that plays like that will be below novice level, having no regard for winning or losing at all.

Upvotes: 2

Related Questions