Implement reversi reversi processing using BitBoard

Implement reversi with BitBoard. This time we will implement the inversion process. (For the sake of simplicity, we will use a 4x4 example, but the implementation is 8x8. W: Shiraishi, B: Kuroishi, x: No stone.)

xxxx
xWBx
xBWx
xxxx

Kuroishi is placed on this board in BitBoard

0000
0010
0100
0000

And the arrangement of Shiroishi

0000
0100
0010
0000

It is represented by two bit strings of.

Black turn start move:

0000
0000
0001
0000

In contrast to the flipped stone placement flipped:

0000
0000
0010
0000

When you ask, the inversion process of the white number is ʻopponent_board ^ = flipped` In other words, the arrangement of Shiroishi is

0000   0000   0000
0100 ^ 0000 = 0100
0010   0010   0000
0000   0000   0000

Also, the arrangement of Kuroishiself_board ^= flipped | moveOrself_board |= flippled | moveObtained from.

0000   0000   0000
0010 ^ 0000 = 0010
0100   0011   0111
0000   0000   0000

From now on, we will focus on finding the inverted Shiraishi flipped. The flipping Shiraishi is always in one of the eight directions diagonally up, down, left, and right of the start move. First, let's start with a search to the left. Inversion to the left corresponds to one of the following two patterns.

BWo
BWWo

(W: Shiraishi, B: Kuroishi, o: Kuroishi start, respectively.)

Shift the start move to the left to get the white number placement and product. You get flipped by shifting the result further to the left and taking the product with the white number placement. (In 8x8, a total of 6 shifts will give you flipped.) However, you need to make sure that there is a white stone that can be flipped to the left before the operation. This is the same as How to find a legal hand.

class Board:
    BLACK, WHITE = True, False

    def __init__(self, black=0x000008100000, white=0x000010080000):
        self.board = {Board.BLACK: black, Board.WHITE: white}

    def flipped(self, player, move):
        """ returns flipped stones """
        flipped = 0b0
        player_board = self.board[player]
        opponent_board = self.board[not player]
        blank_board = ~(player_board | opponent_board)

        masked_opponent_board = opponent_board & 0x7e7e7e7e7e7e7e7e

        #Make sure there is a white stone that can be flipped to the left
        temp = player_board << 1 & masked_opponent_board
        temp |= temp << 1 & masked_opponent_board
        temp |= temp << 1 & masked_opponent_board
        temp |= temp << 1 & masked_opponent_board
        temp |= temp << 1 & masked_opponent_board
        temp |= temp << 1 & masked_opponent_board
        legal_moves = temp << 1 & blank_board

        # move & legal_moves will be move or 0b0
        temp = (move & legal_moves) >> 1 & opponent_board
        temp |= temp >> 1 & opponent_board
        temp |= temp >> 1 & opponent_board
        temp |= temp >> 1 & opponent_board
        temp |= temp >> 1 & opponent_board
        temp |= temp >> 1 & opponent_board
        flipped |= temp

        return flipped

Recommended Posts

Implement reversi reversi processing using BitBoard
Implement reversi reversi processing using BitBoard
Dictionary-type processing using items ()
Using Python mode in Processing
Implement ranking processing with ties in Python using Redis Sorted Set
[Linux] Accelerate compression processing using pigz
100 language processing knock-76 (using scikit-learn): labeling
Environmentally friendly scraping using image processing
100 Language Processing Knock-31 (using pandas): Verb
Horizon processing using OpenCV morphology transformation
Japanese analysis processing using Janome part1
100 language processing knock-73 (using scikit-learn): learning
100 language processing knock-74 (using scikit-learn): Prediction
I tried asynchronous processing using asyncio
100 Language Processing Knock-38 (using pandas): Histogram