LoginSignup
2
2
@tsu_eng(つ)

【コピペで動くよ！】JavaScriptでビットボードを用いたオセロ盤を実装する

Last updated at Posted at 2024-07-17

はじめに

JavaScriptは32bit整数しかサポートしてないからビットボードで実装できないな～って思ってたら、今はそんなことなかったっぽいので実装してみました。

各ブラウザの対応状況

BigInt()使えるやん
image.png

Swiftで実装した記事

ロジックはこちらを丸パクリ参考にします。

ソースコード

盤はSVGで描画しました。

index.html
<!DOCTYPE html>
<html>
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
    <title>オセロ棋譜再生</title>
    <script src="./board.js"></script>
    <style>
        * {
            margin: 0;
            padding: 0;
            touch-action: manipulation;
        }
        .button-list {
            display: flex;
            justify-content: space-between;
            width: 100%;
        }

        button {
            flex: 1;
            margin: 0 5px;
        }
    </style>
</head>
<body>
<div id="board" style="width: 100%"></div>
<div class="button-list">
    <button onmouseup="moveStart(board)">｜＜</button>
    <button onmouseup="movePrev(board)">＜＜</button>
    <button onmouseup="moveNext(board)">＞＞</button>
    <button onmouseup="moveLast(board)">＞｜</button>
</div>
<script>
    const queryParams = new URLSearchParams(window.location.search);
    const params = Object.fromEntries(queryParams.entries());
    const kifu = params.kifu ?? '';
    const initBoard = params.board ?? '';
    const start = params.start ?? 0;
    const board = new Board(kifu, initBoard, Number(start));

    board.makeBoard(board.currentKifu);
    board.drawBoard();
</script>
</body>
</html>
board.js
class Board {
    BLACK_TURN = 100;
    WHITE_TURN = -100;
    nowTurn;
    playerBoard;
    opponentBoard;
    inputBoard;
    inputKifu;
    currentKifu;
    currentMoveCount;
    moveTotalCount;

    constructor(kifu, inputBoard, start = 0) {
        this.inputBoard = inputBoard;
        this.initBoard(this.inputBoard);
        this.inputKifu = kifu ?? '';
        this.moveTotalCount = this.inputKifu.length / 2;
        this.currentMoveCount = start;
        this.currentKifu = kifu.substr(0, start * 2)
    }

    initBoard(inputBoard) {
        this.nowTurn = this.BLACK_TURN;
        this.currentKifu = '';

        if (inputBoard !== '') {
            let black = 0n;
            let white = 0n;
            let index = 0;
            for (let i = 0; i < 8; i++) {
                for (let j = 0; j < 8; j++) {
                    const char = inputBoard.charAt(index++);
                    if (char === "x") {
                        black |= 1n << BigInt(i * 8 + j);
                    } else if (char === "o") {
                        white |= 1n << BigInt(i * 8 + j);
                    }
                }
            }

            this.playerBoard = black;
            this.opponentBoard = white;
        } else {
            // 一般的な初期配置を指定
            this.playerBoard = 0x0000000810000000n;
            this.opponentBoard = 0x0000001008000000n;
        }
    }

    /**
     * 着手し,反転処理を行う
     * @param put 着手した場所のみにフラグが立つ64ビット
     */
    reverse(put) {
        let rev = BigInt(0);
        for (let k = 0; k < 8; k++) {
            let rev_ = BigInt(0);
            let mask = this.transfer(put, k);
            while ((mask !== BigInt(0)) && ((mask & this.opponentBoard) !== BigInt(0))) {
                rev_ |= mask;
                mask = this.transfer(mask, k);
            }
            if ((mask & this.playerBoard) !== BigInt(0)) {
                rev |= rev_;
            }
        }
        this.playerBoard ^= put | rev;
        this.opponentBoard ^= rev;
    }

    /**
     * 手番の入れ替え
     */
    swapBoard() {
        [this.playerBoard, this.opponentBoard] = [this.opponentBoard, this.playerBoard];
        this.nowTurn *= -1;
    }

    /**
     * 反転箇所を求める
     * @param put 着手した場所のみにフラグが立つ64ビット
     * @param k   反転方向(8つ)
     * @return bigint
     */
    transfer(put, k) {
        switch (k) {
            case 0: //上
                return (put << 8n) & 0xffffffffffffff00n;
            case 1: //右上
                return (put << 7n) & 0x7f7f7f7f7f7f7f00n;
            case 2: //右
                return (put >> 1n) & 0x7f7f7f7f7f7f7f7fn;
            case 3: //右下
                return (put >> 9n) & 0x007f7f7f7f7f7f7fn;
            case 4: //下
                return (put >> 8n) & 0x00ffffffffffffffn;
            case 5: //左下
                return (put >> 7n) & 0x00fefefefefefefen;
            case 6: //左
                return (put << 1n) & 0xfefefefefefefefen;
            case 7: //左上
                return (put << 9n) & 0xfefefefefefefe00n;
            default:
                return 0n;
        }
    }

    /**
     * 座標をbitに変換する
     * @param x 横座標(A~H)
     * @param y 縦座標(1~8)
     * @return bigint
     */
    coordinateToBit(x, y) {
        let mask = BigInt("0x8000000000000000");
        // X方向へのシフト
        switch (x) {
            case "A":
                break;
            case "B":
                mask >>= 1n;
                break;
            case "C":
                mask >>= 2n;
                break;
            case "D":
                mask >>= 3n;
                break;
            case "E":
                mask >>= 4n;
                break;
            case "F":
                mask >>= 5n;
                break;
            case "G":
                mask >>= 6n;
                break;
            case "H":
                mask >>= 7n;
                break;
            default:
                break;
        }
        // Y方向へのシフト
        let intY = BigInt(parseInt(y, 10));
        mask >>= ((intY - BigInt(1)) * 8n);

        return mask;
    }

    drawBoard(lastMove) {
        const boardDiv = document.getElementById("board");
        const frameHeight = 760;
        const boardFrameSize = 670;
        const boardSize = 576;
        const cellSize = 72;
        const labelSize = 20;
        const labelFontSize = 28;
        const boardPadding = (boardFrameSize - boardSize) / 2 + labelSize;
        if (this.currentKifu) {
            lastMove = this.currentKifu.substring(this.currentKifu.length - 2);
        }

        const bitLastMove = lastMove && lastMove !== '--'
            ? this.coordinateToBit(lastMove.substring(0, 1), lastMove.substring(1))
            : BigInt(0);

        // 既存のSVGが存在する場合、削除する
        if (boardDiv.firstChild) {
            boardDiv.removeChild(boardDiv.firstChild);
        }

        // 新しいSVGを追加する
        const boardSvg = document.createElementNS("http://www.w3.org/2000/svg", "svg");
        boardSvg.setAttribute("viewBox", "0 0 " + boardFrameSize + " " + frameHeight);

        // オセロ盤を描画する
        const rect = document.createElementNS("http://www.w3.org/2000/svg", "rect");
        rect.setAttribute("x", "0");
        rect.setAttribute("y", "0");
        rect.setAttribute("width", `${boardFrameSize}`);
        rect.setAttribute("height", `${boardFrameSize}`);
        rect.setAttribute("fill", "#3fb8dd");
        rect.setAttribute("rx", "8");
        boardSvg.appendChild(rect);

        // オセロ盤の線を描画する
        for (let i = 0; i <= 8; i++) {
            const verticalLine = document.createElementNS("http://www.w3.org/2000/svg", "line");
            verticalLine.setAttribute("x1", `${i * cellSize + boardPadding}`);
            verticalLine.setAttribute("y1", `${boardPadding}`);
            verticalLine.setAttribute("x2", `${i * cellSize + boardPadding}`);
            verticalLine.setAttribute("y2", `${boardSize + boardPadding}`);
            verticalLine.setAttribute("stroke", "#333366");
            verticalLine.setAttribute("stroke-width", "1");
            boardSvg.appendChild(verticalLine);

            const horizontalLine = document.createElementNS("http://www.w3.org/2000/svg", "line");
            horizontalLine.setAttribute("x1", `${boardPadding}`);
            horizontalLine.setAttribute("y1", `${i * cellSize + boardPadding}`);
            horizontalLine.setAttribute("x2", `${boardSize + boardPadding}`);
            horizontalLine.setAttribute("y2", `${i * cellSize + boardPadding}`);
            horizontalLine.setAttribute("stroke", "#333366");
            horizontalLine.setAttribute("stroke-width", "1");
            boardSvg.appendChild(horizontalLine);
        }

        // 星を描画する
        for (let i = 0; i < 2; i++) {
            for (let j = 0; j < 2; j++) {
                const cell = document.createElementNS("http://www.w3.org/2000/svg", "circle");
                cell.setAttribute("cx", String(cellSize * 3 + i * cellSize * 4 - 5));
                cell.setAttribute("cy", String(cellSize * 3 + j * cellSize * 4 - 5));
                cell.setAttribute("fill", "#333366");
                cell.setAttribute("r", "4");
                boardSvg.appendChild(cell);
            }
        }

        const rowText = ["1", "2", "3", "4", "5", "6", "7", "8"];
        for (let i = 0; i < 8; i++) {
            const text = document.createElementNS("http://www.w3.org/2000/svg", "text");
            text.setAttribute("x", `${labelSize}`);
            text.setAttribute("y", `${cellSize * (i + 1) + ((cellSize - labelFontSize) / 2) + labelSize}`);
            text.setAttribute("fill", "#333366");
            text.setAttribute("font-size", `${labelFontSize}`);
            text.textContent = rowText[i];
            boardSvg.appendChild(text);
        }

        const colText = ["A", "B", "C", "D", "E", "F", "G", "H"];
        for (let i = 0; i < 8; i++) {
            const text = document.createElementNS("http://www.w3.org/2000/svg", "text");
            text.setAttribute("x", `${cellSize * (i + 1) + ((cellSize - labelFontSize) / 2)}`);
            text.setAttribute("y", `${labelSize + labelSize}`);
            text.setAttribute("fill", "#333366");
            text.setAttribute("font-size", `${labelFontSize}`);
            text.textContent = colText[i];
            boardSvg.appendChild(text);
        }

        // 盤面の描画
        let count = 1;
        for (let i = 8; i > 0; i--) {
            for (let j = 8; j > 0; j--) {
                const cell = document.createElementNS("http://www.w3.org/2000/svg", "circle");
                cell.setAttribute("cy", String((i - 0.5) * cellSize + boardPadding));
                cell.setAttribute("cx", String((j - 0.5) * cellSize + boardPadding));
                cell.setAttribute("r", "28");
                if (Number(this.playerBoard.toString(2)[this.playerBoard.toString(2).length - count])) {
                    if (this.nowTurn === this.BLACK_TURN) {
                        cell.setAttribute("fill", "black");
                    } else {
                        cell.setAttribute("fill", "white");
                    }
                } else if (Number(this.opponentBoard.toString(2)[this.opponentBoard.toString(2).length - count])) {
                    if (this.nowTurn === this.BLACK_TURN) {
                        cell.setAttribute("fill", "white");
                    } else {
                        cell.setAttribute("fill", "black");
                    }
                } else {
                    cell.setAttribute("fill", "#3fb8dd");
                }
                boardSvg.appendChild(cell);

                // 最終手にマーク
                if (Number(bitLastMove.toString(2)[bitLastMove.toString(2).length - count])) {
                    const marker = document.createElementNS("http://www.w3.org/2000/svg", "rect");
                    marker.setAttribute("y", String((i - 0.5) * cellSize + boardPadding - 4));
                    marker.setAttribute("x", String((j - 0.5) * cellSize + boardPadding - 4));
                    marker.setAttribute("fill", "red");
                    marker.setAttribute("width", "8");
                    marker.setAttribute("height", "8");
                    boardSvg.appendChild(marker);
                }

                count++;
            }
        }

        // 情報パネル
        const infoRect = document.createElementNS("http://www.w3.org/2000/svg", "rect");
        infoRect.setAttribute("x", "0");
        infoRect.setAttribute("y", `${boardFrameSize + 5}`);
        infoRect.setAttribute("width", `${boardFrameSize}`);
        infoRect.setAttribute("height", "60");
        infoRect.setAttribute("fill", "#aaa");
        boardSvg.appendChild(infoRect);

        for (let i = 0; i < 2; i++) {
            const cell = document.createElementNS("http://www.w3.org/2000/svg", "circle");
            cell.setAttribute("cx", `${100 * i + 80}`);
            cell.setAttribute("cy", "705");
            cell.setAttribute("fill", `${i === 0 ? "#333" : "#fff"}`);
            cell.setAttribute("r", "20");
            boardSvg.appendChild(cell);

            const turnMarker = document.createElementNS("http://www.w3.org/2000/svg", "circle");
            turnMarker.setAttribute("cx", `${100 * i + 40}`);
            turnMarker.setAttribute("cy", "705");
            turnMarker.setAttribute("fill", `${i === 0 && this.nowTurn === this.BLACK_TURN || i === 1 && this.nowTurn === this.WHITE_TURN ? "#fefd68" : "#ccc"}`);
            turnMarker.setAttribute("r", "8");
            boardSvg.appendChild(turnMarker);

            const text = document.createElementNS("http://www.w3.org/2000/svg", "text");
            text.setAttribute("x", `${100 * i + 80}`);
            text.setAttribute("y", "712");
            text.setAttribute("text-anchor", "middle");
            text.setAttribute("fill", `${i === 0 ? "#fff" : "#333"}`);
            text.setAttribute("font-size", "22");
            text.textContent = `${i === 0 ? this.bitCount(this.opponentBoard) : this.bitCount(this.playerBoard)}`;
            boardSvg.appendChild(text);
        }

        // 手数
        const moveCountText = document.createElementNS("http://www.w3.org/2000/svg", "text");
        moveCountText.setAttribute("x", `${350}`);
        moveCountText.setAttribute("y", "712");
        moveCountText.setAttribute("text-anchor", "middle");
        moveCountText.setAttribute("fill", "#333");
        moveCountText.setAttribute("font-size", "22");
        moveCountText.textContent = this.currentKifu.length / 2 + ':';
        boardSvg.appendChild(moveCountText);
        boardDiv.appendChild(boardSvg);

        // 最終手の座標
        const moveText = document.createElementNS("http://www.w3.org/2000/svg", "text");
        moveText.setAttribute("x", `${400}`);
        moveText.setAttribute("y", "712");
        moveText.setAttribute("text-anchor", "middle");
        moveText.setAttribute("fill", "#333");
        moveText.setAttribute("font-size", "22");
        moveText.textContent = this.currentKifu.length < 2 ? "--" : this.currentKifu.substr(-2, 2);
        boardSvg.appendChild(moveText);
        boardDiv.appendChild(boardSvg);
    }

    /**
     * ビットカウント
     * @param num: UINT64
     * @return 立ってるフラグの数[Int]
     */
    bitCount(num) {
        let mask = BigInt("0x8000000000000000");
        let count = 0;

        for (let i = 0n; i < 64; i++) {
            if (mask & num) {
                count += 1;
            }
            mask >>= 1n;
        }
        return count;
    }

    makeBoard(kifu) {
        this.initBoard(this.inputBoard);
        this.currentKifu = kifu;
        const length = this.currentKifu.length / 2;
        for (let i = 0; i < length; i++) {
            const x = kifu.substring(i * 2, i * 2 + 1);
            const y = kifu.substring(i * 2 + 1, i * 2 + 2);

            // パス判定
            if (x === '-' && y === '-') {
                board.swapBoard();
            } else {
                const put = board.coordinateToBit(x, y);
                board.reverse(put);
                board.swapBoard();
            }
        }
    }

    incrementMoveCount(count) {
        if (count < this.inputKifu.length / 2) {
            return count + 1;
        } else {
            return count;
        }
    }

    decrementMoveCount(count) {
        if (count > 0) {
            return count - 1;
        } else {
            return count;
        }
    }
}

function movePrev(board) {
    board.currentMoveCount = board.decrementMoveCount(board.currentMoveCount);
    board.currentKifu = board.inputKifu.substring(0, board.currentMoveCount * 2);
    board.makeBoard(board.currentKifu);
    board.drawBoard();
}

function moveNext(board) {
    board.currentMoveCount = board.incrementMoveCount(board.currentMoveCount);
    board.currentKifu = board.inputKifu.substring(0, board.currentMoveCount * 2);
    board.makeBoard(board.currentKifu);
    board.drawBoard();
}

function moveStart(board) {
    board.currentKifu = '';
    board.currentMoveCount = 0;
    board.makeBoard(board.currentKifu);
    board.drawBoard();
}

function moveLast(board) {
    board.currentKifu = board.inputKifu;
    board.currentMoveCount = board.moveTotalCount;
    board.makeBoard(board.currentKifu);
    board.drawBoard();
}

動かしてみる

index.htmlとboard.jsを同じ階層に置いて、index.htmlをブラウザで開くとオセロ盤が表示されます。
アドレスバーのindex.htmlの後ろに ?kifu=F5D6C3... と入力すれば棋譜を再生できます。
パスは--で表現します。
image.png

その他

着手可能判定や盤面をクリックして着手などの機能は実装していないので、興味のある方はこのコードを修正して実装してみてください。

2
2
0

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
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2