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

# はじめに

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

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

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

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

# IFを作る

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

![01_appimage.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/42445/b9e7cb38-d809-d7de-9b64-53e10470aeda.png)

<font color="dark_pink">自分で書いてて思うけど、デザイナーさんってすごいですね！</font>

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

![05_sequence.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/42445/ca0895d0-c9ab-5440-3bd3-703a0f83d2c9.png)


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

```shell
rebar3 new release tictactoe
```

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

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

```

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

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

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

```shell
rebar3 upgrade
```

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

<details><summary>apps/tictactoe/src/tictactoe_app.erl</summary><div>

```erlang
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).
```

</div></details>

Webページを配置する。

```shell
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
```

<details><summary>apps/tictactoe/priv/index.html</summary><div>

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

</div></details>

<details><summary>apps/tictactoe/priv/index.css</summary><div>

```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;
}
```

</div></details>

<details><summary>apps/tictactoe/priv/js/main.js</summary><div>


```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;
}
```

</div></details>

実行

```shell
rebar3 shell
```

![02_game_interface.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/42445/ac4fe7f3-34a7-fafd-7256-9a7b0145bc5f.png)


<font color="dark_pink">自分で作ってて思うんですけど、Web屋さんってすごいですね！</font>

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

# CPU側の思考を作る

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

```erlang
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で受け取る。

```erlang
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を参照。

```erlang
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で叩いて結果を見る

```shell
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/42445/62cd221b-f18a-5c03-34b1-43d70cbb1e0e.png)

<font color="dark_pink">人間なめんな！</font>

# 終わりに

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

![04_cpu_serifu.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/42445/6263fdad-c337-b237-0193-18e128823a40.png)

<font color="dark_pink">CPU弱いけど、打つときは強気にした。</font>