Review

This part of this lab is a review of the Minimax and Alpha-Beta Pruning. It aims to refresh your memory of what you have learned in class.

• Minimax and Alpha-Beta Pruning
• Minimax in general
• Steps of the Minimax algorithm
• Disadvantages of Minimax
• Alpha-beta pruning
• Alpha-beta pruning with depth

Please download the notebook by right-clicking and selecting "Save link as" and opening it using Google Colab. You should see the following if you open the notebook successfully.

Introduction

Board games are great testbeds to evaluate AI agents due to the simple representations, clear rules, huge search space, and simulation of the 'real world'. You must have heard of Deep Blue and AlphaGo, which defeated top human players in chess and Go, respectively. Deep Blue also used the alpha-beta pruning based method, while AlphaGo used Monte Carlo tree search and deep learning.

In this lab, we will implement a generalized tic-tac-toe (varying board size and number to connect) using minimax and alpha-beta pruning.

Lab Work

Several lab tasks are given to you to practice your skills in implementing the Minimax algorithm and its variants for a generalized tic-tac-toe. Please download the notebook and .py submission template, then open them on Google Colab. You should see the following if you open the notebook successfully.

Submission & Grading

• Deadline: Wednesday, 12 May 2022, 23:59
• You may earn 2 points for each lab via Automated Grading on the ZINC Online Submission System
• Please check here for a usage overview of ZINC
• Zip lab9_tasks.py (the name should be the same, including its case), and submit the zip file (i.e. lab9_tasks.zip) to ZINC
• You may submit your file multiple times, but only the latest version will be graded
• Lab work submitted via channels other than ZINC will NOT be accepted. Late submission will NOT be accepted as well

Frequently Asked Questions

• Q: Is it normal that minimax/alpha-beta pruning chooses not to win immediately?
  A: Yes, if the AI knows it will win eventually, it may not choose the fastest move to win because minimax/alpha-beta pruning is not designed to do so. Therefore, we ask you to implement alpha-beta pruning with depth, which shall choose the fastest move to win.
  

• Q: Is it normal that minimax is really slow for board_size=4, connect=3?
  A: Yes, it's normal. Minimax is actually only suitable for 3x3. For 4x4, connect=3, you're supposed to use alpha-beta pruning, although it is also slow at the first few steps. For 4x4, connect=4, and 5x5 cases, even alpha-beta pruning is quite slow if using the interactive UI. Thus, it's better to separately input a board state and check if the returned position is correct.
  

• Q: Can you give some hints on alpha-beta pruning with depth?
  A: Please refer to this post: https://piazza.com/class/l0dnfumksfu529?cid=346_f4