Homework 3

Table of Contents

Task (100 pts)

  • Code the minimax algorithm, as applied to tic-tac-toe. Allow a human to play against the computer. Modify it so it prefers moves that win sooner. For example, the best move when ‘x’ is at (0,0) and (1,0) and ‘o’ is at (0,1) and (0,2) should be ‘x’ at (2,0) to make the win. (Positions are written in (x,y) format, with (0,0) at the top-left.)

Extra credit (40 pts)

  • Code the alpha-beta pruning algorithm (instead of the minimax algorithm) for the same task described above. This extra credit gives you +20 pts and the 100 pts for the task.
  • Now that you have some experience with search, as a general AI technique, can you think of some problems (2-3 problems) for which it is difficult if not impossible to solve with search? Hint: Think about problems in which it is difficult/impossible to describe the initial state, and/or possible actions, and/or transition model, and/or goal criteria, etc.
CSE 630 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.