はじめに

この記事は

オリジナルのボードゲームをルールからAIまで作る【概要編】
オリジナルのボードゲームをルールからAIまで作る【ルール編】

からの続きです。
オセロやチェスや将棋のようなボードゲームを考案し、
それを実際に実装してAIと1人プレイできるとこまで目指します。

前回の記事からだいぶ時間が開いてしまいました。
今日はいよいよ実装編-1に入りたいと思います。
タイトルから分かる通り、次に実装編-2が控えてます。

普通のオセロを作る

今回は普通のオセロを作ります。オリジナル要素は次回です。

「『オリジナルのボードゲーム』はどこ行ったんだ、タイトル詐欺じゃないか」という話ですが、ひとまず普通のオセロ、オゼロ(オリジナリティゼロのオセロ)を作るところから始めたいと思います。正直なところこの記事を書いてる時点ではオリジナル要素をまだ思いついてません。次どうしよう。

ごくごくごく普通のオセロを作ることを通して「ここをちょっとイジるだけでオリジナルゲーム作れるじゃん」と勘所を掴んでもらえればと思います。

これです

この記事ではJavascript/HTMLでオセロゲームを作ります。

こんな感じです。

四角いですね。
取ってつけたようなオリジナル要素です。

ここで遊べます。必要最低限のオセロです。
http://xiidec.appspot.com/ozero/ozero.html
ソースコードはここから落とせます。
https://github.com/kurehajime/ozero

オセロゲームの概要

今回作るオセロゲームは以下のファイルから成り立っています。

ファイル名	説明
ozero.html	HTML本体です。ゲーム画面を描画するためのcanvasがあるだけで、ほとんど空っぽです。
game.js	クリックイベントや描画の呼び出しをする真の本体です。
render.js	画面描画を担当します。
ai.js	AIの思考ロジックです。

こういう作りです。

ユーザーが石を置く場所をクリックする
↓
game.jsがai.jsを呼び出す
↓
ai.jsがCPの指し手を生成する
↓
game.jsがCPの指し手を反映した盤面を作り、render.jsに渡す
↓
render.jsが画面上に盤面を描画する

ではひとつひとつ見て行きましょう。

ozero.html

ここから落とせます。

ozero.html

<!DOCTYPE html>
<HTML>
<HEAD>
    <meta content="text/html" charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
</HEAD>
<BODY>
    <canvas id="canv" width="500px" height="500px"></canvas>
    <script src="./render.js"></script>
    <script src="./ai.js"></script>
    <script src="./game.js"></script>
    <script>
        var ctx = document.getElementById("canv").getContext('2d');
        Game.initGame(ctx);
    </script>
    <style>
        #canv {
            height: 500px;
            width: 500px;
            float: left;
        }
    </style>
</BODY>
</HTML>

500×500のcanvas要素がひとつあるだけ。
あとは必要なJavascriptを読み込んでます。
特筆することはありません。

canvasとは、HTMLで図形を描画するための要素です。
ここに線を引いたり、色を塗ったり、グラデーションをかけたりして、ゲーム画面を作ります。
今回は図形だけでゲームを作りますが、画像も貼り付けることができます。物凄い勢いで描画しまくればアニメーションも作れます。ようするになんでもできます。

game.js

ここから落とせます。
以下のソースはだいぶ端折ってるので、コピペするときは上のリンクから落としてください。

game.js

(function (global) {
    "use strict";
    // Class ------------------------------------------------
    function Game() {}

    // Header -----------------------------------------------
    global.Game = Game;
    global.Game.initGame = initGame;

    // ------------------------------------------------------
    var COL = 8;//8x8マスのオセロ
    var ctx;//キャンバス要素
    var evented = false;//イベントを登録したか？
    var state = {}//現在の状態
    var point = {//マウスの座標
        x: 0,
        y: 0
    }
    var init_state = {//ゲーム開始時の盤面の状態
        //盤面(0は何もない場所、1は白、-1は黒)
        map: [0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, -1, 1, 0, 0, 0,
                 0, 0, 0, 1, -1, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0,
                 ],
        //ターン。1は先手、-1は後手。
        turn: 1,
        //これが増えてたら画面を描画し直す。
        revision: 0,
        //どのマスが選択されているかの情報
        selected: {
            name: "",
            value: 0
        }
    };
    //ゲームの開始処理
    function initGame(_ctx) {
        ctx = _ctx;
        state = objCopy(init_state);
        if (!evented) {
            evented = true;
            setEvents();
        }
        Render.render(ctx, state, point);
    }
    //イベントの関連付け
    function setEvents() {
        //マウスが動きた時のイベントの関連付けを行う。
        //マウスをクリックした時のイベントの関連付けを行う。
    }
    //マウスが動いた時の処理
    function ev_mouseMove(e) {
        //マウスの座標を取得する。
        //画面を再描画する(マウスがあたってるマスに色をぬる)。
    }
    //マウスがクリックされた時の処理
    function ev_mouseClick(e) {
        var selected = hitTest(point.x, point.y);
        var number = selected.value;//選択されたマスを求める。
        if (Ai.canPut(state.map, selected.value, state.turn) === true) {//置いてもいい場所かどうか判断

            //プレーヤーが指した手を盤面に反映する。
            state.map = Ai.putMap(state.map, selected.value, state.turn);//プレーヤーの指し手を盤面に反映
            state.turn = -1 * state.turn;//ターンチェンジ
            state.revision += 1;//盤面の状態を更新。
            Render.render(ctx, state, point);//画面を描画する。

            //AIが指した手を盤面に反映する。
            setTimeout(function () {//ちょっと時間差で処理を行う(こうしないと画面描画がもたつく)。
                var _number = Ai.thinkAI(state.map, state.turn, 6)[0];//AIに指し手を考えてもらう。
                state.map = Ai.putMap(state.map, _number, state.turn);//AIの指し手を盤面に反映
                state.turn = -1 * state.turn;//ターンチェンジ
                state.revision += 1;//盤面の状態を更新。
                Render.render(ctx, state, point);//画面を描画する。
            }, 100);
        }
    }
    //マウスの座標を取得
    function hitTest(x, y) {
        //どのマスが選択されたかを返す。
    }


})((this || 0).self || global);

では細かいところを見て行きましょう。
まずは全体を囲んでるこの文。

 (function (global) {

    ～～～～～～～～～～～～

})((this || 0).self || global);

これ、おまじないです。気にしないでください。

最近の行儀のよい JavaScript の書き方 -Qiita

おまじないという言葉で片付けられるとムズムズする人はこの記事を読んでください。

では中身を見ていきましょう。

           map: [ 0,  0,  0,  0,  0,  0,  0,  0,
                  0,  0,  0,  0,  0,  0,  0,  0,
                  0,  0,  0,  0,  0,  0,  0,  0,
                  0,  0,  0, -1,  1,  0,  0,  0,
                  0,  0,  0,  1, -1,  0,  0,  0,
                  0,  0,  0,  0,  0,  0,  0,  0,
                  0,  0,  0,  0,  0,  0,  0,  0,
                  0,  0,  0,  0,  0,  0,  0,  0,
                 ]

盤面を配列で表しています。
なんとなく分かりますね。1が白で、-1が黒です。
この配列をai.jsに渡して指し手を考えて貰ったり、render.jsに渡して盤面を描画してもらいます。

    //ゲームの開始処理
    function initGame(_ctx)

ゲームの初期化処理です。
ここで以下の処理をしています。

ステータスの初期化
クリックイベント等の関連付け
画面を描画する

はいはい次に行きましょう。

//イベントの関連付け
function setEvents()

マウスをクリックした時や、動かした時のイベントを関連付けしています。ここに貼り付けてるソースでは端折っていますが、スマートデバイスではクリックではなくタッチに紐付けるようにしています。

//マウスの座標を取得
function hitTest(x, y)

//マウスが動いた時の処理
function ev_mouseMove(e)

ここではマウスが動いた時の処理を書いています。カーソルをマス目の上に乗せるとそのマスの色がちょっとだけ変わります。描画はrender.jsに任せてます。

//マウスがクリックされた時の処理
function ev_mouseClick(e)

マウスがクリックされた時の処理です。
こんな感じのことをしています。

プレーヤーが指した手を盤面に反映する
ai.jsを呼び出してAIに考えてもらう
AIが考えた指し手を盤面に反映する

game.jsの説明はこれだけです。あっさりですね。
いろいろ端折っていますが、実際のところgame.jsの役目はユーザーの操作を受けてai.jsとrender.jsを呼び出すだけです。

render.js

画面描画部です。
ここから落とせます。
以下のソースは端折っているので(略)

render.js

(function (global) {
    "use strict";
    // Class ------------------------------------------------
    function Render() {}

    // Header -----------------------------------------------
    global.Render = Render;
    global.Render.render = render;
    global.Render.RECT_BOARD = RECT_BOARD;
    global.Render.CELL_SIZE = CELL_SIZE;

    //-------------------------------------
    var COL = 8;
    var RECT_CANV = {//canvasの大きさ
        x: 0,
        y: 0,
        w: 500,
        h: 500
    };
    var RECT_BOARD = {//盤の大きさ
        x: 0,
        y: 0,
        w: 500,
        h: 500
    };
    var CELL_SIZE = RECT_CANV.w / COL | 0;//マスの大きさ

    var prev_revision = -1;//状態のバージョン
    var canv_cache = {//canvas要素のキャッシュ
        canv_board: null,
        canv_pieaces: null,
        canv_effect: null
    };

    //画面を描画する。
    function render(ctx, state, point) {
        if (prev_revision < 0) {//初期状態の場合は、全部描画してキャッシュに保持
            canv_cache.canv_board = drawBoard(state);//何も置かれていない盤を部品として描く
            canv_cache.canv_pieaces = drawPieceALL(state);//石を部品として描く。
            canv_cache.canv_effect = drawEffect(state);//フォーカスの当たってるマスの色を部品として描く。
            Render.RECT_BOARD = RECT_BOARD;//ボードの大きさを定義する。
            Render.CELL_SIZE = CELL_SIZE;//マスのサイズを定義する。
        } else {//初期状態以外では、必要に応じて描画
            if (state.revision != prev_revision) {//盤面が変わっていたら盤面を作りなおす。
                canv_cache.canv_pieaces = drawPieceALL(state);//石を作りなおす。
            }
            canv_cache.canv_effect = drawEffect(state, point);//盤面が変わってなくてもフォーカスの当たってるマスの色などは変える。
        }

        ctx.clearRect(0, 0, RECT_CANV.w, RECT_CANV.h);//canvasをクリアする。
        ctx.drawImage(canv_cache.canv_board, 0, 0, RECT_CANV.w, RECT_CANV.h);//盤を描く
        ctx.drawImage(canv_cache.canv_pieaces, 0, 0, RECT_CANV.w, RECT_CANV.h);//石を描く
        ctx.drawImage(canv_cache.canv_effect, 0, 0, RECT_CANV.w, RECT_CANV.h);//フォーカス色を描く
        prev_revision = state.revision;//あとで比べるために今の状態を記憶
    }
    //盤を描く
    function drawBoard(state) {
        if (!canv_cache.canv_board) {//盤をキャッシュする(何度も作ると無駄だから)。
            canv_cache.canv_board = document.createElement("canvas");
            canv_cache.canv_board.width = RECT_CANV.w;
            canv_cache.canv_board.height = RECT_CANV.h;
        }
        var ctx = canv_cache.canv_board.getContext('2d');
        ctx.clearRect(0, 0, RECT_CANV.w, RECT_CANV.h);//盤のクリアする。

        //盤にグラデーションをつける。

        //盤に線を引く。
        for (var x = 0; x < COL; x++) {
            for (var y = 0; y < COL; y++) {
                ctx.strokeStyle = COLOR_LINE;
                ctx.beginPath();
                ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
                ctx.strokeRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
            }
        }

        //盤にグラデーションをテカテカにする。

        return canv_cache.canv_board;
    }

    //石を全部描く
    function drawPieceALL(state) {
        //盤をキャッシュする(何度も作ると無駄だから)。        

        //ぐるぐるループして石を置く。
        for (var x = 0; x < COL; x++) {
            for (var y = 0; y < COL; y++) {
                if (state.map[y * COL + x] != 0) {
                    drawPiece(ctx, x * CELL_SIZE, y * CELL_SIZE, state.map[y * COL + x]);//石を返す。
                }
            }
        }
        return canv_cache.canv_pieaces;
    }

    //石を1個描く
    function drawPiece(ctx, x, y, number) {

        if (number > 0) {//白なら
            //白石の設定
        } else if (number < 0) {//黒なら
            //黒石の設定
        }

        //影の設定

        //石を描く
        ctx.fillRect(x + CELL_SIZE / 10, y + CELL_SIZE / 10, CELL_SIZE - 1 * CELL_SIZE / 5, CELL_SIZE - 1 * CELL_SIZE / 5);

        return ctx;
    }

    //選択されたマス目に色をぬる。
    function drawEffect(state) {
        //選択されたマス目に色をぬる。
    }

})((this || 0).self || global);

render.jsはちょっとややこしい作りになっています。
やりたいことは、

game.jsから盤面を受け取る。
↓
画面に描画

という単純なことなのですが、描画の負荷を軽減するためにパーツごとに分解し前回の内容を使いまわしています。
ぶっちゃけオセロゲームではそんな面倒くさいことをせず毎回再描画しても問題ないのですが、アクションゲームの場合はこういった工夫が必須になります。

では中身を見て行きましょう。

//画面を描画する。
function render(ctx, state, point)

render()関数。これはgame.jsから呼び出されます。
render.jsの内部には複数の関数が用意されていますが、外部から呼び出されるのはこれだけです。
「とりあえず今の状態を教えてくれれば、描画はこっちでなんとかするよ」というのがrender.jsの仕事です。
game.jsのほうでは、ことあるごとにrender()を呼び出せばいいのです。描画について何も考える必要はありません。馬鹿の一つ覚えでrender()すれば良いのです。

ではrender()関数から呼び出される実務担当者を見て行きましょう。

    //盤を描く
    function drawBoard(state) {
        if (!canv_cache.canv_board) {//盤をキャッシュする(何度も作ると無駄だから)。
            canv_cache.canv_board = document.createElement("canvas");
            canv_cache.canv_board.width = RECT_CANV.w;
            canv_cache.canv_board.height = RECT_CANV.h;
        }
        var ctx = canv_cache.canv_board.getContext('2d');
        ctx.clearRect(0, 0, RECT_CANV.w, RECT_CANV.h);//盤のクリアする。

        //盤にグラデーションをつける。

        //盤に線を引く。
        for (var x = 0; x < COL; x++) {
            for (var y = 0; y < COL; y++) {
                ctx.strokeStyle = COLOR_LINE;
                ctx.beginPath();
                ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
                ctx.strokeRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
            }
        }

        //盤にグラデーションをテカテカにする。

        return canv_cache.canv_board;
    }

何も石が置かれていない盤を描きます。
ここはちょっと詳しく見ていきます。

        if (!canv_cache.canv_board) {//盤をキャッシュする(何度も作ると無駄だから)。
            canv_cache.canv_board = document.createElement("canvas");
            canv_cache.canv_board.width = RECT_CANV.w;
            canv_cache.canv_board.height = RECT_CANV.h;
        }

ここで盤のcanvas要素を生成しています。
大元のcanvas要素に直接描いてもいいのですが、盤の色がゲームの途中で変わったりすることはないので、後で使いまわすために一旦別のcanvasに描くようにしています。

        //盤に線を引く。
        for (var x = 0; x < COL; x++) {
            for (var y = 0; y < COL; y++) {
                ctx.strokeStyle = COLOR_LINE;
                ctx.beginPath();
                ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
                ctx.strokeRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
            }
        }

いよいよ描画っぽいことを始めました。盤に線を引いています。
ctx.strokeStyle = COLOR_LINE;
線の色を指定して、
ctx.beginPath();
線の始まりを宣言し、
ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
塗りつぶし、
ctx.strokeRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
線を引いています。

8x8のループを繰り返しマス目を描画しています。
COLという定数では行と列の数を定義しているので、ここを8ではなく32に設定すれば32x32=1024マスのオセロになります。間違って1024を設定してしまうと1024x1024=百万マスオセロになってしまうので注意しましょう。

では次の関数に行きます。

//石を1個描く
function drawPiece(ctx, x, y, number)
//石を全部描く
function drawPieceALL(state)
//選択されたマス目に色をぬる。
function drawEffect(state)

ここでは石を描画しています。あとマウスの当たってるマスに色を付けてます。
canvasへの描き方は基本的にdrawBoardとおんなじです。canvasの機能を組み合わせて駆使すれば、工夫次第でリッチな画面が作れます。canvasには主にこんな機能があります。

ctx.fillRect()
塗りつぶしの四角形を描く
ctx.strokeRect()
塗りつぶさない四角形を書く
ctx.arc()
丸を描く
ctx.beginPath(),ctx.moveTo(),ctx.closePath(),ctx.stroke()
線を引き始めて、移動し、閉じて、繋ぎます。
ctx.drawImage
画像を貼り付けます。

Canvas - HTML5.JP

このサイトに詳しい解説が描いてあります。

ai.js

ではいよいよAIの実装を見ていきます。

ai.jsではgame.jsの中でも使ってるゲームのルールに関わる関数もあります。本当はrule.jsと別出しした方が理想でしょう。

ここで落とせます。

ai.js

    //(略)

ai.jsはこのような構造になっています。

■便利なツール系
getEffectArray()
ある場所に石を置いた時にひっくり返る場所を返す。
canPut()
置ける場所なのか答えてくれる。
putMap()
石を置いたらどんな盤上になるのか返す。
isEnd()
ゲームが終了しているか教えてくれる。
getWinner()
どっちが勝ったか教えてくれる。

■AIの思考系
thinkAI()
現在の盤面を渡すと、AIが考えて次の一手を返す。
game.jsからはこれが呼ばれる。AIの本体。
後述する
getNodeList()
置ける場所の一覧をリストアップする。
evalMap()
戦況を評価し点数付けする。
deepThinkAllAB()
AIにとって一番点数の高い盤になる次の一手を探索する。
紆余曲折で変な関数名になっていますが気にしないでください。

「■便利なツール系」の実装に関しては説明を割愛します。
ai.jsでは全体でもたった200行のコードですので、日本語で説明するよりコード読んだ方が理解が早いかもしれません。

「■AIの思考系」の関数群について見て行きましょう。

AIの思考はとっても単純です。

AIの番で置ける場所の一覧をリストアップする
↓
AIが仮置きした後、次にﾌﾟﾚｲﾔｰが置ける場所をﾘｽﾄｱｯﾌﾟする。
↓
ﾌﾟﾚｲﾔｰが仮置きした後、次にAIが置ける場所をﾘｽﾄｱｯﾌﾟする。
↓
～設定した深さまでこれを繰り返す～
↓
一番奥深くまで進んだ時の盤面を点数付けする。
↓
～すべての分岐を全部網羅する～
↓
プレイヤーが最善手を指し続けた場合にAIにとって一番点数の高い盤面になる一手を採用する。

こんな感じです。
Wikipediaにある図を見るとイメージしやすいかもしれません。

上の図を見て行きましょう。
自分は点数がプラスになるように、相手は点数がマイナスになるように選ぶと仮定しましょう。
まず自分が0の段で左の枝を選べば相手は1の段で右の枝を選びます。こうなると最終的には-10点になってしまいます。相手が左を選んでくれれば+∞の局面もありますが、相手もそこまでバカじゃありません。たぶん。AIはそういう前提で思考します。
逆に自分が0の段で右の枝を選べば、相手が最善の選択を行った場合でも、自分が間違えない限りどんなに悪くとも-7点で抑えることができます。
よってAIにとっては0の段で右の枝を選ぶのが最善手です。

これをミニマックス法(Wikipedia)と呼びます。
オセロのAIもチェスのAIも将棋のAIもだいたいこんな仕組みです。
バカまじめにミニマックス法で思考するととてもとてもとても時間がかかるので、世に出ている将棋AIなどではより洗練されたアルゴリズムを採用していますが、考え方としてはだいたい同じです。

選択肢をリストアップする(getNodeList)
選択肢を探索する(deepThinkAllAB)
局面に点数をつける(evalMap)

この３つの柱。
オリジナルのボードゲームのAIを作る際も、チェス将棋オセロ系であればこれでいけるはずです。

オリジナル要素を入れる

詳しい解説は次の記事に持ち越しますが、
先ほどの解説の中であった３つの柱。
ここをいじればオリジナルのゲームができるはずです。

選択肢をリストアップする

オセロであれば、「一枚でも相手の石をひっくり返すことの出来る場所」を返す、将棋であれば「駒が動ける場所」を返す、というように『ルールに沿って適切な選択肢を返す』という関数を実装すれば、オリジナルのゲームは半分完成したようなものです。

選択肢を探索する

ここはルールにあまり左右されない部分です。既存のプログラムを使いまわしてもオリジナルのゲームは作れそうです。
しかし強いAIを強くするには重要な要素ですので、改良のしがいがある部分です。サンプルのオセロプログラムではアルファベータ法というミニマックス法の改良型を採用しています。もちろんまだまだ改良の余地はあります。

局面に点数をつける

AIの選択肢を決める要素です。オリジナルのゲームでは当然ここはルールに合わせて手を加える必要あります。既存のゲームのAIもこれによってAIの性格が決まります。単純に点数をつけるだけなら簡単ですが、評価関数の自動学習など突き詰めれば底なし沼のように奥の深い世界です・・・。
ちなみに今回のサンプルオセロでは、単純に石の数をカウントして点数付けしているだけです。暇な人は、端っこのマスの点数を高くするとか、角のマスの点数を高くするとか改良してみてください。

まとめ

今回はなんの工夫もない普通のオセロを作りました。
これに少し手を加えればオリジナルのボードゲームになります。

いろいろ解説を端折って分かりづらい部分も多々ありましたが、「こいつの説明は下手糞だが俺にもできるという事だけは分かった」と思っていだたければ幸いです。

サンプルオセロは全部合わせても543行のプログラムです。
オセロくらいシンプルなルールなら、オリジナルのゲームでもこれくらいの量で最低限遊べるレベルになる・・・はずです。

たぶん続きます。

オリジナルのボードゲームをルールからAIまで作る【実装編-1】

はじめに

普通のオセロを作る

これです

オセロゲームの概要

ozero.html

game.js

render.js

ai.js

オリジナル要素を入れる

選択肢をリストアップする

選択肢を探索する

局面に点数をつける

まとめ