feat/cpu/greedy

[hiroto0222]

Issue: #50

目的

1. availableMoves 更新の最適化

2. CPUが置けるピース検索の最適化

3. Greedy CPU の導入

実装の概要

1. availableMoves 更新の最適化

• 毎回新しい availableMoves 配列を作成するのではなく、置いたピースの座標を元に更新を行う

2. CPUが置けるピース検索の最適化

• 現在ピースを置けるマス目 (availableMoves) に対して各ピースの角が当たる様な中心マスの配置法は以下の各赤いマス目がすべての候補である。（ピースによって中心マスを変更する必要があった）

• そのため、事前に availableMoves から全ピースの現在置ける中心マスの候補を計算し、それらに対して各ピースを置き・回転させる事で毎回ボードを全探索する必要がない。AIPlayer クラスの possibleDIRS で図の赤いマス目の座標を表し、 getCurrentAvailableMoves で計算を行っている。

3. Greedy CPU の導入

• 主に以下の記事を参考に導入しました
  • http://artemis.library.tuc.gr/DT2014-0060/DT2014-0060.pdf
  • https://github.com/mknapper1/Machine-Learning-Blokus/blob/master/Blokus%20Solver.ipynb
• Greedy CPU のアルゴリズム:
  1. 現在置ける中心マスの候補を取得し、全ピースをそれらの候補に置いていく。
  2. 置けた場合 -> 置けたピースの重みを以下の様に計算し、配列に保存する

     const weight = 1 * (currPiece.length + 1) + ((currPlayerCornerDiff - opponentCornerDiff) / opponentAvailableMoves.length) * 0.5;

  3. 全ピース（回転を含む）を試した後、置けたピースの配列内で最も重みの高いものを選択し、そのピースをボードに置く。

その他:

• minimax 重み: $ MinimaxEval_{W_2, i} = W4 \left [ size{1,i} W1 + \frac{\sum{(cor{1,my} - cor{1,opp})}}{n{opp}} W_2 \right ] W3 \left [ size{2,i} W1 + \frac{\sum{(cor{2,my} - cor{2,opp})}}{n{opp}} W_2 \right ]$