LoginSignup
3
0

More than 1 year has passed since last update.

オセロAdvent Calendar 2020Day 19
@tsu_eng(つ)

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

Last updated at Posted at 2020-12-19

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

これを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のせい？😿

苦労したこと

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

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
Sign upLogin
3
0