[SWIFT] Introducing Bitboard-with a little Othello implementation-

Hello. This is Qiita's first post. Please feel free to take a look.

What is Bitboard

Have you ever heard of a data structure called Bitboard? I didn't know until I got involved with Procon (laughs) As many of you may have guessed from the name, Bitboard is a data structure that speeds up processing by expressing the board surface as Bit, that is, ** 0 and 1 binary numbers **. In the following, I will introduce it with concrete examples.

To express the board in binary

As mentioned in the title of this article, I will use Othello as an example throughout this article.

How do you usually express the board when writing an Othello program? スクリーンショット 2020-12-17 21.07.23.png When I think of it at a glance, I think that there are many things that are expressed by substituting numbers etc. for the state that Kuroishi, Shiraishi, and not placed in the two-dimensional array of the size of the board like this.

スクリーンショット 2020-12-17 21.47.44.png

In Bitboard, the place where the stone is placed is 1 and the place where the stone is not placed is 0, and it is expressed in binary. The size of the board is 8x8, that is, there are 64 squares, so you can see that it can be expressed in 64 bits. Also, since it is not possible to distinguish between Shiroishi and Kuroishi in binary numbers, ** the state of the board of Shiroishi and the state of the board of Kuroishi are retained **. It looks like this in the figure.

スクリーンショット 2020-12-17 21.50.43.png   スクリーンショット 2020-12-17 21.52.30.png

Speaking of simple, it is simple, but please be careful as it will be very difficult to understand if you drop it in the program.

About the operation of the board

Now let's actually operate the board.

In Bitboard, unlike arrays, the board is represented by binary numbers, so logical operations such as AND and OR and bit shifts that shift bits can be performed. Bitboard operates the board by making full use of this logical operation and bit shift.

Think of the board coordinates as ** 0 start **. From here, it's a little difficult to make a figure, so I will express the board with letters lol

Put a stone

The procedure for "putting a stone" is quite simple. Let's put it in the place of (5, 3). By the way, the expression is (x, y). First, prepare a variable in which the upper 1 bit is 1 and the remaining 63 bits are 0.

1000000000000000...0000000

Let's divide this into 8 bits and display it with a line break.

10000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000

It looks like this. This is the board that was represented in the figure earlier.

Now, bit shift to the cell where you want to place it, and move 1. The number to be shifted at this time can be calculated by y ​​× 8 + x. In this example, the bit is shifted 3 × 8 + 5 = 29 times.

Then, it will be in the following state. You can see that the location has been moved correctly.

00000000
00000000
00000000
00000100
00000000
00000000
00000000
00000000

After that, you can add it by ORing the board surface of the color you want to place the board surface with the bit standing in this place you want to place.

00000000      00000000    00000000
00000000      00000000    00000000
00000000      00000000    00000000
00000100  OR  00010000 =  00010100
00000000      00001000    00001000
00000000      00000000    00000000
00000000      00000000    00000000
00000000      00000000    00000000

List the places where you can put it

This is an important process in Othello. The process is a little complicated. Let's take the process of enumerating the places where the initial state can be placed as an example.

Before explaining the specific processing, I would like to introduce a mask that shows the edge of the board.

horizontal mask  vertical mask  allside mask
   01111110        00000000       00000000
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        11111111       01111110
   01111110        00000000       00000000

Since the board is a binary number, the program does not know where the edge of the board is. ** (In this article, the binary number is broken by the size of the board to make it easier to understand) Therefore, the problem is solved by using the above mask that shows the edge of the board.

Now, let's get into the explanation of specific processing. In this example, I will list some places that can be placed in the initial state. First, prepare the board in the initial state.

player board  enemy board
  00000000     00000000
  00000000     00000000
  00000000     00000000
  00010000     00001000
  00001000     00010000
  00000000     00000000
  00000000     00000000
  00000000     00000000

Next, AND the horizontal mask to the enemy board and apply the mask.

enemy board  horizontal mask  masked board
 00000000       01111110        00000000
 00000000       01111110        00000000
 00000000       01111110        00000000
 00001000  AND  01111110   =    00001000
 00010000       01111110        00010000
 00000000       01111110        00000000
 00000000       01111110        00000000
 00000000       01111110        00000000

Then bit shift the player board to the left and AND it with the masked board to see if there are any stones that can be turned over.

player board     masked board       tmp
  00000000         00000000       00000000
  00000000         00000000       00000000
  00000000         00000000       00000000
  00100000   AND   00001000   =   00000000
  00010000         00010000       00010000
  00000000         00000000       00000000
  00000000         00000000       00000000
  00000000         00000000       00000000

By performing this above processing, the bit will be set only at the location of the enemy stone adjacent to the player's stone. In other words, the bit stands only in the place of the stone that can be turned over.

From now on, tmp is bit-shifted and ANDed with masked board, and tmp before bit-shifting is ORed and updated. Do this 6 times, which is the maximum number that can be flipped (maximum when placed on the edge).

    tmp          masked board          tmp
  00000000         00000000         00000000
  00000000         00000000         00000000
  00000000         00000000         00000000
  00000000   AND   00001000   OR=   00000000
  00100000         00010000         00010000
  00000000         00000000         00000000
  00000000         00000000         00000000
  00000000         00000000         00000000

The final result is as follows. In this state, ** only the stones that can be flipped to the left of the player's stones are listed **.

    tmp   
  00000000
  00000000
  00000000
  00000000
  00010000
  00000000
  00000000
  00000000

I will keep the bit standing only in the place where it can be placed last. First, OR the player board and enemy board to prepare the board on which both stones are placed.

player board    enemy board   current board
  00000000       00000000       00000000
  00000000       00000000       00000000
  00000000  OR   00000000   =   00000000
  00010000       00001000       00011000
  00001000       00010000       00011000
  00000000       00000000       00000000
  00000000       00000000       00000000
  00000000       00000000       00000000

Next, NOT current board to create a empty board in which bits are set only in places where no stones are placed on the current board.

current board    empty board
  00000000        11111111
  00000000        11111111
  00000000  NOT=  11111111
  00011000        11100111
  00011000        11100111
  00000000        11111111
  00000000        11111111
  00000000        11111111

Bitshift tmp to the left and move it to the left of a stone that can be flipped over. This is the state where the bit stands only in the place where it can be pinched. Then, by ANDing the empty board to the bit-shifted board surface, the state where the bit stands only in the place where the stone can be placed is completed.

    tmp          empty board    legal board
  00000000         11111111       00000000
  00000000         11111111       00000000
  00000000         11111111       00000000
  00000000   AND   11100111   =   00000000
  00100000         11100111       00100000
  00000000         11111111       00000000
  00000000         11111111       00000000
  00000000         11111111       00000000

Doing this in all eight directions completes the enumeration. Use horizontal mask for left and right, vertical mask for top and bottom, and allside mask for diagonal.

The process of turning over

Next is the process of turning over.

First, prepare a board with bits standing only where you want to place the stone. In the example, it is assumed to be placed at (5,3).

puted mask
 00000000
 00000000
 00000000
 00000100
 00000000
 00000000
 00000000
 00000000

Next, shift it 1 bit to the left and AND it with horizontal mask.

puted mask  horizontal mask     tmp
 00000000      01111110       00000000
 00000000      01111110       00000000
 00000000      01111110       00000000
 00001000 AND  01111110   =   00001000
 00000000      01111110       00000000
 00000000      01111110       00000000
 00000000      01111110       00000000
 00000000      01111110       00000000

AND the enemy board to tmp.

    tmp       empty board   reverse tmp
 00000000      00000000       00000000
 00000000      00000000       00000000
 00000000      00000000       00000000
 00001000 AND  00001000   =   00001000
 00000000      00010000       00000000
 00000000      00000000       00000000
 00000000      00000000       00000000
 00000000      00000000       00000000

After that, tmp is further bit-shifted, ANDed with empty board, and the process of ORing the result to reverse tmp and updating is repeated until tmp AND empty board becomes 0. When tmp AND empty board becomes 0, it means that there are no more consecutive enemy stones.

AND player board and tmp at the timing when the iteration process is finally exited.

player board       tmp          reverse tmp
  00000000       00000000        00000000
  00000000       00000000        00000000
  00000000       00000000        00000000
  00010000  AND  00010000  =     00010000
  00001000       00000000        00000000
  00000000       00000000        00000000
  00000000       00000000        00000000
  00000000       00000000        00000000

If this result is other than 0, it means that the enemy stone is sandwiched between your own stones, so it is confirmed as the final upside-down stone. This time it is other than 0, so OR reverse to update and confirm. reverse is a variable whose bits are set only where it can be turned over.

reverse tmp     reverse
 00000000       00000000
 00000000       00000000
 00000000       00000000
 00010000  OR=  00010000
 00000000       00000000
 00000000       00000000
 00000000       00000000
 00000000       00000000

When you finish in one direction, do it in the other direction.

Once this reverse part is created, it can be turned over with only the following logical operations. ^ means NOT and | means OR. player board ^= puted mask | reverse enemy board ^= reverse

That is all for the explanation. In addition to this, there are other things such as path processing and checking whether it can be placed, but it can be implemented by applying the processing introduced so far.

Practice

From here, I will introduce what I actually put into the program. The implementation itself is written in Swift, which I'm relatively familiar with, but if you want speed, I think it's best to write it in C ++, which can be accelerated by using AVX. When I actually tried to use it in a competition pro, I wrote it in C ++.

Put a stone

func put(x: String, y: String) {
    guard let xInt = Int(x) else { return }
    guard let yInt = Int(y) else { return }
    var putedMask: UInt64 = 0x8000000000000000
        
    putedMask = putedMask >> xInt
    putedMask = putedMask >> (yInt * 8)
        
    if isCanPut(putedMask: putedMask) {
        doReverse(putedMask: putedMask)
        nextTurn()
            
        if shouldPass {
            print("Passed because there is no space to put")
            nextTurn()
        }
    } else {
        print("(" + x + ", " + y + ")Cannot be placed in")
    }
}

List the places where you can put it

//List and return the places that can be placed in 8 directions
func makeLegalBoard(playerBoard: UInt64, enemyBoard: UInt64) -> UInt64 {
    var legalBoard = getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP_RIGHT)
    legalBoard |= getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .RIGHT)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM_RIGHT)
    legalBoard |= getCanPutPoint(mask: verticalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .BOTTOM_LEFT)
    legalBoard |= getCanPutPoint(mask: horizontalMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .LEFT)
    legalBoard |= getCanPutPoint(mask: allSideMask, playerBoard: playerBoard, enemyBoard: enemyBoard, direction: .TOP_LEFT)
        
    return legalBoard
}

//Return the board with the bit standing in the direction where it can be placed
func getCanPutPoint(mask: UInt64, playerBoard: UInt64, enemyBoard: UInt64, direction: DIRECTION) -> UInt64 {
    let masked = mask & enemyBoard
    var tmp: UInt64 = masked & getStridedBoard(target: playerBoard, direction: direction)
    for _ in 0..<5 {
        tmp |= masked & getStridedBoard(target: tmp, direction: direction)
    }
    return ~(playerBoard | enemyBoard) & getStridedBoard(target: tmp, direction: direction)
}

//Bit shift the target in the direction of direction
func getStridedBoard(target: UInt64, direction: DIRECTION) -> UInt64 {
    return direction.stride.isNegativeNumber ? target << direction.stride.absValue : target >> direction.stride.absValue
}

The process of turning over

//The process of actually turning over
func doReverse(putedMask: UInt64) {
    var reversed: UInt64 = 0
    for i in 0..<8 {
        var revTmp: UInt64 = 0
        var tmp: UInt64 = moveTo(target: putedMask, direction: DIRECTION(rawValue: i)!)
        while (tmp != 0) && ((tmp & enemyCell) != 0) {
            revTmp |= tmp
            tmp = moveTo(target: tmp, direction: DIRECTION(rawValue: i)!)
        }
            
        if (tmp & playerCell) != 0 {
            reversed |= revTmp
        }
    }
    playerCell ^= putedMask | reversed
    enemyCell ^= reversed
}

//Move the target in the DIRECTION direction and then mask it
func moveTo(target: UInt64, direction: DIRECTION) -> UInt64 {
    let stridedBoard = getStridedBoard(target: target, direction: direction)
    return stridedBoard & direction.sideMask.rawValue
}

At the end

How was that? I did not compare the performance with the normal implementation this time, but I feel that it seems to be faster lol

I think the advantage of using Bit is that it can be obtained in parallel **. In Othello, the process of enumerating the places where you can put it can be obtained for all stones at the same time using Bitboard, but not so with arrays.

When I was actually writing the program in Procon, it was a camp game, but when I tried to express it in Bitboard, the processing speed became about 100 times faster lol (Processing after optimizing with AVX in C ++) Speed) I remember being a little impressed at that time.

This time I remembered that impression a little, so I wrote it. There is something called Magic Bitboard as an evolution of Bitboard. It may be interesting to look it up.

That is all. Thank you for browsing.

Recommended Posts

Introducing Bitboard-with a little Othello implementation-
A little complicated conditional branching