Lab: Adversarial Search
Before the lab
- Reading:
- AIMA: Chapter 6, Sections 6.1-6.3. Focus on game formulation, optimal decisions, minimax, alpha-beta pruning, cutoff search, and evaluation functions.
- Technical preparation:
- Open today's notebook and run all setup cells and the first code cell in Segment 1 to verify that the notebook works in your environment. The output should show an empty Tic-Tac-Toe board represented by nine dots, along with a short summary of the game state and the available legal moves.
Entry quiz
Q&A
- How does an adversarial game differ from a single-agent search problem?
- Should the agent exploit an opponent who often makes mistakes?
- Why can alpha-beta pruning examine fewer states without changing the minimax decision? Why might center-first ordering be useful in Connect Four?
- Does a higher evaluation score mean that the position is truly better?
Notebook
Notebook: HCAI_Lab_Adversarial_Search.ipynb (Work in Google Colab or download the .ipynb file to local environment)
Work in groups of 2-4. Every group member must be able to explain the results.
Challenge
Work in groups of 2-4 to build an agent for the Connect 4 arena.
Your agent receives the current board and must select a legal column for its next piece. The CodinGame version uses a 7×9 board and includes an optional STEAL action for the second player, so read the rules carefully before adapting code from the notebook.
Begin with a simple working agent that selects legal moves. Then improve it using: a hand-crafted evaluation function; depth-limited minimax; alpha-beta pruning; move ordering that prioritizes promising or tactically necessary actions.
Consider which features help the agent recognize immediate wins, opponent threats, valuable positions, and longer-term opportunities. Remember that the response-time limit prevents exhaustive exploration of the complete game tree.
Start the challenge during the lab and continue it as part of the self-study regarding classes. Selected groups may share their strategies at the next lab, and effective solutions may receive bonus points.
Learn more!
- Chess Programming Wiki: Alpha-Beta – practical refinements of alpha-beta search, including move ordering, iterative deepening, principal variations, and alternative implementations.
- Chess Programming Wiki: Horizon Effect – examples of errors caused by depth-limited search, together with techniques such as search extensions and quiescence search.
- OpenSpiel: Available Algorithms – a broader overview of game-playing algorithms implemented in OpenSpiel, including minimax, alpha-beta, and more advanced methods.