JavaScriptとミニマックス法を用いて三目並べ（〇×ゲーム）を作ってみる

bubudoufu

3年前

このページではソースコードの一部分を簡単な解説をしています。

ソースコードはgithubにあります 。
その他、作成したアプリやゲームの一覧はこちらにあります。

概要
ミニマックス法概要
JavaScriptでミニマックス法をプログラムする

概要

コンピュータと三目並べで対戦できます。先手か後手を選びクリックするとゲームが開始されます。相手より先に三つ同じ色を縦・横・斜めのいずれかに並べれば勝ちのゲームです。以前作成した三目並べは三つ置ける場所や阻止する場所がない場合はランダムにマスに置くようにコンピュータ側の指し手をプログラムしたため弱かったですが、今回はミニマックス法を用いてコンピュータの指し手をプログラムをしたので先手・後手ともに最善を尽くすと、必ず引き分けとなります。コンピュータ側が負けることはありません。

以前作成した三目並べの記事は↓です。

HTMLとCSSとJavaScriptを使って三目並べ（〇×ゲーム）を作ってみる

このページではソースコードの一部分を簡単な解説をしています。完成品で遊ぶにはコチラから完成品のソースコードはgithubにあります三目並べゲーム概要先手・後手をプレイヤーが選びコンピューターと対戦できます。相手より先に三つ同じ色を縦・横・斜...

勝敗表機能を実装しました。ブログ記事は↓にあります。

PHPとSqliteとJavaScriptを使って勝敗を管理してみる

このページではソースコードの一部分を簡単な解説をしています。サンプルのソースコードはgithubにあります。概要いままで作成したゲームの中で三目並べなどコンピューターと対戦できるゲームの戦績を管理する表を作りました。データベースはSql...

ミニマックス法概要

ゲーム木

現在の局面から着手可能な手を指したそれぞれの局面について、同じように着手可能な手を繰り返し調べていくとゲーム木と呼ばれる木の形になります。

ミニマックス法

展開したゲーム木の末端ノードに評価値を付け、末端ノードの一つ前のノードが自分の手番の局面であれば評価値が最大(Max)となるノードを選択し、相手の手番であれば評価値が最小(Mini)となるノードを選択します。この作業をルートノードへ戻るまで繰り返していき、指し手を決めます。

JavaScriptでミニマックス法をプログラムする

今回作成したプログラムは空いているマスの全局面を勝負がつくまで再帰的に関数を実行します。勝負がついた時の評価値は自分が勝った場合10、相手の勝ちの場合-10、引き分けは0としています。下記のプログラムを実行すると↓の局面でXを置く場所をindex番号で返しconsole.logに表示させます。

let board =
["O", 1, "X",
 "X", 4, "X",
  6, "O", "O"];

let board =

["O", 1, "X",

"X", 4, "X",

6, "O", "O"];

"use strict";
const huPlayer = "O"; // 人間
const aiPlayer = "X"; // コンピュータ

let board = 
  ["O", 1, "X", 
   "X", 4, "X", 
    6, "O", "O"];

function minimax(board, player) {
  // 空いているマスを探す
  let emptyIndex = emptyIndexies(board);
  // 勝敗がついた時の評価値と置いた場所を保持
  let result = {};
  // resultオブジェクトの評価値を比較して良かったほうを保持
  let best = {};
  // 初期値設定
  if (player == aiPlayer) {
    best.score = -1000;
  } else {
    best.score = 1000;
  }

  // 勝ち、負け、引き分けなどに応じて評価値を付ける
  if (winning(board, huPlayer)) {
    return { score: -10 };
  } else if (winning(board, aiPlayer)) {
    return { score: 10 };
  } else if (emptyIndex.length === 0) {
    return { score: 0 };
  }

  emptyIndex.forEach(function (cell) {
    // マスに置く
    board[cell] = player;
    // 手番を変えて再度minimax関数を実行する
    if (player == aiPlayer) {
      result = minimax(board, huPlayer);
    } else {
      result = minimax(board, aiPlayer);
    }
    // 置いたマスを空にする
    board[cell] = cell;
    // 置いたマスを記録
    result.index = cell;

    if (player == aiPlayer) {
      if (result.score > best.score) best = result;
    } else {
      if (result.score < best.score) best = result;
    }
  });
  
  // 呼び出し元に評価値を返す
  return best;
}

console.log(minimax(board, aiPlayer).index)

// 空いているマスを探す
function emptyIndexies(board) {
  return board.filter((s) => s != "O" && s != "X");
}

// 勝敗を調べる
function winning(board, player) {
  if (
    (board[0] == player && board[1] == player && board[2] == player) ||
    (board[3] == player && board[4] == player && board[5] == player) ||
    (board[6] == player && board[7] == player && board[8] == player) ||
    (board[0] == player && board[3] == player && board[6] == player) ||
    (board[1] == player && board[4] == player && board[7] == player) ||
    (board[2] == player && board[5] == player && board[8] == player) ||
    (board[0] == player && board[4] == player && board[8] == player) ||
    (board[2] == player && board[4] == player && board[6] == player)
  ) {
    return true;
  } else {
    return false;
  }
}

"use strict";

const huPlayer = "O"; // 人間

const aiPlayer = "X"; // コンピュータ

let board =

["O", 1, "X",

"X", 4, "X",

6, "O", "O"];

function minimax(board, player) {

// 空いているマスを探す

let emptyIndex = emptyIndexies(board);

// 勝敗がついた時の評価値と置いた場所を保持

let result = {};

// resultオブジェクトの評価値を比較して良かったほうを保持

let best = {};

// 初期値設定

if (player == aiPlayer) {

best.score = -1000;

} else {

best.score = 1000;

}

// 勝ち、負け、引き分けなどに応じて評価値を付ける

if (winning(board, huPlayer)) {

return { score: -10 };

} else if (winning(board, aiPlayer)) {

return { score: 10 };

} else if (emptyIndex.length === 0) {

return { score: 0 };

}

emptyIndex.forEach(function (cell) {

// マスに置く

board[cell] = player;

// 手番を変えて再度minimax関数を実行する

if (player == aiPlayer) {

result = minimax(board, huPlayer);

} else {

result = minimax(board, aiPlayer);

}

// 置いたマスを空にする

board[cell] = cell;

// 置いたマスを記録

result.index = cell;

if (player == aiPlayer) {

if (result.score > best.score) best = result;

} else {

if (result.score < best.score) best = result;

}

});

// 呼び出し元に評価値を返す

return best;

}

console.log(minimax(board, aiPlayer).index)

// 空いているマスを探す

function emptyIndexies(board) {

return board.filter((s) => s != "O" && s != "X");

}

// 勝敗を調べる

function winning(board, player) {

if (

(board[0] == player && board[1] == player && board[2] == player) ||

(board[3] == player && board[4] == player && board[5] == player) ||

(board[6] == player && board[7] == player && board[8] == player) ||

(board[0] == player && board[3] == player && board[6] == player) ||

(board[1] == player && board[4] == player && board[7] == player) ||

(board[2] == player && board[5] == player && board[8] == player) ||

(board[0] == player && board[4] == player && board[8] == player) ||

(board[2] == player && board[4] == player && board[6] == player)

) {

return true;

} else {

return false;

}

↓は上記プログロムを可視化したものです。

赤枠1番から実行されます。この枠では勝負がついていない局面があるので手番を変えて２番緑枠で再度minimax関数が実行されます。２番緑枠では勝負がつき評価値が出そろったので点数を比較して呼び出し元の１番赤枠へ評価値と置いた場所を返します。２番緑枠は相手の手番なので評価値が最小(Mini)となるノードを選択します。この場合はどちらも-10なので比較する必要はないのですが左側のindex番号4と評価値-10が呼び出し元の1番赤枠へ返されます。同様に３番枠、４番枠の順に実行されます。４番枠はindex番号4と評価値10を3番枠に返し、3番枠では返ってきた評価値を比較して呼び出し元の1番枠へ返します。3番枠は相手の手番なので-10の局面を呼び出し元の1番枠へ返します。1番枠の局面の評価値が出そろったので比較します。1番枠は自分の手番なので評価値が最大(Max)となるノードを選択します。この場合は真ん中の10点がついている局面を選択し、置いたマスのindex番号が返されます。

全体のソースコードはgithubにあります。
最後までお読みいただきありがとうございました。