読者です 読者をやめる 読者になる 読者になる
スポンサーリンク

あなたが,勝つことも引き分けることもできない三目並べ (jQueryプラグイン「jQuery.fakeTicTacToe.js」によるマルバツ・ゲーム)

jQuery ゲーム 小ネタ 作品


三目並べゲームには,必勝法は存在しない。

したがって○×ゲームでは,お互いが最善の手を尽くすと,必ず引き分ける。


ところが,下記の三目並べは,CPUが必ず勝つ。あなたは必ず負ける。

三目並べゲームに必勝法が無いはずにも関わらず,ここではCPU必勝なのである。




ウソだと思ったら,下記の動作サンプルで,何ゲームでも戦ってみてほしい。
毎回かならず負けるから…。

jQueryプラグイン「jQuery.fakeTicTacToe.js」 動作デモページ
http://jquery-fake-tic-tac-toe-js.goo...

※スマートフォン・タブレットでも遊べる。



このjQueryプラグインの使用法は,リンク先のGoogle Codeのプロジェクトページに詳しく書いてある。

自由に改変したり,自分のWebサイトに埋め込んだりすることができる。

オープンソース・MITライセンス。



下記では,このjQueryプラグインのソースコードをかいつまんで追いかけることにより,

CPUを必勝とするアルゴリズムの概要を手短に説明する。

プラグインのソースコードの概要

下記のURLから,ソースコード全体を閲覧できる。

jquery.fakeTicTacToe.js(Google CodeのGitリポジトリ)
https://code.google.com/p/jquery-fake...


プロジェクトのトップページ
https://code.google.com/p/jquery-fake...


まず,冒頭部分。

(function(jQuery){

        // 公開メソッド
        jQuery.fn.fakeTicTacToe = function() {
                //return this.each(function() {
                        setupOneBoard(this);
                //});
        };
       
        jQuery.fakeTicTacToeRetry = function() {
                resetOneBoard();
        };

ここでは,jQueryプラグインとして外部に公開するメソッドを定義している。

ゲームの開始メソッドは,$("セレクタ").fakeTicTacToe() という用途を想定しているので,プロトタイプチェイン上に設置する。

一方,ゲームの終了メソッドは,セレクタを介さずにどこからでも呼ばれうるため,静的メソッドとしてある。

1ページ内でゲーム盤の個数は1個でかまわないだろう,という考えから,eachによるイテレーションは実装しないでおいた。

jQuery プラグインの定義パターンについて調べてみた(by id:cyokodog氏)
http://d.hatena.ne.jp/cyokodog/200911...

  • jQueryオブジェクト($)に対して直接メソッドをくっつけるのが,関数 API 系。プロトタイプチェイン上(fn)にメソッドを乗っけるのが,メソッド API 系。
    • メソッドAPI系:プラグイン定義の際に使用される jQuery.fn はjQuery.prototype の別名。jQuery セレクタで要素を取得すると・・・jQuery インスタンスは、jQuery.prototype に定義された関数郡を、自身が保有するメソッドのように扱う

jQuery Pluginの書き方
http://tech.kayac.com/archive/jquery-...

  • メソッドチェインを切らさないようにするには,最後にreturn this;する
  • 複数要素が指定されている場合,thisをeachで処理


JavaScriptの動かないコード (中級編) オブジェクトのprototypeを変更した時のエラー
http://language-and-engineering.hatenablog.jp/entry/20080922/1222010471

  • prototypeとは,new後に「困ったときのデフォルトの参照先」
  • JSの言語仕様として,オブジェクトの__proto__([ [Prototype] ] )にデフォルトで代入されるのがprototype
        /* ------- メッセージ ------- */
       
       
        var FTMSG = {
                msg_en : {

このゲームは,ブラウザの利用言語が英語の場合にも対応している。

そのため,文言を国際化し,ブラウザの言語設定から利用メッセージを判定・取得している。

        /* ------- ゲーム全体 ------- */
       
       
        // セットアップ
        var setupOneBoard = function( divElement )
        {

ここでは,ゲーム盤を生成し,各セルに押下イベントをセットして,

ユーザ側に最初の一手を促すところまで。


そして,次の関数以降は,ゲーム版全体の状態をデータ構造として裏側で保持しておくためのこまごました処理が続く。

       
        // 特定のコマタイプがリーチ状態にあるかどうかの詳細情報を返す。
        // 第二引数には,検査したいマップを渡す。
        var getReachInfo = function( pieceType, targetMap ){

この関数は重要である。

ゲーム盤全体を満遍なくスキャンすることにより,

ユーザが勝ちそうな状態か,すなわち「CPUにとってピンチの事態が発生しているかどうか」を判定するメソッドなのだから・・・。

        /* ------- ユーザ ------- */
       
       
        // ユーザが一手を打ったとき
        var onRvCellClicked = function( x, y )
        {
                if( ! isTurnOfUser ) return;
                if( ! isBlankCell( x, y ) ) return;
               
                execTurnOfUser(x, y);
        };
        var execTurnOfUser = function(x, y){
                // コマを置く
                recordPieceOnBoard({ is_user : true, x : x, y : y });
               
                // ゆずる
                isTurnOfUser = false;
                alertRv(FTMSG._("cpus_turn"));
                setTimeout(
                        execTurnOfCPU,
                        2000
                );
        };

ユーザがセルをクリック(タップ)した時のイベントである。

そのセルにコマを設置し,CPUに手を譲るだけ。



ここから先のコードに,次第に,うさんくさい怪しさが・・・。

        /* ------- CPU ------- */
       
       
        // CPUの一手
        var execTurnOfCPU = function(){
                var stra = createCPUStrategy();
                stra.exec();
        };
       
        // CPUの戦略を考え,JSONで返す
        var createCPUStrategy = function(){
       
                // 最善の手を考える
                var normal_stra = getNormalBestStrategy();
               
                // 最善の手を打っても負けるか引き分ける?
                if( requiresFakeOn( normal_stra ) )
                {
                        // 危機に瀕しているので,インチキをする
                        return {
                                exec : function(){ execFakeOnPinch(); }
                        };
                }
                else
                if( ( countAllPieces() <= 9 - 3 - 2 ) && ( Math.random() < 0.2 ) )
                {
                        // 一定の確率で,危機に瀕していなくてもインチキをする。
                        // 条件は,3倍速で動いた後に,ラリーが一回続くこと。
                        return {
                                exec : function(){ execFakeSpeed( normal_stra ); }
                        };
                }
                else
                {
                        // インチキなしで続行
                        return normal_stra;
                }
               
        };
       
        // まっとうな最善の戦略を考える
        var getNormalBestStrategy = function(){
               
                // NOTE: 3目並べは,お互いに最善の手を打った場合,必ず引き分けになる。
               
               
                // 自分が3つ並ぶならそうする
                var reachInfoCPU = getReachInfo( 0, cellsMap );
                if( reachInfoCPU.flagged )
                {
                        return {
                                exec : function(){ putPieceOfCPU( reachInfoCPU.flaggedCell ); },
                                target : reachInfoCPU.flaggedCell
                        };
                }
               
                // 相手が3つ並ぶなら妨害する
                var reachInfoUser = getReachInfo( 1, cellsMap );
                if( reachInfoUser.flagged )
                {
                        return {
                                exec : function(){ putPieceOfCPU( reachInfoUser.flaggedCell ); },
                                target : reachInfoUser.flaggedCell
                        };
                }
               
                // できれば中央に置く
                if( isBlankCell( 1, 1 ) ){
                        return {
                                exec : function(){ putPieceOfCPU( { x : 1, y : 1 } ); },
                                target : { x : 1, y : 1 }
                        };
                }
               
                // できればどれか隅に置く
                var stra_corner = null;
                $.each( [ 0, 2 ], function(){
                        var x_corner = this;
                        $.each( [ 0, 2 ], function(){
                                var y_corner = this;
                               
                                if( isBlankCell( x_corner, y_corner ) ){
                                        stra_corner = {
                                                exec : function(){ putPieceOfCPU( { x : x_corner, y : y_corner } ); },
                                                target : { x : x_corner, y : y_corner }
                                        };
                                }
                        } );
                } );
                if( stra_corner ) return stra_corner;
               
                // 何でもいいのでランダムな空きマスに置く
                for( var i = 0; i < 3; i ++ )
                {
                        for( var j = 0; j < 3; j ++ )
                        {
                                if( isBlankCell( i, j ) ){
                                        return {
                                                exec : function(){ putPieceOfCPU( { x : i, y : j } ); },
                                                target : { x : i, y : j }
                                        };
                                }
                        }
                }
               
        };

まず,CPUは,最初から邪悪なわけではない。

できるだけまっとうな戦略を採ろうとするのだ。

このコード中で示されているアルゴリズムこそ,三目並べの「最善の手」を打つための確立された方法である。


この戦略をとる限り,決して負ける事はない,という事が知られている。

もし双方のプレーヤがこの戦略でプレーしたら,かならず引き分けとなることが証明されている。

この手順をミスった場合にのみ,三目並べには「負け」という状態が存在しうるのだ。



ちなみに,何気なくStrategyパターンが使用されていることにお気づきだろうか?

createCPUStrategy も getNormalBestStrategy も,戦略(ストラテジー)オブジェクトを返すメソッドである。

返却されたJSONオブジェクトは,exec() でその戦略を実行可能,という点で共通したインタフェースを持つようにしている。

Javaのデザインパターンと異なるのは,各戦略オブジェクトに対して,exec() の実装を言語的に強制はしていない(インタフェースオブジェクトの指定とかがない)という点だけだ。

GoFの23のデザインパターンを,Javaで活用するための一覧表 (パターンごとの要約コメント付き)
http://language-and-engineering.hatenablog.jp/entry/20120330/p1

  • Strategy: アルゴリズム切り替え。アルゴリズム実装のための専用オブジェクト

で,問題は,この先の

// 危機に瀕しているので,インチキをする

// 一定の確率で,危機に瀕していなくてもインチキをする。

の部分。

ここでCPUが牙をむき始める。



        /* ------- CPUによるインチキ工作 ------- */
       
       
        // インチキが必要か判定
        var requiresFakeOn = function( strat ){
                // NOTE: 8手目までに必ず勝つ必要がある。9マス目をユーザが打つことはない。
               
                // 最善の手を打っても負けるか引き分けるか,を判定。
               
                // 現在のボードのコピー
                //var mapCopy = $.merge( [], cellsMap ); > 参照コピーになって干渉してしまう
                var mapCopy = getNewNullMap();
                for(var i = 0; i < 3; i ++)
                {
                        for( var j = 0; j < 3; j ++ )
                        {
                                mapCopy[i][j] = cellsMap[i][j];
                        }
                }
               
                // CPUが一手打ったシミュレーション
                mapCopy[ strat.target.x ][ strat.target.y ] = 0;
                        debug("count = " + countAllPieces());
                       
                // この仮想状況でもユーザにリーチの可能性があるか,または8手目でゲーム完了しないか?
                if(
                        ( getReachInfo( 1, mapCopy ).flagged )
                        ||
                        ( ( countAllPieces() == 7 ) && ( ! isCPUCompleted( mapCopy ) ) )
                )
                {
                        return true;
                }
                else
                {
                        return false;
                }
        };

まっとうな方法では勝てない,ということを確認するために,

CPUは一度,まっとうな手をシミュレーションする。

仮想的なマップ上で,一手打ってみるのである。


それでもダメだったら,いよいよ裏工作に走る。


具体的なインチキ工作については,

エフェクトで「むなしさ」を表現することを心がけた。

この部分はコードよりも,実際のゲームにおいて,負け続ける楽しみをぜひ味わって頂きたい。


結び

「何と不毛なプラグイン・・・」と,

呆れて口がふさがらないリアクションを引き出すことができたら,

このプラグインの目的は果たせたことになる。


プレーしてみると意外とはまる。お試しあれ。

補足

下記のページで,ソースコードリーディングの対象として紹介されている。

jQuery.fakeTicTacToe.js | 「三目並べ(ゲーム)」カテゴリー | JavaScriptデモ
http://javascript-demo.e1blue.net/js/...

関連する記事:

わずか1.7キロバイトのJavaScript マリオ風のゲーム (脱力系)
http://language-and-engineering.hatenablog.jp/entry/20081006/1223209263


jQuery をSQLの「select文」のように使う方法
http://language-and-engineering.hatenablog.jp/entry/20081004/1223056859


あなたが理解できない,たった一行のRubyのコード (動的言語に対する静的解析の限界)
http://language-and-engineering.hatenablog.jp/entry/20120619/p1