courses:hcai:lab_advsearch

  • 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

  1. How does an adversarial game differ from a single-agent search problem?
  2. Should the agent exploit an opponent who often makes mistakes?
  3. Why can alpha-beta pruning examine fewer states without changing the minimax decision? Why might center-first ordering be useful in Connect Four?
  4. Does a higher evaluation score mean that the position is truly better?

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.

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.

  • 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.
  • courses/hcai/lab_advsearch.txt
  • Last modified: 2 weeks ago
  • by kkt