【ボドゲ】モザイクをPHPで実装してみた【ビットボード】

# 前置き

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

- ビットボードとは？ -> 調べてください。
- モザイクとは？ -> ボードゲームです。[[概要]](https://mosaic.games/blog/mosaic/mosaic_rule/)

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

2021/01/21 追記: 

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

# こんな人向けの記事

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

# 完成品

https://github.com/izayoi256/mosaicgame-php

- 記事内のコードとは異なる部分があります。
- 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(反転)/文字列への変換といった必須の機能を宣言します。

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

``` php
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`というクラスを実装しました。具体的な実装方法は参考元を確認してください。

https://github.com/adagiolabs/bitset/blob/master/src/Adapter/ArrayBitSet.php

### GMPで実装する

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

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

[PHP: GMP - Manual](https://www.php.net/manual/ja/book.gmp.php)

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

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

AND演算を例に上げます。

``` php
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としたインデックスで表現します。

> ![mosaic.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/7a5429c6-2bb6-c39b-3cc1-9016851ce143.png)

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

## インターフェース

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

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

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

``` php
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`に持たせることで、具象クラスの派生が容易になります。

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

``` php
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`で処理するケースを説明します。

> ![promotion01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/bb0fec9e-3352-d929-3618-414e4f1ba8ce.png)

***

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

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

***

``` php
        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`です。

> ![promotion02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/987d7e1e-90e1-aeb7-f430-0ca791196490.png)

***

``` php
            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`の場合、上記の箇所を通ります。

> ![promotion03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/a66024dc-065e-b550-26fc-1e4d818379f3.png)

&nbsp;

> ![promotion04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/eedaf19c-f264-1efd-d3f0-d7aa657f408f.png)

&nbsp;

> ![promotion05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/e15f73bf-3ae8-e4dd-06dc-c1e253fbf9fc.png)

&nbsp;

> ![promotion06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/96b93126-72f4-1589-aae9-5a86ff34d7cd.png)

&nbsp;

> ![promotion07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/cf2bd170-2b32-382d-430c-f886e126ea0c.png)

***

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

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

``` php
                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`でプロモーション先の行ごとに利用するマスクです。

***

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

> $i = 0;
> ![promotion08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/36e55f34-2447-df98-918a-f7f4ed92f22d.png)

&nbsp;

> ![promotion09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/f26c4132-09bb-0ebf-5644-aca55a385f79.png)

&nbsp;

> ![promotion10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/72981c49-7a86-0aeb-ef9c-39687a5e677f.png)


> $i = 1;
> ![promotion11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/51f013d9-930d-a1ec-6d84-85de080373cd.png)

&nbsp;

> ![promotion12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/705e2af8-c8b8-15c4-5ecf-4eaf137e7974.png)

&nbsp;

> ![promotion13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/9fe636cd-4b17-a47c-6f00-54784ae1769f.png)


### 中段->上段

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

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

> ![promotion22.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/eeae3639-4ebd-689e-d974-ba4599e07d3a.png)

&nbsp;

> ![promotion23.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/5932e637-c362-460d-faaa-230493567ca4.png)

&nbsp;

> ![promotion24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/237995c8-c3c8-42f9-4511-c8c7d39fc579.png)

&nbsp;

> ![promotion25.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/75f34b1d-8611-86e5-6b21-50a48580de93.png)

&nbsp;

> ![promotion26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/00f2007c-f400-5f47-33d3-178cd76ed6fc.png)

&nbsp;

> ![promotion27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/7f906a76-28c9-f900-c407-20b341115755.png)

&nbsp;

> $i = 0;
> ![promotion28.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/61e48c39-e131-61e2-a139-a60c5ac230ca.png)

&nbsp;

> ![promotion29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/1464c521-4a40-6a47-0bd6-8bb0516d7533.png)

&nbsp;

> ![promotion30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88941/87d49173-bd97-21c0-0e3e-10086d4a62e4.png)

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

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

# ゲーム

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

https://github.com/izayoi256/mosaicgame-php

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

## 盤面の扱い

### 必須

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

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

### 補助

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

- 最下段のマスク用Board `$groundBoard`

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

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

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

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

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

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

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

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

## コマを置く際の処理

### 概要

1. 手番プレイヤーのBoardをOR演算で更新する。

2. 比較用にコマが置かれているBoardを取得する。

3. ゲームの終了条件を満たしていたら処理を終了する。

4. 先手番と後手番のそれぞれのプレイヤーのBoardについて、4.と5.の処理を行なう。

5. プレイヤーのBoardを`promoteMajority()`したBoardと、`legalBoard()`でAND演算をして、自動で置かれるマスを計算する。

6. プレイヤーの手持ちコマ数が、自動で置かれるマス数以下だった場合、自動で置かれるマスすべてにコマを置く。そうでなければ、手持ちコマ数の分だけ置く。

7. 現時点のコマが置かれているBoardを取得する。比較用のBoardと比較して、同じ値なら処理を終了する。

8. 比較用のコマが置かれているBoardを、現時点のコマが置かれているBoardで上書きする。

### ソースコード

``` php
    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
<?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
<?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のチーム戦で対局する`モザイク・クオ`も実装したかったのですが、あちらは以下のルールが存在します。

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

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