Generating moves in Othello with bitboards

Question

I have made two very similar Othello AIs. In the first one, the board is represented as an array of length 100 (10x10) where the 8x8 board is represented in the "middle" of the array and the rest of the array is buffer spaces around the edge (index 11 is top left corner of 8x8 board, index 88 is bottom right corner). To make a move at position index, I use the following code:

changed = [index]

for direction in (1, 9, 10, 11):
    shift = index - direction
    while board[shift] == opp:
        shift -= direction
    if board[shift] == player:
        changed += [*range(shift + direction, index, direction)]

for direction in (1, 9, 10, 11):
    shift = index + direction
    while board[shift] == opp:
        shift += direction
    if board[shift] == player:
        changed += [*range(index + direction, shift, direction)]

To generate moves, I then go through the possible indices (which are tiles in the inner 8x8 board) and check if len(changed) > 1. If it is, I set the tiles of the board in changed to that player.

In the second AI, which I had expected would be faster in making moves, the board is represented as two 64-bit bitboards - one for the player aiming to maximize the score and another for the player trying to minimize the score. To make a move, I use the same code as here just converted into Python:

new_disk = 1 << index
captured = 0
newmy_disks = my_disks | new_disk

for direction in range(8):
    x = shift(new_disk, direction) & opp_disks
    
    for i in range(5):
        x |= shift(x, direction) & opp_disks
    
    bounding_disk = shift(x, direction) & my_disks
    if bounding_disk != 0:
        captured_disks |= x

newmy_disks = newmy_disks ^ captured_disks
newopp_disks = opp_disks ^ captured_disks

With the bitboard representation, playing 1000 random games takes around 7 seconds, while the array representation takes 4 seconds.

How can I make the bitboard representation faster in generating and making moves, and would it be possible to check possible moves and return the new bitboards at the same time?

I'm not sure the questions you ask at the end are really the most important ones to be asking here. It may not be possible for a bit-arithmetic version of this code to be as fast as a more traditional data-structure-based one, at least, not in pure Python. Python's integers are much more heavyweight objects, so creating and manipulating them is always going to be a lot slower than doing it in C, where the compiler may optimize bit operations down to individual machine instructions. So best answer might be *use the first code* or *don't use pure Python for bit operations*. — Blckknght, Jan 27 '20 at 05:51
I looked at the same site and implemented the algorithm within Python, but I didn't see any noticeable differences in runtimes when using bitboards as opposed to a normal string representation. Perhaps check if you are not running any redundant things? — Chris, Apr 16 '22 at 19:07

Generating moves in Othello with bitboards

0 Answers0