ビットボードをPHPで実装してみた

いい感じの記事にする時間がなかったので捨てようかと思ったけど、せっかくコード書いたので公開しときます❗️😸👊

これをPHPで実装しました💁‍♀️✨
https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43

##ソースコード

``` Board.php
<?php

namespace App\Board;

class Board
{
    public $blackTurn = 100;
    public $whiteTurn = -100;

    public $nowTurn;
    public $nowIndex;
    public $playerBoard;
    public $opponentBoard;

    public function __construct()
    {
        $this->nowTurn = $this->blackTurn;
        $this->nowIndex = 1;

        $this->playerBoard = 0x0000000810000000;
        $this->opponentBoard = 0x0000001008000000;
    }

    public function coordinateToBit($x, $y)
    {
        $mask = 0x0000000000000001;

        switch ($x) {
            case "A":
                $mask = $mask << 7;
                break;
            case "B":
                $mask = $mask << 6;
                break;
            case "C":
                $mask = $mask << 5;
                break;
            case "D":
                $mask = $mask << 4;
                break;
            case "E":
                $mask = $mask << 3;
                break;
            case "F":
                $mask = $mask << 2;
                break;
            case "G":
                $mask = $mask << 1;
                break;
            default:
                break;
        }

        $intY = (int) $y;
        $mask = $mask << ((8 - $intY) * 8);

        return $mask;
    }

    public function bitCount($num)
    {
        $boardSize = 64;
        $mask = 0x8000000000000000;
        $count = 0;

        for ($i = 0; $i < $boardSize; $i++) {
            if ($mask & $num != 0) {
                $count += 1;
            }
            $mask = $mask >> 1;
        }
        return $count;
    }

    public function canPut($put)
    {
        // 着手可能なマスにフラグが立っている合法手ボードを生成
        $legalBoard = $this->makeLegalBoard($this);

        // 今回の着手が、その合法手ボードに含まれれば着手可能
        return ($put & $legalBoard) == $put;
    }

    public function reverse($put)
    {
        //着手した場合のボードを生成
        $rev = 0;
        for ($k = 0; $k < 8; $k++) {
            $rev_ = 0;
            $mask = $this->transfer($put, $k);

            while (($mask != 0) && (($mask & $this->opponentBoard) != 0)) {
                $rev_ |= $mask;
                $mask = $this->transfer($mask, $k);
            }
            if (($mask & $this->playerBoard) != 0) {
                $rev |= $rev_;
            }
        }
        //反転する
        $this->playerBoard ^= $put | $rev;
        $this->opponentBoard ^= $rev;
        //現在何手目かを更新
        $this->nowIndex = $this->nowIndex + 1;
    }

    public function isPass()
    {
        // 手番側の合法手ボードを生成
        $playerLegalBoard = $this->makeLegalBoard($this);

        // 相手側の合法手ボードを生成
        $tmpBoard = new Board();
        $tmpBoard->nowTurn = $this->nowTurn;
        $tmpBoard->nowIndex = $this->nowIndex;
        $tmpBoard->playerBoard = $this->playerBoard;
        $tmpBoard->opponentBoard = $this->opponentBoard;
        $opponentLegalBoard = $this->makeLegalBoard($tmpBoard);

        // 手番側だけがパスの場合
        return $playerLegalBoard == 0x0000000000000000 && $opponentLegalBoard != 0x0000000000000000;
    }

    public function isGameFinished()
    {
        $playerLegalBoard = $this->makeLegalBoard($this);
        $tmpBoard = new Board();
        $tmpBoard->nowTurn = $this->nowTurn;
        $tmpBoard->nowIndex = $this->nowIndex;
        $tmpBoard->playerBoard = $this->playerBoard;
        $tmpBoard->opponentBoard = $this->opponentBoard;
        $opponentLegalBoard = $this->makeLegalBoard($tmpBoard);

        // 両手番とも置く場所がない場合
        return $playerLegalBoard == 0x0000000000000000 && $opponentLegalBoard == 0x0000000000000000;
    }

    public function swapBoard()
    {
        //ボードの入れ替え
        $tmp = $this->playerBoard;
        $this->playerBoard = $this->opponentBoard;
        $this->opponentBoard = $tmp;

        //色の入れ替え
        $this->nowTurn = $this->nowTurn * -1;
    }

    public function getResult()
    {
        //石数を取得
        $blackScore = $this->bitCount($this->playerBoard);
        $whiteScore = $this->bitCount($this->opponentBoard);
        if ($this->nowTurn === $this->whiteTurn) {
            $tmp = $blackScore;
            $blackScore = $whiteScore;
            $whiteScore = $tmp;
        }
        // 勝敗情報を取得
        $winner = "黒番";
        $isWhiteWin = $whiteScore >= $blackScore;
        if ($isWhiteWin) {
            $winner = "白番";
        }
        return [$blackScore, $whiteScore, $winner];
    }

    private function transfer($put, $k)
    {
        switch ($k) {
            case 0: //上
                return ($put << 8) & 0x8000000000000000 >> 56;
            case 1: //右上
                return ($put << 7) & 0x7f7f7f7f7f7f7f00;
            case 2: //右
                return ($put >> 1) & 0x7f7f7f7f7f7f7f7f;
            case 3: //右下
                return ($put >> 9) & 0x007f7f7f7f7f7f7f;
            case 4: //下
                return ($put >> 8) & 0x00ffffffffffffff;
            case 5: //左下
                return ($put >> 7) & 0x00fefefefefefefe;
            case 6: //左
                $put <<= 1;
                if ($put > 0xfefefefe) {
                    return ($put) & 0xfefefefe00000000;
                }else {
                    return ($put) & 0xfefefefe;
                }
            case 7: //左上
                $put <<= 9;
                if ($put > 0xfefefefe) {
                    return ($put) & 0xfefefefe00000000;
                }else {
                    return ($put) & 0xfefefefe;
                }
            default:
                return 0;
        }
    }

    private function makeLegalBoard($board)
    {
        //左右端の番人
        $horizontalWatchBoard = $board->opponentBoard & 0x7e7e7e7e7e7e7e7e;
        //上下端の番人
        $verticalWatchBoard = $board->opponentBoard & 0x00FFFFFFFFFFFF00;
        //全辺の番人
        $allSideWatchBoard = $board->opponentBoard & 0x007e7e7e7e7e7e00;
        //空きマスのみにビットが立っているボード
        $blankBoard = ~($board->playerBoard | $board->opponentBoard);

        //8方向チェック
        // ・一度に返せる石は最大6つ ・高速化のためにforを展開(ほぼ意味ないけどw)
        //左
        $tmp = $horizontalWatchBoard & ($board->playerBoard << 1);
        $tmp |= $horizontalWatchBoard & ($tmp << 1);
        $tmp |= $horizontalWatchBoard & ($tmp << 1);
        $tmp |= $horizontalWatchBoard & ($tmp << 1);
        $tmp |= $horizontalWatchBoard & ($tmp << 1);
        $tmp |= $horizontalWatchBoard & ($tmp << 1);
        $legalBoard = $blankBoard & ($tmp << 1);

        //右
        $tmp = $horizontalWatchBoard & ($board->playerBoard >> 1);
        $tmp |= $horizontalWatchBoard & ($tmp >> 1);
        $tmp |= $horizontalWatchBoard & ($tmp >> 1);
        $tmp |= $horizontalWatchBoard & ($tmp >> 1);
        $tmp |= $horizontalWatchBoard & ($tmp >> 1);
        $tmp |= $horizontalWatchBoard & ($tmp >> 1);
        $legalBoard |= $blankBoard & ($tmp >> 1);

        //上
        $tmp = $verticalWatchBoard & ($board->playerBoard << 8);
        $tmp |= $verticalWatchBoard & ($tmp << 8);
        $tmp |= $verticalWatchBoard & ($tmp << 8);
        $tmp |= $verticalWatchBoard & ($tmp << 8);
        $tmp |= $verticalWatchBoard & ($tmp << 8);
        $tmp |= $verticalWatchBoard & ($tmp << 8);
        $legalBoard |= $blankBoard & ($tmp << 8);

        //下
        $tmp = $verticalWatchBoard & ($board->playerBoard >> 8);
        $tmp |= $verticalWatchBoard & ($tmp >> 8);
        $tmp |= $verticalWatchBoard & ($tmp >> 8);
        $tmp |= $verticalWatchBoard & ($tmp >> 8);
        $tmp |= $verticalWatchBoard & ($tmp >> 8);
        $tmp |= $verticalWatchBoard & ($tmp >> 8);
        $legalBoard |= $blankBoard & ($tmp >> 8);

        //右斜め上
        $tmp = $allSideWatchBoard & ($board->playerBoard << 7);
        $tmp |= $allSideWatchBoard & ($tmp << 7);
        $tmp |= $allSideWatchBoard & ($tmp << 7);
        $tmp |= $allSideWatchBoard & ($tmp << 7);
        $tmp |= $allSideWatchBoard & ($tmp << 7);
        $tmp |= $allSideWatchBoard & ($tmp << 7);
        $legalBoard |= $blankBoard & ($tmp << 7);

        //左斜め上
        $tmp = $allSideWatchBoard & ($board->playerBoard << 9);
        $tmp |= $allSideWatchBoard & ($tmp << 9);
        $tmp |= $allSideWatchBoard & ($tmp << 9);
        $tmp |= $allSideWatchBoard & ($tmp << 9);
        $tmp |= $allSideWatchBoard & ($tmp << 9);
        $tmp |= $allSideWatchBoard & ($tmp << 9);
        $legalBoard |= $blankBoard & ($tmp << 9);

        //右斜め下
        $tmp = $allSideWatchBoard & ($board->playerBoard >> 9);
        $tmp |= $allSideWatchBoard & ($tmp >> 9);
        $tmp |= $allSideWatchBoard & ($tmp >> 9);
        $tmp |= $allSideWatchBoard & ($tmp >> 9);
        $tmp |= $allSideWatchBoard & ($tmp >> 9);
        $tmp |= $allSideWatchBoard & ($tmp >> 9);
        $legalBoard |= $blankBoard & ($tmp >> 9);

        //左斜め下
        $tmp = $allSideWatchBoard & ($board->playerBoard >> 7);
        $tmp |= $allSideWatchBoard & ($tmp >> 7);
        $tmp |= $allSideWatchBoard & ($tmp >> 7);
        $tmp |= $allSideWatchBoard & ($tmp >> 7);
        $tmp |= $allSideWatchBoard & ($tmp >> 7);
        $tmp |= $allSideWatchBoard & ($tmp >> 7);
        $legalBoard |= $blankBoard & ($tmp >> 7);

        return $legalBoard;
    }
}
```

``` BoardController.php
<?php

namespace App\Http\Controllers;

use App\Board\Board;
use Illuminate\Support\Facades\Log;

class BoardController extends Controller
{
    public function makeBoard($kifu)
    {
        $board = new Board();

        $length = strlen($kifu) / 2;

        for ($i = 0; $i < $length; $i++) {
            $x = substr($kifu, $i * 2, 1);
            $y = substr($kifu, $i * 2 + 1, 1);

            $put = $board->coordinateToBit($x, $y);

            if ($board->canPut($put)) {
                $board->reverse($put);
                $board->swapBoard();
            }

            if ($board->isPass()) {
                $board->swapBoard();
            }
            if ($board->isGameFinished()) {
                $result = $board->getResult();
            }

        }
        return $board;
    }

    public function index()
    {
        $kifu = request('kifu') ?? '';
        $board = $this->makeBoard($kifu);

        Log::debug($board);
    }
}
```

##動かしてみた
axiosをローカルで使ったらなんか遅延する(Dockerのせい？😿

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">800ms遅延オセロ <a href="https://t.co/7w32R3rFMU">pic.twitter.com/7w32R3rFMU</a></p>&mdash; tsu🐳🐘 (@tsu_eng) <a href="https://twitter.com/tsu_eng/status/1340301396051075081?ref_src=twsrc%5Etfw">December 19, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

##苦労したこと
PHPは符号なし整数をサポートしていません❗️😾
許せねぇ…

なので、`0b1000000000000000(略)` みたいなものを右シフトしたとき `0b0100000000000(略)` になってくれず、`0b110000000000(略)` のように1がついてきます😿

あと、`0xfefefefefefefefe` が `0xfefefefefefe0000` になったりしたので分岐して無理やり対応しました😸