Lab 9

Topics: game tree search, exceptions

Getting started:


Part 1 (14:00)


Part 2 (14:20)


Part 3 (15:20)


Part 4 (15:30)


Tic-Tac-Toe

Sample Game:
---  x   --x   o    --x  x   -xx  o   -xx  x   xxx
--- ---> ---  --->  -o- ---> -o- ---> -oo ---> -oo  x wins
---      ---        ---      ---      ---      ---

MiniMax Search Applied to Tic-Tac-Toe

MiniMax Notes

Game Tree

MiniMax Search

Tic-Tac-Toe Game Tree 1

             ---
             ---                   [x to move]
             ---

      / / / / | \ \ \ \            9 moves; pick one with highest value
                                   in view of player to move
    x--               ---
    ---     .....     ---          [o to move]
    ---               --x
  ////\\\\          ////\\\\       8 moves in each state
 
 xo-                       o--
 ---  ...         ...      ---     [x to move]
 ---                       --x
  .        etc.             .
  .         .               .
  .         .               .
 xox        .              oxo
 oox                       xox     [o to move]
 oxx                       oxx

 x wins                    o wins

Tic-Tac-Toe Game Tree 2

What is the value of this game state in view of player x?
             xoo
             --x  [x to move]
             -o-
[ draw game tree on a piece of paper ]

Game Tree Search Mechanics

MiniMax or NegaMax (preferred) search can be implemented by depth-first-search, copying states and applying moves to the copied states as we go down the game tree until we reach a terminal state, which gets evaluated and its value passed back to the caller for maximization of the negated value (NegaMax) or minimization/maximization of the returned value depending on whose turn it is (MiniMax)

Please refer to lecture notes (especially page 27) for details and code snippets you may want to use

Tuples

In this exercise you'll use std::tuple, which is a generalization of std::pair. Tuples contain a sequence of data items that don't necessarily share the same type. Individual items can be accessed by std::get<i>(tuple)

Example:

    std::tuple<int,double,char> t(0, 3.5, 'x');
    cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
  
prints 0 3.5 x

Prep Problem

In this problem you will implement missing functions of a tic-tac-toe program that read a game state from a string, print it to stdout, and determine whether a board is completely filled

In file ttt1.cpp, which is given, implement the parts marked with

// ... implement
You may want to use this script file to compile your program: make1

Solution
Prep Solutions

Lab Exercise

Secrets