What is the best method to go for the game playing problem ?

Answer: Heuristic Search

Why this is best:

• Heuristic Search uses an evaluation function to estimate the value of non-terminal positions, allowing the algorithm to make good decisions without exploring the entire game tree.

• It combines well with standard search techniques (for example, minimax + alpha-beta pruning) to prune irrelevant branches and reach deeper search depths efficiently.

• Heuristics are adaptable: you can improve play by refining the evaluation function, adding iterative deepening, transposition tables, and move ordering.

• For very large or stochastic games, heuristic ideas integrate with Monte Carlo Tree Search (MCTS) to balance exploration and exploitation.

Why not the other approaches:

• Optimal Search: Guarantees the best move only when the full search is feasible; impractical for complex games due to exponential growth of the search tree.

• Random Search: Too undirected to produce competitive play; can be used as a simple baseline or for random playouts within other algorithms but not as the main strategy.

• Stratified Search: Not a standard term in game-playing literature; partitioning ideas may help but are typically covered by selective search or sampling techniques that are themselves guided by heuristics.

Practical steps to implement a strong game-playing agent:

1. Design a good evaluation function that captures important features of positions.

2. Use minimax search with alpha-beta pruning and iterative deepening to get the best results under time limits.

3. Add optimizations: move ordering, transposition tables, and selective extensions.

4. For very large or probabilistic games, consider Monte Carlo Tree Search combined with heuristic priors.

Summary: Heuristic Search provides the right trade-off between performance and practicality for typical game-playing problems and is usually the best starting approach.