• Minimax Algorithm
  • 상태 s가 주어졌을 때
    • 최대화 플레이어(maximizing player)는 Actions(s) 가운데 Min-Value(Result(s, a))의 최댓값을 생산하는 행동 a를 선택한다.
    • 최소화 플레이어(minimizing player)는 Actions(s) 중에서 Max-Value(Result(s, a))의 최솟값을 생산하는 행동 a를 선택한다.

Things to consider

1. Considering depth in Minimax. Chess tends to be 5-6 depths at max
2. breadth-first vs depth-first vs iterative-deepening
   1. You simply search to depth 1, then 2, then 3, and so on. This seems incredibly wasteful, but since each depth takes much longer than the previous one, the overall search time is still dominated by the time spent processing the greatest depth. As an added bonus, you can use the results of the previous iterations to guide the search.
3. Edit your code to shave microseconds off the functions that check the state of the board, and that get all the valid moves.
   1. These microseconds add up to a significant amount of time when you analyse millions of positions! I remember spending a couple of evenings trying make my code as fast as it possible could be. In the end it shaved a few seconds off the runtime at depth 5.
4. Reduce the complexity of checking the state of the board → need time limit?
   1. With each engine there is a trade off between speed and accuracy. Take a look the this heuristic to analyzing the position of board: https://www.chessprogramming.org/Simplified_Evaluation_Function.
   2. Though it tends to break down in the mid/end game.