From 6.034 Wiki

(Difference between revisions)

Revision as of 10:44, 25 September 2015

Games and Adversarial search

This lab has two parts. In the first part of this lab, you'll work with the game Connect Four, writing methods to represent states of a ConnectFour game as a game tree.

In the second part of this lab, you'll write subroutines for performing search functions on a game tree: depth-first search, ordinary minimax search, minimax search with alpha-beta pruning, and finally progressive deepening.

[in progress]

todo: make sure below is consistent with docstrings from lab3.py

more todo notes... (commented out, edit to view)

Part 1 : Representing Connect Four as a game tree

How to play Connect Four

Connect Four is a two-player game where players take turns dropping a piece into a 6x7 grid. The first player to build a consecutive sequence of four pieces wins. The sequence of four pieces can lie either horizontally, vertically, or diagonally. In this way, Connect Four is similar to other games you might know such as tic-tac-toe/noughts and crosses.

From an abstract perspective, each player has seven alternative moves in a turn, corresponding to the seven columns where the player can drop the piece (unless the column is full, in which case the player cannot move there.)

Utility functions for playing Connect Four

For the first part of this lab, we have provided an API for constructing and manipulating Connect Four boards (see ConnectFourBoard below). Your task is to define subroutines for generating a player's set of possible moves, for determining whether the game is over, and for determining whether any player has won. These subroutines will provide the necessary definitions for treating Connect Four boards as states in a game tree, which will be useful in the second half of this lab.

Return True if the game is over, otherwise False.

def is_endgame_connectfour(board) :
   returns True if board contains chain of length 4, or all columns are full

Return 1 or 2 if one of the players has won, otherwise None. Assume that the board is legal, so at most one player has won.

def winner_connectfour(board) :

Return a list of boards representing the legal game states you can end up in by making a move in the given position.

At most, you can move in any of the 7 columns. But you cannot legally move in a column if it's full. And you should check in advance if the game is already over and return the empty list if so.

For each board in the list, board.prev_move_string() notes which column you moved in (for debugging purposes).

Note: iterate over columns in increasing numerical order

def next_boards_connectfour(board) :

Here, we'll define the utility/score of a connect four game that has been won. We'll return a score of 1000 (arbitrarily chosen) if player 1 has won, and a score of -1000 if player 2 has won.

def endgame_score_connectfour(board) :

However, the above score function doesn't reward players for winning sooner, since all winning states have the same value. Instead, write a score function that rewards players for winning sooner. (Hint: you can use board.count_pieces())

make sure you return a value with abs(val) >= 1000 to indicate that someone has won

def endgame_score_connectfour_faster(board) :

To define the rules and starting state of the game ConnectFour, we can pass the functions you wrote above to the AbstractGameState constructor.

Example (which we won't use for now):

starting_state_connectfour = AbstractGameState(state = ConnectFourBoard(),
                                               who_won_fn = winner_connectfour,
                                               generate_next_states_fn = next_moves_connectfour,
                                               endgame_score_fn = endgame_score_connectfour_faster)

Part 2: Searching a game tree

Cooperative depth-first search

Now we can begin writing minimax functions for abstract game states. Note: we will now be using the AbstractGameState API.

First, we'll see what non-adversarial search looks like. Imagine both players are trying to collaboratively find the best path. Use depth-first search to find the best path. Assume both players have the same goal: finding the maximum score.

use dfs to explore all possible end-game states

Please return a tuple containing the best path (a list of Move objects), the score value of the leaf node (a number), and the number of score evaluations you performed (a number).

Although we elide over this in recitation and only return the final score, it is necessary both to keep track of and to return the entire sequence of states so that you know where the score came from, and so that you'll know which move to make to get to that score. We also ask you to keep track of the number of evaluations so that you can compare the performance of the different algorithms.

use the constant INF in lab3.py to represent infinity

def dfs_maximizing(state) :

Minimax search with endgame scores only

Find the minimax path by alternating max/min. Same return type as dfs.

def minimax_endgame_search(state, maximize=True) :

You can run your function on the test boards (todo)

A heuristic for ConnectFour boards

In practice, it is infeasible to search through the entire game tree in order to find a score. (Imagine ranking opening chess moves by whether they are automatic wins/losses for perfect play.)

Instead, define a heuristic that allows you to estimate the goodness of a state

There are many possible strategies and ways of measuring/defining the goodness of a state; you only need to define something that gives higher scores for obviously stronger positions.

hint: incorporate information about each player's chains must be abs < 1000 b/c not winning states

def connectfour_heuristic(board) :

Minimax with heuristic and endgame scores

The previous version of minimax which you wrote could only handle endgame states. Now we'll define minimax search which can search to any shallower depth, using a heuristic score instead of an endgame score for states that are not endgame states.

Define minimax search which (1) recurses if the state is not an endgame state or at the maxdepth limit (2) uses endgame score if the state is an endgame state (3) uses heuristic_fn for states at the maxdepth limit. Same return value as minimax_search.

if game is over and limit reached, use endgame score (not heuristic). maxdepth is the number of levels further you can look. ie, if maxdepth=1, you can look at all the child nodes of the current state, but no further. If maxdepth=0, you are at the maxdepth and cannot look at any child nodes.

the evaluation count should count the total number of endgame score evals and heuristic score evals. You don't need to distinguish between them for the purpose of counting evaluations.

todo: describe what is always_zero

def minimax_search(state, heuristic_fn=always_zero, maxdepth=INF, maximize=True) :

Minimax with alpha-beta optimization

Perform alphabeta pruning. Same return type as minimax_search.

def minimax_search_alphabeta(state, alpha=-INF, beta=INF, maxdepth=INF,
                            heuristic_fn=always_zero, maximize=True) :

Use progressive deepening to return anytime values

Write a progressive deepening algorithm (using minimax with alpha-beta pruning)

Anytime value api:

class AnytimeValue :

.set_value(val):
.get_value():

Code progressive deepening as you normally would, with the same return type as minimax_search. But at each level when you call alphabeta and it returns a new value, store that value using anytime_value.set_value(new_best_option).

def progressive_deepening(state, maxdepth=INF, heuristic_fn=always_zero, maximize=True, 
                         anytime_value = AnytimeValue()) :

   """Runs minimax with alpha-beta pruning. At each level, updates anytime_value
   with the tuple returned from minimax_search_alphabeta. Returns anytime_value."""

API

[in progress]

ConnectFourBoard

todo: use updated docstrings from more recent version of file

class ConnectFourBoard :

   max_height = 6
   max_width = 7 #number of columns

.get_current_player():

       """Return the current player. By convention, 1 or 2."""

.set_current_player(player):

       """Set the current player. By convention, 1 or 2."""

.get_other_player():

       """Return the other player (the one whose turn it is NOT). By convention, 1 or 2."""

.count_pieces(player=None):

       """Return the total number of pieces on the board. If player is
       supplied, returns only the number of those belonging to that player."""

.get_column_height(col_number):

       """Return the number of pieces in the column; e.g., 0 if the column is empty."""

.is_column_full(col_number):

       "Return True if column is full, False otherwise"

.add_piece(col_number, player):

       """Adds a piece belonging to the player to the given column.
       Returns new board without modifying original."""

.describe_previous_move():

       "Returns a string describing the most recent move leading to current state"

.get_all_chains(player=None):

       """Get all maximal contiguous chains of pieces. If player is provided, 
       returns only chains belonging to that player."""

AbstractGameState

todo: which methods do we want in the api?

class AbstractGameState :

.__init__(self,

                state,
                who_won_fn,
                generate_next_states_fn,
                endgame_score_fn):

.state(self):

       return self.state

.endgame_winner():

       return self.who_won_fn(self.state)

.is_game_over():

       return self.endgame_winner() is not None

.generate_next_states():

       return self.generate_next_states_fn(self.state)

.describe_previous_move():

       return self.state.describe_previous_move()

.get_endgame_score():

       # only for leaf nodes
       if not self.is_game_over():
           raise ValueError("Only endgame states have endgame score defined.")
       return self.endgame_score_fn(self.state)

.restart():

       self.state = self.starting_state

@@ Line 285: / Line 285: @@
          self.state = self.starting_state
-<!--= Problems =!-->
+<!-- from old Lab_3
+This problem set is about game search, and it will focus on the game "[http://en.wikipedia.org/wiki/Connect_Four Connect Four]".  This game has been around for a very long time, though it has been known by different names; it was most recently released commercially by Milton Bradley.
+A board is a 7x6 grid of possible positions.  The board is arranged vertically: 7 columns, 6 cells per column, as follows:
+<pre>
+1 2 3 4 5 6
+* * * * * * *
+* * * * * * *
+* * * * * * *
+* * * * * * *
+* * * * * * *
+* * * * * * *
+</pre>
+Two players take turns alternately adding tokens to the board.  Tokens can be added to any column that is not full (ie., does not already contain 6 tokens).  When a token is added, it immediately falls to the lowest unoccupied cell in the column.
+The game is won by the first player to have four tokens lined up in a row, either vertically:
+<pre>
+1 2 3 4 5 6
+
+
+       O
+       O     X
+       O     X
+       O     X
+</pre>
+horizontally:
+<pre>
+1 2 3 4 5 6
+
+
+
+
+
+X X X O O O O
+</pre>
+or along a diagonal:
+<pre>
+1 2 3 4 5 6
+
+
+             O
+O         O X
+O       O X X
+O     O X X X
+</pre>
+<pre>
+1 2 3 4 5 6
+
+
+       X
+       O X O O
+       O O X X
+X     O O X X
+</pre>
+==== Playing the game ====
+You can get a feel for how the game works by playing it against the computer. For example,  by uncommenting this line in lab3.py, you can play white, while a computer player that does minimax search to depth 4 plays black.
+<code><pre>
+run_game(basic_player, human_player)
+</pre></code>
+For each move, the program will prompt you to make a choice, by choosing what column to add a token to.
+The prompt may look like this:
+<pre>
+Player 1 (☺) puts a token in column 0
+1 2 3 4 5 6
+
+
+
+
+
+☺
+Pick a column #: --&gt;
+</pre>
+In this game, Player 1 just added a token to Column 0.  The game is prompting you, as Player 2, for the number of the column that you want to add a token to.  Say that you wanted to add a token to Column 1.  You would then type '1' and press Enter.
+The computer, meanwhile, is making the best move it can while looking ahead to depth 4 (two moves for itself and two for you).  If you read down a bit farther in the lab3.py file (or farther into this lab writeup), we'll explain how to create new players that search to arbitrary depths.
+=== The code ===
+Here's an overview of the code in the various lab files that you may need to work with.  The code contains inline documentation as well; feel free to read it.
+==== ConnectFourBoard ====
+<tt>connectfour.py</tt> contains a class entitled <tt>ConnectFourBoard</tt>.  As you might imagine, the class encapsulates the notion of a Connect Four board.
+<tt>ConnectFourBoard</tt> objects are ''immutable''.  If you haven't studied mutability, don't worry: This just means that any given ConnectFourBoard instance, including the locations of the pieces on it, will never change after it's created.  To make a move on a board, you (or, rather, the support code that we provide for you) create a new <tt>ConnectFourBoard</tt> object with your new token in its correct position.  This makes it much easier to make a search tree of boards: You can take your initial board and try several different moves from it without modifying it, before deciding what you actually want to do.  The provided <tt>minimax</tt> search takes advantage of this; see the <tt>get_all_next_moves</tt>, <tt>minimax</tt>, and <tt>minimax_find_board_value</tt> functions in <tt>basicplayer.py</tt>.
+So, to make a move on a board, you could do the following:
+<code><pre>
+>>> myBoard = ConnectFourBoard()
+>>> myBoard
+1 2 3 4 5 6
+
+
+
+
+
+
+>>> myNextBoard = myBoard.do_move(1)
+>>> myNextBoard
+1 2 3 4 5 6
+
+
+
+
+
+   X
+>>> myBoard    # Just to show that the original board hasn't changed
+1 2 3 4 5 6
+
+
+
+
+
+
+>>>
+</pre></code>
+There are quite a few methods on the ConnectFourBoard object.  You are welcome to call any of them.  However, many of them are helpers or are used by our tester or support code; we only expect you to need some of the following methods:
+-->

Lab 2: Games