JavaScript でオセロを実装する(一人二役で指す寂しいゲーム編)

2013年 07月 02日

問題

今年も弊社に新卒採用で入社された方が何名かいます。
採用情報ページに記載されているように、
弊社ではメンター制度が設けられており、
誰かしら指導役の社員が面倒を見たり見なかったりします。
ただ指導するにはまず相手の力量を測る必要があります。
技術者として採用された方を相手にするなら、
適当な課題を与えて、それに対して作り上げたモノを見るのが一番手っ取り早いです。

と言う訳で「適当な課題」として今回は「オセロを実装する」ことにしました。
しかしこれだけではテキトー過ぎるので、以下のように段階を設定しました:

1. 黒も白も人間が指す一人二役の寂しいオセロを実装する。

盤面のサイズは4×4とする。
外観やUIは凝らなくてよい。
実装はJavaScriptで行い、Webブラウザで遊べるものにする。

2. 仮AIを実装する。このAIの手筋は以下の通り:

取り得る手のうち最も上の行に石を置ける手を選ぶ。
同一行に指せる手が複数あるなら最も左の列に石を置ける手を選ぶ。

3. 本格的なAIを実装する。このAIの手筋は以下の通り:

最大4手先まで読み、取り得る盤面のうち最も「優勢」な盤面に辿り着く手を選ぶ。
AIの手番を読む時はAIにとって最も「優勢」な盤面になる手を選ぶ。
人間の手番を読む時は人間にとって最も「優勢」な盤面になる手を選ぶ。
AIは同じ盤面に対して常に同じ手を指す。
「優勢」度合いの判定は凝らなくてよい。

4. 盤面を6×6や8×8に拡大する。

拡大に伴って処理すべきデータ量が増大するのでパフォーマンスが落ちる。快適に遊べるようパフォーマンスを改善すること。

各段階での狙いとしては

オセロくらいのロジックはサクサク組める。
「誰が手を指すのか」を見越して抽象化した処理を書ける。
再帰的なロジックがサクサク組める。
ボトルネックを見つけ出して適切な対処を取ることができる。

といったところです。

が、課題を設定した人間がこれくらいサクサク書けなくては話になりませんよね。
と言う訳で実際に実装してみることにしましょう。
できれば昨今のビッグウェーブであるところの
関数型プログラミング
に乗っかった形で書けばかっこいいんじゃないでしょうか。

(なお、実際に作成したオセロのソースコードはGitHubで公開されており、完成品で遊ぶこともできます)

設計

オセロのある局面は

盤面の状態
誰の手番か
ここから指し得る手

で構成されます。
手を指した後は別の局面に変わりますが、
やはり同じ要素で構成されています。
つまり、オセロは局面が節点で手が枝の木構造で表現できます。

これなら

初期配置を根とするゲーム木を作る。
ゲーム開始時に「現在の局面」がゲーム木の根を指すよう初期化する。
「現在の局面」から取り得る手を提示してユーザーに選ばせる。
選んだ手の先にある局面を「現在の局面」に変える。

とすれば一人二役のオセロは簡単に作れそうですね。
必要な状態も「現在の局面」だけなので、
大半を関数型で書き進めることができます。

基礎作成

設計方針が固まったところでまずは基礎部分を作成しましょう。
Webブラウザで遊べるものを作るので、
まずはHTML/CSS/JavaScriptのテンプレートを作りましょう。
ついでに jQuery と Twitter Bootstrap もダウンロードしておきます。

index.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>Othello JS</title>
    <link href="vendor/twitter-bootstrap/css/bootstrap.min.css" rel="stylesheet">
    <link href="vendor/twitter-bootstrap/css/bootstrap-responsive.min.css" rel="stylesheet">
    <link href="app.css" rel="stylesheet">
  </head>
  <body>
    <div id="main" class="container">
      <div id="game-board"></div>
      <div id="current-player">Current player: <span id="current-player-name">-</span></div>
      <div id="message"></div>
      <div id="console"></div>
    </div>

    <script src="vendor/jquery/jquery-1.9.1.min.js"></script>
    <script src="vendor/twitter-bootstrap/js/bootstrap.min.js"></script>
    <script src="app.js"></script>
  </body>
</html>

app.css

#main
{
  text-align: center;
}

#game-board > table
{
  margin: 0 auto;
}

#game-board > table th
{
  margin: 0;
  padding: 0.125em 0.25em;
  line-height: 100%;
}

#game-board > table .cell
{
  background: #090;
  border: 1px solid #ccc;
  padding: 0;
  margin: 0;
  line-height: 0;
}
#game-board > table .cell > .disc
{
  display: inline-block;
  width: 2em;
  height: 2em;
  border-radius: 1em;
  margin: 0.25em;
}
#game-board > table .cell.white > .disc
{
  background: #fff;
}
#game-board > table .cell.black > .disc
{
  background: #000;
}

app.js

(function () {
  var N = 4;  // TODO: 後で拡大する。
})();

盤面の作成、表示

ロジックから作り始めても良いのですが、
取り敢えず目に見える物がある方が安心できるので、
盤面の作成と表示を先に作りましょう。

まずは初期配置の盤面を作る関数 makeInitialGameBoard を定義しましょう:

var EMPTY = 'empty';
var WHITE = 'white';
var BLACK = 'black';

function makeInitialGameBoard() {
  var board = {};

  for (var x = 0; x < N; x++)
    for (var y = 0; y < N; y++)
      board[[x, y]] = EMPTY;

  var x2 = x >> 1;
  var y2 = y >> 1;
  board[[x2 - 1, y2 - 1]] = WHITE;
  board[[x2 - 1, y2 - 0]] = BLACK;
  board[[x2 - 0, y2 - 1]] = BLACK;
  board[[x2 - 0, y2 - 0]] = WHITE;

  return board;
}

盤面の表示処理は <table> を作って #game-board に差し込む形にしましょう:

function drawGameBoard(board, player) {
  var ss = [];

  ss.push('<table>');
  for (var y = -1; y < N; y++) {
    ss.push('<tr>');
    for (var x = -1; x < N; x++) {
      if (0 <= y && 0 <= x) {
        ss.push('<td class="');
        ss.push('cell');
        ss.push(' ');
        ss.push(board[[x, y]]);
        ss.push('">');
        ss.push('<span class="disc"></span>');
        ss.push('</td>');
      } else if (0 <= x && y == -1) {
        ss.push('<th>' + 'abcdefgh'[x] + '</th>');
      } else if (x == -1 && 0 <= y) {
        ss.push('<th>' + '12345678'[y] + '</th>');
      } else /* if (x == -1 && y == -1) */ {
        ss.push('<th></th>');
      }
    }
    ss.push('</tr>');
  }
  ss.push('</table>');

  $('#game-board').html(ss.join(''));
  $('#current-player-name').text(player);
}

試しに drawGameBoard(makeInitialGameBoard(), BLACK); とすれば……

なんだかそれっぽい盤面が表示されました。やりましたね。

ゲーム木の作成

さて、ここからが本題です。
まずはゲーム中のある局面(=ゲーム木)を作る関数 makeGameTree を定義しましょう。
先述のように、ゲーム中のある局面は

盤面
手番のプレイヤー
取り得る手

から構成されますから、これをそのままコードで表現すれば良いので簡単ですね。
ただ、オセロは「二人連続でパスしたらゲーム終了」なので、
「前の手番がパスしたかどうか」も必要になります:

function makeGameTree(board, player, wasPassed) {
  return {
    board: board,
    player: player,
    moves: listPossibleMoves(board, player, wasPassed)
  };
}

次に「取り得る手」を列挙する関数 listPossibleMoves を定義しましょう。
「取り得る手」は

攻撃する手
パス

の2種類です。
パスに関しては「攻撃できないならパスする」というルールになっているので、
「攻撃できる手を列挙する」関数と「必要ならパスする手を補完する」関数に分離しましょう:

function listPossibleMoves(board, player, wasPassed) {
  return completePassingMove(
    listAttackingMoves(board, player),
    board,
    player,
    wasPassed
  );
}

「必要ならパスする手を補完する」関数 completePassingMove は

攻撃できる手があるならパスできない
攻撃できる手がなく、直前の手番でパスされていなければパスできる
二人連続でパスしたらゲーム終了

というルールをそのままコードで表現するだけなので簡単ですね:

function completePassingMove(attackingMoves, board, player, wasPassed) {
  if (0 < attackingMoves.length) {
    return attackingMoves;
  } else if (!wasPassed) {
    return [{
      isPassingMove: true,
      gameTree: makeGameTree(board, nextPlayer(player), true)
    }];
  } else {
    return [];
  }
}

「攻撃できる手を列挙する」関数 listAttackingMoves
は全てのマスを調べて石が置ける手を列挙してくだけなので、
これも簡単ですね:

function listAttackingMoves(board, player) {
  var moves = [];

  for (var x = 0; x < N; x++) {
    for (var y = 0; y < N; y++) {
      if (canAttack(board, x, y, player)) {
        moves.push({
          x: x,
          y: y,
          gameTree: makeGameTree(
            makeAttackedBoard(board, x, y, player),
            nextPlayer(player),
            false
          )
        });
      }
    }
  }

  return moves;
}

これでゲーム木の作成はできました。
簡単過ぎて拍子抜けしちゃいますね。

細々としたユーティリティの作成

と、まあ、ここまでは楽勝だったのですが、
それは面倒臭いことを全て別の関数に丸投げしていたからでした。
さすがにここからはサボれないので丸投げしていた関数を一つづつ定義しましょう。

nextPlayer は次の手番のプレイヤーを返すだけの簡単な関数です:

function nextPlayer(player) {
  return player == BLACK ? WHITE : BLACK;
}

canAttack は石が置けるかどうかの判定をする関数です。
ロジックを書き始めると大変なので
「ある盤面であるマスに石を置いた時に自分のものになるマスがどれだけあるか」
を列挙する関数 listVulnerableCells があるとして、
これを使って定義しましょう:

function canAttack(board, x, y, player) {
  return listVulnerableCells(board, x, y, player).length;
}

makeAttackedBoard は石を置いた後の盤面を作る関数です。
これも listVulnerableCells があれば
「元の盤面をコピーしてから必要な箇所だけ石を置き換える」
だけになるので定義は簡単になります:

function makeAttackedBoard(board, x, y, player) {
  var newBoard = JSON.parse(JSON.stringify(board));
  var vulnerableCells = listVulnerableCells(board, x, y, player);
  for (i = 0; i < vulnerableCells.length; i++)
    newBoard[vulnerableCells[i]] = player;
  return newBoard;
}

ただ listVulnerableCells に関してはサボりようがありません。
あるマスに石が置けるかどうかは

そのマスにどの石も置かれておらず
上下左右斜めに敵の石が1個以上連続して存在し
その後に自分の石が存在する

ことなので、これをそのまま書き下しましょう。
もっと簡単に書けそうなのですが、
あまり凝っても仕方が無いので愚直に書くことにします:

function listVulnerableCells(board, x, y, player) {
  var vulnerableCells = [];

  if (board[[x, y]] != EMPTY)
    return vulnerableCells;

  var opponent = nextPlayer(player);
  for (var dx = -1; dx <= 1; dx++) {
    for (var dy = -1; dy <= 1; dy++) {
      if (dx == 0 && dy == 0)
        continue;
      for (var i = 1; i < N; i++) {
        var nx = x + i * dx;
        var ny = y + i * dy;
        if (nx < 0 || N <= nx || ny < 0 || N <= ny)
          break;
        var cell = board[[nx, ny]];
        if (cell == player && 2 <= i) {
          for (j = 0; j < i; j++)
            vulnerableCells.push([x + j * dx, y + j * dy]);
          break;
        }
        if (cell != opponent)
          break;
      }
    }
  }

  return vulnerableCells;
}

ところで、よくよく見ると同じマスに対して
canAttack と makeAttackedBoard から2回も
listVulnerableCells を呼んでいます。
無駄と言えば無駄なのですが、
今の段階では分かり易さを優先して効率に関しては度外視することにします。

UIの作成

これで必要な道具は一通り揃ったので、
次は最低限操作に必要なUIを作りましょう。
理想としては盤面をクリックして石を置きたいところですが、
それは面倒臭いです。
なので今の段階では手抜きをして、
各手を選ぶためのボタンを作って提示する形にします:

function setUpUIToChooseMove(gameTree) {
  $('#message').text('Choose your move.');
  gameTree.moves.forEach(function (m, i) {
    $('#console').append(
      $('<input type="button" class="btn">')
      .val(makeLabelForMove(m))
      .click(function () {
        shiftToNewGameTree(m.gameTree);
      })
    );
  });
}

UIは適当にするとはいえ、
少なくともボタンのラベルくらいはちゃんとしたものにしておきましょうか:

function makeLabelForMove(move) {
  if (move.isPassingMove)
    return 'Pass';
  else
    return 'abcdefgh'[move.x] + '12345678'[move.y];
}

ボタンやメッセージを表示する前に、
前の手番向けに表示されたものはリセットする必要があります。
これを行なう処理も定義しておきましょう:

function resetUI() {
  $('#console').empty();
  $('#message').empty();
}

ゲームが終了した場合に結果を表示する処理も必要ですね:

function showWinner(board) {
  var nt = {};
  nt[BLACK] = 0;
  nt[WHITE] = 0;

  for (var x = 0; x < N; x++)
    for (var y = 0; y < N; y++)
      nt[board[[x, y]]]++;

  $('#message').text(
    nt[BLACK] == nt[WHITE]
    ? 'The game ends in a draw.'
    : 'The winner is ' + (nt[WHITE] < nt[BLACK] ? BLACK : WHITE) + '.'
  );
}

また、ゲーム終了後に新しくゲームを始めるためのUIも必要ですね:

function setUpUIToReset() {
  $('#console').append(
    $('<input type="button" class="btn">')
    .val('Start a new game')
    .click(function () {
      resetGame();
    })
  );
}

新しいゲームを始める処理も定義しましょう:

function resetGame() {
  shiftToNewGameTree(makeGameTree(makeInitialGameBoard(), BLACK, false));
}

最後に「次の局面へ移動する」処理を定義しましょう:

function shiftToNewGameTree(gameTree) {
  drawGameBoard(gameTree.board, gameTree.player, gameTree.moves);
  resetUI();
  if (gameTree.moves.length == 0) {
    showWinner(gameTree.board);
    setUpUIToReset();
  } else {
    setUpUIToChooseMove(gameTree);
  }
}

ゲームの実行

これで必要な道具が全て揃いました。
後は画面ロード後にresetGame()を呼べば一人二役でボタン式とはいえオセロが遊べます。
具体的には以下のような感じです:

おお……UIと石の配置可否は面倒でしたが、
それ以外は驚くほど簡単に定義することができました。
しかもUIに関するもの以外は全て関数型で書くこともできました。
やりましたね。

次回予告

しかし、この実装には快適に遊ぶに当たって大きな問題があるのだった……!

< 前の記事へ次の記事へ >

2024年6月14日

RubyKaigi 2024参加レポート（by CTO）

#人事ブログ