Homework 4: Adversarial Games

Instructions

In this assignment, you will explore a game from the perspective of adversarial search. A skeleton file homework4.py containing empty definitions for each question has been provided. As before, since portions of this assignment will be graded automatically, none of the names or function signatures in this file should be modified. However, you are free to introduce additional variables or functions if needed. You may import definitions from any standard Python library, and are encouraged to do so in case you find yourself reinventing the wheel. If you are unsure where to start, consider taking a look at the data structures and functions defined in the collections, itertools, Queue, and random modules. You will find that in addition to a problem specification, most programming questions also include a pair of examples from the Python interpreter. These are meant to illustrate typical use cases, and should not be taken as comprehensive test suites. Once you have completed the assignment, you should submit your file on Gradescope. You may submit as many times as you would like before the deadline, but only the last submission will be saved.

Style [5 points]

Your code should follow the proper Python style guidelines set forth in PEP 8, which was written in part by the creator of Python. Our autograders will automatically scan your submission for style errors using the pycodestyle library on default settings. If your submission contains any style errors, the autograder will show you some of them and you will not receive these 5 points. You can use pycodestyle or any other tool you like to make sure that your submission conforms to PEP 8 guidelines.

Dominoes Game

In this section, you will develop an AI for a game in which two players take turns placing $1 \times 2$ dominoes on a rectangular grid. One player must always place his dominoes vertically, and the other must always place his dominoes horizontally. The last player who successfully places a domino on the board wins. As with the Tile Puzzle, an infrastructure that is compatible with the provided GUI has been suggested. However, only the search method will be tested, so you are free to choose a different approach if you find it more convenient to do so. The representation used for this puzzle is a two-dimensional list of Boolean values, where True corresponds to a filled square and False corresponds to an empty square.

1. In the DominoesGame class, write an initialization method __init__(self, board) that stores an input board of the form described above for future use. You additionally may wish to store the dimensions of the board as separate internal variables, though this is not required.
2. Suggested infrastructure. In the DominoesGame class, write a method get_board(self) that returns the internal representation of the board stored during initialization.

>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[False, False], [False, False]]
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[True, False], [True, False]]

Write a top-level function create_dominoes_game(rows, cols) that returns a new DominoesGame of the specified dimensions with all squares initialized to the empty state.

>>> g = create_dominoes_game(2, 2)
>>> g.get_board()
[[False, False], [False, False]]
>>> g = create_dominoes_game(2, 3)
>>> g.get_board()
[[False, False, False],
[False, False, False]]

In the DominoesGame class, write a method reset(self) which resets all of the internal board's squares to the empty state.

>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[False, False], [False, False]]
>>> g.reset()
>>> g.get_board()
[[False, False], [False, False]]
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.get_board()
[[True, False], [True, False]]
3 / 6
>>> g.reset()
>>> g.get_board()
[[False, False], [False, False]]

In the DominoesGame class, write a method is_legal_move(self, row, col, vertical) that returns a Boolean value indicating whether the given move can be played on the current board. A legal move must place a domino fully within bounds, and may not cover squares which have already been filled. If the vertical parameter is True, then the current player intends to place a domino on squares (row, col) and (row + 1, col). If the vertical parameter is False, then the current player intends to place a domino on squares (row, col) and (row, col + 1). This convention will be followed throughout the rest of the section.

>>> b = [[False, False], [False, False]]
>>> g = DominoesGame(b)
>>> g.is_legal_move(0, 0, True)
True
>>> g.is_legal_move(0, 0, False)
True
>>> b = [[True, False], [True, False]]
>>> g = DominoesGame(b)
>>> g.is_legal_move(0, 0, False)
False
>>> g.is_legal_move(0, 1, True)
True
>>> g.is_legal_move(1, 1, True)
False

...

Feedback

1. Approximately how long did you spend on this assignment?
2. Which aspects of this assignment did you find most challenging? Were there any significant stumbling blocks?
3. Which aspects of this assignment did you like? Is there anything you would have changed?