LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@miyatama(NAOYUKI MIYATA)

自分で作ったミニマックスと三目並べで対決する

Posted at

はじめに

Erlangの勉強がてらアルゴリズムクイックリファレンスをやっていて、ミニマックスまでできたので、自分のプログラムと対決する。本にある通り、三目並べ。別名、〇×ゲーム。ちなみに、三目並べは英語でtic-tac-toeらしい(この本で知った)。

ミニマックスをざっくり説明すると

打てる可能性のある手を全部調べて勝てる可能性のある手を返すアルゴリズム

作ったやつはmiyatama/tictactoeにアップした。分かんない所とかは本買って調べて欲しい。
ちなみに、使ってるとエラーが出るけど調べてない。
興味がある方は是非解決法を教えて欲しい。

IFを作る

コンソールは味気ないのでWebアプリにする。Erlang x WebApp = cowboyなので、cowboyを使う。
イメージはこんな感じ

01_appimage.png

自分で書いてて思うけど、デザイナーさんってすごいですね！

必ずユーザが先行としてシーケンスを進める想定

05_sequence.png

さっそくプロジェクトを用意する

rebar3 new release tictactoe

rebar.confにcowboyの参照を追加する

{deps, [
  {jsone, "1.5.6"},
  {cowboy, "2.8.0"}
]}.

./apps/tictactoe/src/tictactoe.app.srcにもcowboyを追加

{applications,
   [kernel,
    stdlib,
    cowboy
   ]},

プラグインをインストール

rebar3 upgrade

Webページへのルートを追加する

apps/tictactoe/src/tictactoe_app.erl
start(_StartType, _StartArgs) ->
  Dispatch = cowboy_router:compile([
    {'_', [
      {
        "/", 
        cowboy_static, 
        {
          priv_file, 
          tictactoe, 
          "index.html"
        }
      },
      {
        "/img/[...]",
        cowboy_static,
        {priv_dir,tictactoe,"img",[{mimetypes, cow_mimetypes, all}]}
      },
      {
        "/css/[...]",
        cowboy_static,
        {priv_dir,tictactoe,"css",[{mimetypes, cow_mimetypes, all}]}
      },
      {
        "/js/[...]",
        cowboy_static,
        {priv_dir,tictactoe,"js",[{mimetypes, cow_mimetypes, all}]}
      }
    ]}]),
    {ok, _} = cowboy:start_clear(http, [{port, 8080}],
      #{
        env => #{dispatch => Dispatch}
      }),
    rest_sup:start_link().

stop(_State) ->
    ok = cowboy:stop_listener(http).

Webページを配置する。

mkdir -p apps/tictactoe/priv/css
mkdir -p apps/tictactoe/priv/js
mkdir -p apps/tictactoe/priv/img
touch apps/tictactoe/priv/index.html
touch apps/tictactoe/priv/css/index.css
touch apps/tictactoe/priv/js/main.js
apps/tictactoe/priv/index.html
<!DOCTYPE html>
<html>
  <head>
    <title>human vs minimax</title>
    <link rel="stylesheet" type="text/css" href="./css/index.css"/>
    <script type="text/javascript" src="./js/main.js"></script>
  </head>
  <body>
    <div class="game-control-panel">
      <input class="reset_game_button" id="reset_button" type="button" value="reset"></input>
    </div>
    <div id="cpu_panel" class="cpu_panel" >
      <img class="avator_image" src="./img/cpu_avator.png"/>
      <div class="avator_serifu_panel cpu_avator_serifu" id="cpu_fukidashi_panel">
        <p id="cpu_serifu">よろしくおねがいします</p>
      </div>
    </div>
    <div class="geme-center-panel">
      <div id="game_panel" class="game-panel">
        <img id="pos_1_1" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_1_2" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_1_3" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_2_1" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_2_2" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_2_3" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_3_1" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_3_2" class="game_position_img" src="./img/empty_position.png"/>
        <img id="pos_3_3" class="game_position_img" src="./img/empty_position.png"/>
      </div>
    </div>
    <div id="user_panel" class="user-panel" >
      <div class="avator_serifu_panel user_avator_serifu" id="cpu_fukidashi_panel">
        <p id="user_serifu">よろしくおねがいします</p>
      </div>
      <img class="avator_image" src="./img/user_avator.png"/>
    </div>
  </body>
</html>
apps/tictactoe/priv/index.css
body {
  background-color: #08182f;
}

.game-control-panel {
  display: flex;
  justify-content: center;
}

.reset_game_button {
  margin-top: 1rem;
  margin-right: 1rem;
  margin-left: 1rem;
  margin-bottom: 1rem;
  width: 20rem;
}

.cpu_panel {
  width: 40rem;
  height: 5rem;
  display: flex;
}

.user-panel {
  float: right;
  width: 40rem;
  height: 5rem;
  display: flex;
  margin-right: 0rem;
}

.geme-center-panel {
  display: flex;
  justify-content: center;
}

.game-panel {
  display: grid;
  grid-template-columns: 5rem 5rem 5rem;
  grid-template-rows: 5rem 5rem 5rem;
  grid-gap: 0.5rem;
  margin-top: 1rem;
  margin-bottom: 1rem;
  margin-left: 1rem;
  margin-right: 1rem;
}

.game_position_img {
  width: 5rem;
  height: 5rem;
}

.avator_image {
  width: 5rem;
  height: 5rem;
}

.avator_serifu_panel {
  width: 25rem;
  min-width: 25rem;
  background-color: #A988Af;
}

.cpu_avator_serifu {
  position: relative;
  display: inline-block;
  margin: 0rem 0 1.5em 15px;
  padding: 7px 10px;
  max-width: 100%;
  color: #555;
  font-size: 16px;
  background: #e0edff;
}

.cpu_avator_serifu:before {
  content: "";
  position: absolute;
  top: 50%;
  left: -30px;
  margin-top: -15px;
  border: 15px solid transparent;
  border-right: 15px solid #e0edff;
}


.cpu_avator_serifu p {
  margin: 0;
  padding: 0;
}

.user_avator_serifu {
  position: relative;
  display: inline-block;
  margin: 1rem 1rem 0rem 0rem;
  padding: 7px 10px;
  max-width: 100%;
  color: #555;
  font-size: 16px;
  background: #e0edff;
}

.user_avator_serifu:before {
  content: "";
  position: absolute;
  top: 50%;
  left: 100%;
  margin-top: -1rem;
  border: 15px solid transparent;
  border-left: 15px solid #e0edff;
}

.user_avator_serifu p {
  margin: 0;
  padding: 0;
}
apps/tictactoe/priv/js/main.js
var autoMode = true;
var cpuThinking = false;
var noside = true;
var cpuSerifu;
var userSerifu;
var troutes;
var troutStates;

window.addEventListener('load', (event) => {
  cpuSerifu = document.getElementById("cpu_serifu");
  userSerifu = document.getElementById("user_serifu");
  troutes = [
    document.getElementById("pos_1_1"),
    document.getElementById("pos_1_2"),
    document.getElementById("pos_1_3"),
    document.getElementById("pos_2_1"),
    document.getElementById("pos_2_2"),
    document.getElementById("pos_2_3"),
    document.getElementById("pos_3_1"),
    document.getElementById("pos_3_2"),
    document.getElementById("pos_3_3")
  ];
  troutStates = [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ];
  troutes.forEach(trout => {
    trout.onclick = function() {onClickTrout(trout)};
  });
  var reset_button = document.getElementById("reset_button")
  reset_button.onclick = function() {resetGameScene(); };
  resetGameScene();
});

function resetGameScene() {
  let helloText = "よろしくおねがいします";
  setCpuSerifu(helloText);
  setUserSerifu(helloText);
  troutStates = [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ];
  setTroutInitImage();
  cpuThinking = false;
  noside = false;
}

function setTroutInitImage() {
  troutes.forEach(trout => {
    trout.src = "./img/empty_position.png";
  });
}

function setTroutCpu(x, y) {
  var id = "pos_" + x + "_" + y;
  var node = document.getElementById(id);
  setStateFromId(id, 2);
  node.src = "./img/cpu_mark.png";
}

function onClickTrout(e) {
  console.log(e);

  // もうゲームが終わっている場合
  if (noside) {
    return;
  }

  var state = getStateFromId(e.id);
  // 初期状態以外は何もしない
  console.log("state is " + state);
  if (state !== 0) {
    return;
  }

  setCpuSerifu("うーん...");
  setUserSerifu("そこっ！");
  setStateFromId(e.id, 1);
  e.src = "./img/user_mark.png";

  if(autoMode) {
    dmyCpu();
  } else {
    callCpuThink();
  }
}

function setCpuSerifu(text) {
  cpuSerifu.innerText = text;

}

function setUserSerifu(text) {
  userSerifu.innerText = text;
}

function getStateFromId(id) {
  return troutStates[getStateIndexFromId(id)];
}

function setStateFromId(id, value) {
  troutStates[getStateIndexFromId(id)] = value;
}

function getStateIndexFromId(id) {
  var index = 0;
  switch(id) {
    case "pos_1_1":
      index = 0;
      break;
    case "pos_1_2":
      index = 1;
      break;
    case "pos_1_3":
      index = 2;
      break;
    case "pos_2_1":
      index = 3;
      break;
    case "pos_2_2":
      index = 4;
      break;
    case "pos_2_3":
      index = 5;
      break;
    case "pos_3_1":
      index = 6;
      break;
    case "pos_3_2":
      index = 7;
      break;
    case "pos_3_3":
      index = 8;
      break;
  }
  return index;
}


function dmyCpu() {
  positions = [
    [1,1],
    [1,2],
    [1,3],
    [2,1],
    [2,2],
    [2,3],
    [3,1],
    [3,2],
    [3,3]
  ];
  var moved = false;
  positions.forEach((position, index) => {
    if (!moved && troutStates[index] === 0) {
      setTroutCpu(position[0], position[1]);
      moved  = true;
    }
  });
}

function callCpuThink() {
  cpuThinking = true;
  var request = new XMLHttpRequest();
  var postData = createCpuThinkPostData();
  request.addEventListener("load", loadCpuThink);
  request.addEventListener("progress", updateProgressCpuThink);
  request.addEventListener("load", transferCompleteCpuThink);
  request.addEventListener("error", transferFailedCpuThink);
  request.open("POST", "http://localhost/cpu_think");
  request.setRequestHeader("Content-Type", "application/json");
  request.setRequestHeader("Accept", "application/json");
  console.log('post data: ', postData);
  request.responseType = 'json';
  request.send(postData);
}

function createCpuThinkPostData() {
  var jsonObject = new Object();
  jsonObject.troutes = troutStates;
  return JSON.stringify(jsonObject);
}

function loadCpuThink(evt) {
  setCpuSerifu("ダイブ!!!!!!!");
}

function updateProgressCpuThink (oEvent) {
  let min = 1;
  let max = 5;
  let serifuNo = Math.floor(Math.random() * (max - min) + min); 
  var text = "";
  switch(serifuNo) {
    case 1:
      text = "えーっと...";
      break;
    case 2:
      text = "うーん...";
      break;
    case 3:
      text = "これだと...";
      break;
    case 4:
      text = "まいったね...";
      break;
    case 5:
      text = "まじでまいったね...";
      break;
  }
  setCpuSerifu(text);
}

function transferCompleteCpuThink (evt) {
  setCpuSerifu("おらぁ！");
  let result = evt.currentTarget.response;
  if(result.succeed) {
    setTroutCpu(result.x,result.y);
  } 
  checkGameState();
  cpuThinking = false;
}

function transferFailedCpuThink(evt) {
  setCpuSerifu("思考停止しました。リセットしてください。。");
  cpuThinking = false;
}

function checkGameState() {
  let gamestate = calculateGameState(troutStates);
  var gameset = false;
  switch(gamestate){
    case 1:
      // user win
      setUserSerifu("や　　っ　　た　　ぜ　　！");
      setCpuSerifu("ち　　く　　し　　ょ　　う");
      gameset = true;
      break;
    case 2:
      // cpu win
      setCpuSerifu("や　　っ　　た　　ぜ　　！");
      setUserSerifu("ち　　く　　し　　ょ　　う");
      gameset = true;
      break;
  }

  if(gameset) {
    noside = true;
  }
}

function calculateGameState(troutStates) {
  var lines = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [0, 4, 8],
    [2, 4, 6]
  ];
  var winSide = 0;
  lines.forEach(line => {
    if (winSide === 0) {
      if(troutStates[line[0]] === troutStates[line[1]] &&
        troutStates[line[1]] === troutStates[line[2]]) {
          if( troutStates[line[0]] == 1) {
            winSide = 1;
          }
          if( troutStates[line[0]] == 2) {
            winSide = 2;
          }
      }
    }
  });
  return winSide;
}

実行

rebar3 shell

02_game_interface.png

自分で作ってて思うんですけど、Web屋さんってすごいですね！

とりあえずダミー関数で画像が変わるところまで確認。

CPU側の思考を作る

いよいよミニマックスを組んでゆく。まずはサーバ側にエンドポイントを追加する。

start(_StartType, _StartArgs) ->
  Dispatch = cowboy_router:compile([
    {'_', [
      {
        "/", 
        cowboy_static, 
        {
          priv_file, 
          tictactoe, 
          "index.html"
        }
      },
      % snip
      % CPU思考のエンドポイント
      {
        "/cpu_think",
        cpu_think_h,
        []
      }
    ]}]),
    {ok, _} = cowboy:start_clear(http, [{port, 80}],
      #{
        env => #{dispatch => Dispatch}
      }),
    tictactoe_sup:start_link().

思考はcpu_think_h.erlに実装してゆく。まずは思考呼び出し部分。POSTで受け取る。

allowed_methods(Req, State) ->
  ?OUTPUT_DEBUG("allowed_methods/2"),
  {
    [
      <<"POST">>
    ],
    Req,
    State 
  }.

content_types_accepted(Req, State) ->
  ?OUTPUT_DEBUG("content_types_accepted/2"),
  {
    [
      {{<<"application">>, <<"json">>, '*'}, think_logic}
    ],
    Req,
   State 
  }.

content_types_provided(Req, State) ->
  ?OUTPUT_DEBUG("content_types_provided/2"),
  {
    [
      {{<<"application">>, <<"json">>, '*'}, think_logic}
    ],
    Req,
   State 
  }.

think_logic(Req, State) ->
  ?OUTPUT_DEBUG("think_logic/2"),
  Response = case cowboy_req:method(Req) of
    <<"POST">> -> 
      post_think_logic(Req, State);
    Method -> 
      ?OUTPUT_ERROR(
        "think_logic unknown method: ~w",
        [Method]),
      Resp2 = cowboy_req:reply(
        500,
        jsone:encode(<<"\"error_reason\": \"unknown method\"">>)),
      {true, Resp2, State}
  end,
  ?OUTPUT_DEBUG(
      "think_logic - response: ~w",
      [Response]),
  Response.

post_think_logic(Req, State) ->
  ?OUTPUT_DEBUG("post_think_logic/2"),
  GameState = generate_game_state(Req),
  ?OUTPUT_DEBUG("post_think_logic/2 - game state: ~w", [GameState]),
  MainPlayer = generate_main_player(),
  {Move, _} = best_move(GameState, MainPlayer),
  {X, Y, Succeed} = case Move of
      null ->
          {0, 0, false};
      SucceedMove ->
          {MoveX, MoveY} = SucceedMove,
          {MoveX, MoveY, true}
  end,
  ResultJson = #{
      <<"succeed">> => Succeed,
      <<"x">> => X,
      <<"y">> => Y
  },
  ?OUTPUT_DEBUG("post_think_logic/2 - think result: ~w", [ResultJson]),
  Resp = cowboy_req:set_resp_body(
    jsone:encode(ResultJson),
    Req
  ),
  Resp2 = cowboy_req:reply(
    200,
    Resp),
  {true, Resp2, State}.

ミニマックス本体。今回は負けが-99, 勝ちが99。空きマスが多いほど良い手として判断するようにした。全体はgithubを参照。

best_move(State, MainPlayer) ->
    PlyDepth = ?MAX_PLYDEPTH,
    minimax(State, PlyDepth, MainPlayer, null, null).

% minimax(GameState, PlyDepth, MainPlayer) -> {Move, Score}.
-spec minimax(list(), integer(), map(), map(), integer()) -> {map(), integer()}.
minimax(GameState, PlyDepth, MainPlayer, Move, _)  ->
    case is_leaf_scene(GameState, PlyDepth) of
        true ->
            NewScore = evaluate_score(GameState, MainPlayer),
            {Move, NewScore};
        false ->
            EmptyPositions = get_null_positions(GameState),
            minimax(
                GameState, 
                PlyDepth, 
                MainPlayer, 
                EmptyPositions , 
                null, 
                get_side_min_score(MainPlayer#player_record.side))
    end.

-spec minimax(list(), integer(), map(), list(), map(), integer()) -> {map(), integer()}.
minimax(_, _, _, [], Move, Score) -> 
    {Move, Score};
minimax(GameState, PlyDepth, MainPlayer, EmptyPositions, Move, Score) ->
    [EmptyPosition | EmptyPositionRetain] = EmptyPositions,
    GameStateAfterPlayer = set_game_state(GameState, MainPlayer, EmptyPosition),
    {_, OpponentScore} = minimax(
        GameStateAfterPlayer, 
        PlyDepth - 1, 
        get_opponent_player(MainPlayer), 
        Move, 
        Score),
    NeedExchangeMove = need_exchange_move(
        get_opponent_player(MainPlayer),
        Move, 
        Score, 
        OpponentScore),
    {NewMove, NewScore} = case NeedExchangeMove of
        true -> 
            {EmptyPosition, OpponentScore};
        _ -> {Move, Score}
    end,
    minimax(GameState, PlyDepth, MainPlayer, EmptyPositionRetain, NewMove, NewScore).

-spec evaluate_score(list(), map()) -> integer().
evaluate_score(GameState, Player) -> 
    Side = Player#player_record.side,
    % many empty state is short circuit
    case is_win_game(GameState, Side) of
        win -> ?WIN_SCORE + length(get_null_positions(GameState));
        lose -> ?LOSE_SCORE - length(get_null_positions(GameState));
        _ -> calculate_draw_score(GameState, Side)
    end. 

-spec is_win_game(list(), main | opponent) -> win | lose | draw.
is_win_game(GameState, PlayerSide) ->
    Positions = get_lines(),
    PlayerWinState = is_win_game(GameState, PlayerSide, Positions),
    OpponentWinState = is_win_game(GameState, get_opponent(PlayerSide), Positions),
    case {PlayerWinState, OpponentWinState} of
        {win, win} -> draw;
        {win, _} -> win;
        {_, win} -> lose;
        _ -> draw
    end.

-spec is_win_game(list(), main | opponent, list()) -> win | no_win.
is_win_game(_, _, []) -> draw;
is_win_game(GameState, PlayerSide, Positions) when is_list(Positions) ->
    [Position|Retain] = Positions,
    PlayerWinGameResult = is_player_win_game(GameState, PlayerSide, Position),
    case PlayerWinGameResult of
        win -> win;
        _ -> is_win_game(GameState, PlayerSide, Retain)
    end.

-spec is_player_win_game(list(), main | opponent, list()) -> win | not_win.
is_player_win_game(GameState, PlayerSide, Position)  ->
    PositionState = get_position_state(GameState, Position),
    PlayerCount = count_player_side(PositionState, PlayerSide),
    OpponentCount = count_player_side(PositionState, get_opponent(PlayerSide)),
    case {PlayerCount, OpponentCount} of
        % もう勝ってる
        {3, 0} -> win;
        % 分からん
        _ -> not_win
    end.

とりあえずcurlで叩いて結果を見る

curl -X POST -d '{"troutes": [1,1,2,0,0,2,1,0,0]}' -H 'Content-Type: application/json' -H 'Accept: application/json' http://localhost/cpu_think

対決する

10番勝負する

no result
1 俺の勝ち
2 俺の勝ち
3 俺の勝ち
4 俺の勝ち
5 俺の勝ち
6 俺の勝ち
7 俺の勝ち
8 俺の勝ち
9 俺の負け
10 俺の勝ち

03_result.png

人間なめんな！

終わりに

アルゴリズムを組むのも楽しいけど、実際にそれを活かせる所まで持っていくのは大変だなと思った。

04_cpu_serifu.png

CPU弱いけど、打つときは強気にした。

0
0
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
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?