search

denkspuren / BitboardC4

The Design of Bitboards for use in Connect Four
MIT License
62 stars 8 forks source link

A more efficient bitboard #2

Closed jmeintrup closed 4 years ago

jmeintrup commented 4 years ago

Hello, i just wanted to mention that it is possible to store the board state with less bits, which might be interesting if this repository is still used for teaching.

a boardstate S for a board of width W and height H can be stored with H*(W+1) bits. Example:

. . . . . . .         0000000
. . . . . . .         0000000
. . . . . . .   =>    0000100
. . . . X . .         0000101
. . . . X . X         0011101
. . X O O . O         1110010

every O is encoded by a 0, and every X is encoded by a 1. Additionally, a 1 is added to as an 'outline' to each column.

This data structure is used in the AI using a hard-solved solution at https://connect4.gamesolver.org/

The board is used as a key in a lookup table for starting positions. Some masking is needed for fast operations, ofc.

denkspuren commented 4 years ago

Thank you very much for your comment and the link to the website. This is a very interesting encoding that's worth having a closer look into. As I noticed the bitboard is described in http://blog.gamesolver.org/solving-connect-four/06-bitboard/ by the author @PascalPons of https://connect4.gamesolver.org/ (https://github.com/PascalPons/connect4). Thx