Beej's Bit Bucket
a day ago
- Chess uses a move tree that is manageable due to limited moves, allowing deep lookahead.
- In Go, the large board (19x19) causes the tree to explode, making traditional tree search impractical.
- The Monte Carlo Method runs random simulations to estimate the best move based on win rates.
- For tic-tac-toe, random simulations show the center move is most likely to win.
- In Four in a Row, the method runs 1000 random games from the current board and picks the move with the highest win percentage.
- The approach has O(1) space complexity, using only one extra board for simulations.
- A weakness is that it assumes opponents move randomly, so it may miss obvious winning moves for the opponent.
- Improvements like Monte Carlo Tree Search (MCTS) combine random simulations with tree search for better results.