===== 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 ==== * 08:30 -- [[https://forms.cloud.microsoft/e/buQ4nF6LNv|MS Forms]] * 10:00 -- [[https://forms.cloud.microsoft/e/C2SA9gmUHv|MS Forms]] ==== 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:** [[https://colab.research.google.com/drive/1AT2tx-PW6obzoAnIwe3ku4gOP1x0E0d5?usp=sharing|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 [[https://www.codingame.com/multiplayer/bot-programming/connect-4|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! ==== * [[https://chessprogramming.org/Alpha-Beta|Chess Programming Wiki: Alpha-Beta]] -- practical refinements of alpha-beta search, including move ordering, iterative deepening, principal variations, and alternative implementations. * [[https://chessprogramming.org/Horizon_Effect|Chess Programming Wiki: Horizon Effect]] -- examples of errors caused by depth-limited search, together with techniques such as search extensions and quiescence search. * [[https://openspiel.readthedocs.io/en/latest/algorithms.html|OpenSpiel: Available Algorithms]] -- a broader overview of game-playing algorithms implemented in OpenSpiel, including minimax, alpha-beta, and more advanced methods.