前置き

PHPを用いてモザイクをビットボードで実装した際の知見を共有する記事です。

ビットボードとは？ -> 調べてください。
モザイクとは？ -> ボードゲームです。[概要]

~~当初はC++で実装したのですが、PHPのFFIで使おうとしたところSegfaultが発生してしまい、力不足で解消できなかったため泣く泣くPHPで再実装しました。~~

2021/01/21 追記:

C++とPHP FFIで実現できました。ベンチマークに結果を追記しておきます。

こんな人向けの記事

ビットボードに興味がある。
PHPでビットボードを実装したい。
- intで表現できる64bitより多い桁が必要。
モザイクを実装したいがロジックが思い付かない。

完成品

記事内のコードとは異なる部分があります。
GPL 3.0ライセンスです。

ビット演算

リバーシなら8*8=64マス、つまり64bitのintで済みますが、モザイクは7段のピラミッド状で7²+6²+5²+...1²=140マス、つまり140bitが必要です。

なお記事内では簡略化のため、3段で3²+2²+1²=14マスのモザイクを実装することとします。

まずはBitSetというインターフェースで抽象化することにします。

BitSetの抽象化は非推奨

2021/01/21 追記:

BitSetを抽象化することでインスタンス化やメソッドコールのコストが発生します。

後述するBoard内でビット演算を行なうことで、実装方法によってはパフォーマンスが50〜60%程度改善しました。

詳細は記事下部のベンチマーク結果にて確認してください。

インターフェース

AND/OR/XOR/左シフト/右シフト/popcount/set/clear/flip(反転)/文字列への変換といった必須の機能を宣言します。

その他、配列やイテレータへの変換等の補助的な機能は必要に応じてどうぞ。

interface BitSet extends ArrayAccess, Countable, IteratorAggregate
{
    public function __toString();
    public function toString(): string;
    public function size(): int;
    public function getIterator();
    public function toArray();
    public function count();
    public function equalsTo(self $other): bool;
    public function set(int ...$offsets): self;
    public function setAll(): self;
    public function clear(int ...$offsets): self;
    public function clearAll(): self;
    public function and(self $other): self;
    public function or(self $other): self;
    public function xor(self $other): self;
    public function lshift(int $amount): self;
    public function rshift(int $amount): self;
    public function flip(): self;
}

実装

僕はイミュータブルなクラスとして実装しました。

ただ、7段だと1ゲームで80000回以上インスタンス化することになるため、パフォーマンスが犠牲になっています。

ミュータブルかイミュータブルかはお好みでどうぞ。この記事ではイミュータブルとして話を進めます。

配列で実装する

開発開始当初は既存のライブラリを参考に、配列を用いてArrayBitSetというクラスを実装しました。具体的な実装方法は参考元を確認してください。

GMPで実装する

先述の配列による実装は素のPHPで実装可能ですが、パフォーマンスが良くないです。

PHPで多倍長整数を扱う方法を探したところ、GMP拡張にて実現できることが分かりました。

PHP: GMP - Manual

ビット演算に関する処理をすべてGMPに任せたGMPBitSetというクラスを実装して計測したところ、ArrayBitSetと比較して57%ものパフォーマンス改善が達成できました。

パフォーマンス改善のヒント

AND演算を例に上げます。

final class GMPBitSet implements BitSet
{
    public function and(BitSet $other): BitSet
    {
        return new self(
            $this->size,
            gmp_and($this->gmp, ($other instanceof self)
                ? $other->gmp
                : gmp_init($other->toString(), 2)),
        );
    }
}

BitSet::and(BitSet $other)の$otherはBitSetを実装していますが、GMPBitSetのインスタンスとは限りません。

しかし常に$other->toString()を呼び出すと、$otherがGMPBitSetだった場合に余計なコストがかかります。

もし$otherがGMPBitSetだった場合はそのままgmp_and()に渡すようにすれば、コストが節約できます。

盤面

実装したBitSetを用いて、今度は盤面を表現します。

下図のように最上段の1マスを0としたインデックスで表現します。

盤面もインターフェース化して抽象化することにします。

インターフェース

盤面同士もビット演算できるように、ビット演算に関する機能を宣言します。

ある条件を満たす2*2マスの上方のマスを抽出する処理を勝手にプロモーションと名付けました。

例えば、石が1つ置かれた上方のマスはpromoteOne()、石が3つ以上置かれた上方のマスはpromoteMajority()といった具合ですね。

interface Board extends Countable
{
    public function __toString();
    public function toString(): string;
    public function getIterator();
    public function toArray();
    public function count(): int;
    public function size(): int;
    public function and(self $other): self;
    public function or(self $other): self;
    public function xor(self $other): self;
    public function equalsTo(self $other): bool;
    public function flip(): self;
    public function promoteZero(): self;
    public function promoteOne(): self;
    public function promoteTwo(): self;
    public function promoteThree(): self;
    public function promoteFour(): self;
    public function promoteHalfOrMore(): self;
    public function promoteMajority(): self;

    // public function mirrorHorizontal(): self;
    // public function flipVertical(): self;
    // public function flipDiagonal(): self;
    // public function rotate90(): self;
    // public function rotate180(): self;
    // public function rotate270(): self;
}

最下部のコメントアウトしてあるものは、盤面の変形(回転/反転)に関する機能です。

機械学習等で用いる際に盤面を正規化したければ、併せて実装するといいでしょう。

実装

まずはBitSetインターフェースで盤面を扱うBitSetBoardという抽象クラスを実装します。

盤面の処理のほとんどはBitSetBoardで扱うこととして、BitSetを実装したオブジェクトを生成する処理を具象クラスとなるArrayBitSetBoardやGMPBitSetBoardに持たせることで、具象クラスの派生が容易になります。

(以下、かなり長くなります)

abstract class BitSetBoard implements Board
{
    public const MAX_SIZE = 7;

    /** @var int */
    private $size;

    /** @var BitSet */
    private $bitSet;

    protected function __construct(int $size, BitSet $bitSet)
    {
        assert(0 < $size && $size <= self::MAX_SIZE, sprintf('Board size must be between 1 and %d.', self::MAX_SIZE));
        $this->size = $size;
        $this->bitSet = self::boardMask($size)->and($bitSet);
    }

    abstract protected static function stringToBitSet(int $size, string $string): BitSet;

    public static function fromString(int $size, string $cells): Board
    {
        return new static($size, static::stringToBitSet(self::bitSetSize($size), $cells));
    }

    public static function emptyBoard(int $size): Board
    {
        static $boards = [];
        return $boards[$size]
            ?? ($boards[$size] = new static($size, self::zeroBitSet($size)));
    }

    public static function groundBoard(int $size): Board
    {
        static $boards = [];
        return $boards[$size]
            ?? ($boards[$size] = self::emptyBoard($size)->or(new static($size, self::layerMask($size, $size))));
    }

    public static function neutralBoard(int $size): Board
    {
        static $boards = [];

        if (!isset($boards[$size])) {
            if ($size % 2 === 1) {
                $bitSet = self::oneBitSet($size);
                for ($i = 1; $i < $size; $i++) {
                    $bitSet = $bitSet->lshift($i ** 2);
                }
                $bitSet = $bitSet->lshift(intdiv($i ** 2, 2));
                $boards[$size] = new static($size, $bitSet);
            } else {
                $boards[$size] = self::emptyBoard($size);
            }
        }

        return $boards[$size];
    }

    public static function filledBoard(int $size): Board
    {
        static $boards = [];
        return $boards[$size]
            ?? ($boards[$size] = new static($size, self::boardMask($size)));
    }

    public function __toString()
    {
        return $this->toString();
    }

    public function toString(): string
    {
        return $this->bitSet->toString();
    }

    public function size(): int
    {
        return $this->size;
    }

    public function count(): int
    {
        return count($this->bitSet);
    }

    public function flip(): Board
    {
        return new static($this->size, $this->bitSet->flip());
    }

    public function and(Board $other): Board
    {
        return new static($this->size, $this->bitSet->and(self::boardToBitSet($other)));
    }

    public function or(Board $other): Board
    {
        return new static($this->size, $this->bitSet->or(self::boardToBitSet($other)));
    }

    public function xor(Board $other): Board
    {
        return new static($this->size, $this->bitSet->xor(self::boardToBitSet($other)));
    }

    public function equalsTo(Board $other): bool
    {
        return ($other instanceof self)
            ? $this->bitSet->equalsTo($other->bitSet)
            : $this->toString() === $other->toString();
    }

    public function promoteZero(): Board
    {
        return $this->promote(self::PROMOTE_ZERO);
    }

    public function promoteOne(): Board
    {
        return $this->promote(self::PROMOTE_ONE);
    }

    public function promoteTwo(): Board
    {
        return $this->promote(self::PROMOTE_TWO);
    }

    public function promoteThree(): Board
    {
        return $this->promote(self::PROMOTE_THREE);
    }

    public function promoteFour(): Board
    {
        return $this->promote(self::PROMOTE_FOUR);
    }

    public function promoteHalfOrMore(): Board
    {
        return $this->promote(self::PROMOTE_HALF_OR_MORE);
    }

    public function promoteMajority(): Board
    {
        return $this->promote(self::PROMOTE_MAJORITY);
    }

    public function getIterator()
    {
        return $this->bitSet->getIterator();
    }

    public function toArray()
    {
        return $this->bitSet->toArray();
    }

    private function promote(int $type): self
    {
        $promotedBitSet = self::zeroBitSet($this->size);

        for ($srcLayerSize = $this->size; $srcLayerSize > 1; $srcLayerSize--) {
            $dstLayerSize = $srcLayerSize - 1;
            $srcLayerMask = self::layerMask($this->size, $srcLayerSize);
            $srcLayer = $this->bitSet->and($srcLayerMask);
            $promotedLayer = self::zeroBitSet($this->size);

            if ($type & (self::PROMOTE_ZERO | self::PROMOTE_ONE)) {
                $srcLayer = $srcLayer->flip()->and($srcLayerMask);
            }

            if ($type & (self::PROMOTE_ZERO | self::PROMOTE_FOUR)) {
                $p = $srcLayer->and($srcLayer->rshift(1));
                $p = $p->and($p->rshift($srcLayerSize));
                $promotedLayer = $promotedLayer->or($p);
            }

            if ($type & (self::PROMOTE_ONE | self::PROMOTE_THREE)) {
                $p1 = $srcLayer->and($srcLayer->rshift(1));
                $p1 = $p1->xor($p1->rshift($srcLayerSize));
                $p2 = $srcLayer->xor($srcLayer->rshift(1));
                $p2 = $p2->xor($p2->rshift($srcLayerSize));
                $promotedLayer = $promotedLayer->or($p1->and($p2));
            }

            if ($type & self::PROMOTE_TWO) {
                $p1 = $srcLayer->xor($srcLayer->rshift(1));
                $p1 = $p1->and($p1->rshift($srcLayerSize));
                $p2 = $srcLayer->xor($srcLayer->rshift($srcLayerSize));
                $p2 = $p2->and($p2->rshift(1));
                $promotedLayer = $promotedLayer->or($p1)->or($p2);
            }

            if ($type & self::PROMOTE_MAJORITY) {
                $p1 = $srcLayer->and($srcLayer->rshift(1));
                $p1 = $p1->or($p1->rshift($srcLayerSize));
                $p2 = $srcLayer->and($srcLayer->rshift($srcLayerSize));
                $p2 = $p2->or($p2->rshift(1));
                $promotedLayer = $promotedLayer->or($p1->and($p2));
            }

            if ($type & self::PROMOTE_HALF_OR_MORE) {
                $p1 = $srcLayer->or($srcLayer->rshift(1));
                $p1 = $p1->and($p1->rshift($srcLayerSize));
                $p2 = $srcLayer->or($srcLayer->rshift($srcLayerSize));
                $p2 = $p2->and($p2->rshift(1));
                $promotedLayer = $promotedLayer->or($p1)->or($p2);
            }

            for ($i = 0; $i < $dstLayerSize; $i++) {

                static $rowMasks = [];
                if (!isset($rowMasks[$dstLayerSize][$i])) {
                    $rowMask = self::zeroBitSet($this->size)
                        ->set(...range(0, $dstLayerSize - 1))
                        ->lshift(self::layerShift($srcLayerSize))
                        ->lshift(($srcLayerSize) * $i);
                    $rowMasks[$dstLayerSize][$i] = $rowMask;
                }
                $rowMask = $rowMasks[$dstLayerSize][$i];

                $promotedRow = $promotedLayer->and($rowMask);
                $promotedRow = $promotedRow->rshift($dstLayerSize * $dstLayerSize + $i);
                $promotedBitSet = $promotedBitSet->or($promotedRow);
            }
        }

        return new static($this->size, $promotedBitSet);
    }

    private static function zeroBitSet(int $size): BitSet
    {
        static $bitSets = [];
        return $bitSets[$size] ?? ($bitSets[$size] = static::stringToBitSet(self::bitSetSize($size), '0'));
    }

    private static function oneBitSet(int $size): BitSet
    {
        static $bitSets = [];
        return $bitSets[$size] ?? ($bitSets[$size] = static::stringToBitSet(self::bitSetSize($size), '1'));
    }

    private static function boardToBitSet(Board $board): BitSet
    {
        return ($board instanceof self)
            ? $board->bitSet
            : static::stringToBitSet($board->size(), $board->toString());
    }

    private static function layerMask(int $size, int $layerSize): BitSet
    {
        static $layerMasks = [];

        if (!isset($layerMasks[$size][$layerSize])) {
            $layerMask = self::zeroBitSet($size);
            $j = $layerSize ** 2;
            for ($i = 0; $i < $j; $i++) {
                $layerMask = $layerMask->set($i);
            }
            $layerMask = $layerMask->lshift(self::layerShift($layerSize));
            $layerMasks[$size][$layerSize] = $layerMask;
        }

        return $layerMasks[$size][$layerSize];
    }

    private static function layerShift(int $layerSize): int
    {
        static $layerShifts = [];

        if (!isset($layerShifts[$layerSize])) {
            $layerShift = 0;
            for ($i = 0; $i < $layerSize; $i++) {
                $layerShift += $i ** 2;
            }
            $layerShifts[$layerSize] = $layerShift;
        }

        return $layerShifts[$layerSize];
    }

    private static function boardMask(int $size): BitSet
    {
        static $boardMasks = [];

        if (!isset($boardMasks[$size])) {
            $boardMask = self::zeroBitSet($size);
            for ($i = 1; $i <= $size; $i++) {
                $boardMask = $boardMask->or(self::layerMask($size, $i));
            }
            $boardMasks[$size] = $boardMask;
        }

        return $boardMasks[$size];
    }

    private static function bitSetSize(int $size): int
    {
        static $bitSetSizes = [];

        if (!isset($bitSetSizes[$size])) {
            $bitSetSize = 0;
            for ($i = 1; $i <= $size; $i++) {
                $bitSetSize += $i ** 2;
            }
            $bitSetSizes[$size] = $bitSetSize;
        }

        return $bitSetSizes[$size];
    }
}

プロモーション処理の説明

大部分の機能は実装やメソッド名を読めば理解できるかと思います。(説明放棄)

プロモーション処理は複雑なため、下図の盤面をpromoteMajorityで処理するケースを説明します。

    private function promote(int $type): self
    {
        $promotedBitSet = self::zeroBitSet($this->size);

$promotedBitSetはプロモーション結果を保持するBitSetです。最初は空白の状態です。

        for ($srcLayerSize = $this->size; $srcLayerSize > 1; $srcLayerSize--) {
            $dstLayerSize = $srcLayerSize - 1;
            $srcLayerMask = self::layerMask($this->size, $srcLayerSize);
            $srcLayer = $this->bitSet->and($srcLayerMask);
            $promotedLayer = self::zeroBitSet($this->size);

プロモーション処理は段ごとに行ないます。

$srcLayerSizeはプロモーション元の段のサイズ、$dstLayerSizeはプロモーション先の段のサイズです。

$promotedLayerは、段ごとのプロモーション処理を保持するBitSetです。

下段->中段

ここでは$srcLayerSizeは下段のサイズ=3、$dstLayerSizeは中段のサイズ=2とします。

$srcLayerMaskは下段のマスクです。これと盤面をAND演算したものが$srcLayerです。

            if ($type & self::PROMOTE_MAJORITY) {
                $p1 = $srcLayer->and($srcLayer->rshift(1));
                $p1 = $p1->or($p1->rshift($srcLayerSize));
                $p2 = $srcLayer->and($srcLayer->rshift($srcLayerSize));
                $p2 = $p2->or($p2->rshift(1));
                $promotedLayer = $promotedLayer->or($p1->and($p2));
            }

promoteMajorityの場合、上記の箇所を通ります。

            for ($i = 0; $i < $dstLayerSize; $i++) {

最後に、行ごとにプロモーション処理を行ないます。

                static $rowMasks = [];
                if (!isset($rowMasks[$dstLayerSize][$i])) {
                    $rowMask = self::zeroBitSet($this->size)
                        ->set(...range(0, $dstLayerSize - 1))
                        ->lshift(self::layerShift($srcLayerSize))
                        ->lshift(($srcLayerSize) * $i);
                    $rowMasks[$dstLayerSize][$i] = $rowMask;
                }
                $rowMask = $rowMasks[$dstLayerSize][$i];

$rowMasksは、$promotedLayerでプロモーション先の行ごとに利用するマスクです。

                $promotedRow = $promotedLayer->and($rowMask);
                $promotedRow = $promotedRow->rshift($dstLayerSize * $dstLayerSize + $i);
                $promotedBitSet = $promotedBitSet->or($promotedRow);

$i = 0;

$i = 1;

中段->上段

ここでは$srcLayerSizeは下段のサイズ=2、$dstLayerSizeは中段のサイズ=1とします。

コード自体は下段->中段と同じなので、画像のみ貼っていきます。

$i = 0;

パフォーマンス改善のヒント

各所でstaticキーワードを使って計算結果やインスタンスをキャッシュすることで、重複する処理を少しでも減らすようにしています。

ゲーム

書きたい内容のほとんどは書いてしまったので、実際にゲームを進行させる処理はソースコードを見てください。

重要なポイントだけ以下で抑えます。

盤面の扱い

必須

実際の盤面を表現するには3つのBoardが必要になります。

先手番のBoard $firstBoard
後手番のBoard $secondBoard
中立(最初から置かれているマス)のBoard $neutralBoard

補助

補助的な用途で以下のBoardがあると便利です。

最下段のマスク用Board $groundBoard

コマが置かれているマスのBoard

    protected function occupiedBoard(): Board
    {
        return $this->firstBoard->or($this->secondBoard)->or($this->neutralBoard);
    }

コマが置かれていないマスのBoard

    protected function vacantBoard(): Board
    {
        return $this->occupiedBoard()->flip();
    }

(そのマスにコマが置かれているかどうかに関わらず) コマを置けるマスのBoard

    protected function scaffoldedBoard(): Board
    {
        return $this->groundBoard()->or($this->occupiedBoard()->promoteFour());
    }

コマを置けて、かつ空いているマスのBoard

    public function legalBoard(): Board
    {
        return $this->vacantBoard()->and($this->scaffoldedBoard());
    }

コマを置く際の処理

概要

手番プレイヤーのBoardをOR演算で更新する。
比較用にコマが置かれているBoardを取得する。
ゲームの終了条件を満たしていたら処理を終了する。
先手番と後手番のそれぞれのプレイヤーのBoardについて、4.と5.の処理を行なう。
プレイヤーのBoardをpromoteMajority()したBoardと、legalBoard()でAND演算をして、自動で置かれるマスを計算する。
プレイヤーの手持ちコマ数が、自動で置かれるマス数以下だった場合、自動で置かれるマスすべてにコマを置く。そうでなければ、手持ちコマ数の分だけ置く。
現時点のコマが置かれているBoardを取得する。比較用のBoardと比較して、同じ値なら処理を終了する。
比較用のコマが置かれているBoardを、現時点のコマが置かれているBoardで上書きする。

ソースコード

    private function handleMove(Move $move, int $movesMade): void
    {
        /** @var Board[] $boards */
        $boards = [
            &$this->firstBoard,
            &$this->secondBoard,
        ];

        $playerBoard =& $boards[$movesMade % 2];
        $playerBoard = $playerBoard->or($move->toBoard($this->size));

        $occupiedBoard = $this->occupiedBoard();

        while (true) {
            if ($this->isOver()) {
                break;
            }

            foreach ($boards as &$chainingBoard) {
                $chain = $this->vacantBoard()->and($this->scaffoldedBoard())->and($chainingBoard->promoteMajority());
                $vacancy = $this->piecesPerPlayer - $chainingBoard->count();
                if ($chain->count() <= $vacancy) {
                    $chainingBoard = $chainingBoard->or($chain);
                } else {
                    $chainMoves = static::createMovesFromBoard($chain);
                    for ($i = 0; $i < $vacancy; $i++) {
                        /** @var Move $chainMove */
                        $chainMove = array_lshift($chainMoves);
                        $chainingBoard = $chainingBoard->or($chainMove->toBoard($this->size));
                    }
                }
            }

            $newOccupiedBoard = $this->occupiedBoard();
            if ($occupiedBoard->equalsTo($newOccupiedBoard)) {
                break;
            }

            $occupiedBoard = $newOccupiedBoard;
        }
    }

ベンチマーク

100ゲームを完了するまでの時間を、各実装方法や環境ごとに計測します。

ソースコード

<?php

require_once __DIR__ . '/vendor/autoload.php';

switch ($argv[1]) {
    case 'gmp':
        $createGame = function () {
            // 2021/01/21追記
            // BitSetで抽象化せずにGMPで実装したケース
            return \MosaicGame\Game\GMPOneToOneGame::create(7);
        };
        break;
    case 'gbs':
        $createGame = function () {
            return \MosaicGame\Game\GMPBitSetOneToOneGame::create(7);
        };
        break;
    case 'abs':
        $createGame = function () {
            return \MosaicGame\Game\ArrayBitSetOneToOneGame::create(7);
        };
        break;
    default:
        throw new InvalidArgumentException();
}

$start = microtime(true);

for ($i = 0; $i < 100; $i++) {
    $game = $createGame();
    while (!$game->isOver()) {
        $legalMoves = $game->legalMoves();
        $game->makeMove($legalMoves[0]);;
    }
}

$end = microtime(true);

echo $end - $start, ' seconds', PHP_EOL;

結果

実装方法	実行環境	OPcache	JIT	計測結果(秒)
Array&BitSet	php:7.3-alpine			17.464858055115
Array&BitSet	php:7.3-alpine	✓		16.988431930542
Array&BitSet	php:8.0.1-alpine			15.647920846939
Array&BitSet	php:8.0.1-alpine	✓		16.106576919556
Array&BitSet	php:8.0.1-alpine		✓	16.116796970367
GMP&BitSet	php:7.3-alpine			6.6696288585663
GMP&BitSet	php:7.3-alpine	✓		6.5686361789703
GMP&BitSet	php:8.0.1-alpine			5.6893467903137
GMP&BitSet	php:8.0.1-alpine	✓		5.646008014679
GMP&BitSet	php:8.0.1-alpine		✓	4.2216958999634
GMP	php:7.3-alpine			2.6879260540009
GMP	php:7.3-alpine	✓		2.5570001602173
GMP	php:8.0.1-alpine			2.28826212883
GMP	php:8.0.1-alpine	✓		2.2428948879242
GMP	php:8.0.1-alpine		✓	1.9412138462067

配列よりGMPを利用した方が高速ですね。

OPcacheは何故か効果が見られませんでした。opcache.enable_cli=1としてあるので効いているはずですが…。

JITはGMP利用時のみバッチリ効いてます。

2021/01/21 追記: BitSetを抽象化しないことで50%以上のパフォーマンス改善しました。

C++との比較

GMPではなくstd::bitsetを使ってるので純粋な比較とはいきませんが、参考用に比べてみました。

ソースコード

ゲームの処理に関する速度を比較したいので、ループ部分はPHPに行わせます。

<?php

$ffi = FFI::cdef(
    '
void *create(unsigned char size);
void destroy(void *gamePointer);
bool isOver(void *gamePointer);
char *legalBoard(void *gamePointer);
void makeMove(void *gamePointer, unsigned int offset);
    ',
    __DIR__ . '/libmosaicgame.so',
);

$start = microtime(true);

for ($i = 0; $i < 100; $i++) {
    $gamePointer = $ffi->create(7);
    while (!$ffi->isOver($gamePointer)) {
        $legalBoard = $ffi->legalBoard($gamePointer);
        $legalMoves = array_keys(array_filter(str_split(strrev(FFI::string($legalBoard)))));
        FFI::free($legalBoard);
        $ffi->makeMove($gamePointer, $legalMoves[0]);
    }
    $ffi->destroy($gamePointer);
}

$end = microtime(true);

echo $end - $start, ' seconds', PHP_EOL;

結果

実装方法	実行環境	OPcache	JIT	計測結果(秒)
GMP	php:8.0.1-alpine		✓	1.9412138462067
C++&std::bitset	php:7.4-alpine			0.2579939365387

PHPで最速だったJIT環境と比較しても8倍。

PHPで実装する意味とは。

最後に

いかがでしたか？ここまで書いておいてなンですが、自分で読み返しても分かりづらい記事だなと思います。

ちなみに、本当は2対2のチーム戦で対局するモザイク・クオも実装したかったのですが、あちらは以下のルールが存在します。

あがりの時、コマを置く場所が複数あった場合、どこに最後のコマを置いてあがりにするかは、そのコマの持ち主が決められます。

これをうまく実装できる方法が見つからなかったため頓挫しました。