Homework 5 — a game-playing agent
UWL CS452/552 Artificial Intelligence
Fall 2019
For your fih and final homework, please write an agent for competitive play in the game Tsuro:
The Game of the Path.
Tsuro is a multiplayer game in which players build paths and advance along them. Paths are
printed on tiles:
The tiles are all the same size. Notice how paths run to and from the same points on the edges of
each tile, but that different tiles connect these points in different ways. When we place a new tile
next to tiles already on the grid, the paths made by the old tiles will be extended with the new
tile.
Each player is represented by a small stone, which will always be at the edge of one of the
paths. At the beginning of the game, someone shuffles the deck of tiles, and deals three tiles to
each player. Each player’s turn consists of two steps: first placing one tile in the empty grid space
next to their stone, and then drawing a new tile from the deck (if any remain). When the player
places a tile, it extends the path they are following, and the player must immediately move their
stone to the new endpoint of the path. For example, this row of pictures shows the possible
opening moves for Player Green:
The lemost of the pictures shows Green in their starting position. Notice that the stone in on a
small white dash (the stone covers the dash, but you can see the other white dashes above and
below Green) — this is Green’s tiny initial path. Each player starts on a different little path. In
Green’s first turn, they will select one tile from their hand, place it on the empty grid space next
to the Green stone, and move their stone through the new tile along the path. The middle picture
shows the outcome of one possible way of placing a tile by Green. Turn aer turn, Green’s stone
advances along its path as it grows. The rightmost picture above shows Player Green’s position
aer three turns.
A player must always place a tile in the empty space adjacent to where their stone sits at the
end of its path. However the player may choose to place any of the tiles in their hand, and may
rotate that tile as they choose when they place it. If a newly-placed tile leads a player’s path back
to the edge of the grid, then that player is eliminated from the game! So it important to choose
tiles and their rotation carefully. When all but one player has been eliminated, the last remaining
player wins.
It is possible, especially later in the game, that a new tile placement by one player might extend
the paths of several players, not just the player who places the tile. In the position shown in the
lemost photo below, Players Green and Blue are in this situation:
When either player adds a tile to the empty corner space, both players’ paths will grow, and
each stone must move forward to the end of its path. Let us assume that Green plays first, and
makes the very wise choice of play shown in the middle picture. Then (rightmost picture) Green
advances safely, but Blue’s path leads back to the edge of the grid — and so Blue is eliminated.
When a player is eliminated, any tiles in their hand are returned to the draw pile. If the draw
pile had been empty, and other players have been waiting to draw tiles, then these players draw
from the refreshed pile in the order they had been waiting. When all players but one have been
eliminated, the survivor wins the game. If all remaining players are eliminated by the same tile,
then these players tie for the win. If more than one player is still in the game aer all tiles have
been played, then again these players tie for the win.
In our virtual version of the game, the size of the playing grid may vary from game to game. For
an n × n playing grid, there will be n2 1 separate tiles. In the physical board game (which has a
6 × 6 grid), players choose their initial positions in turn at the start of the game. In our simulation
of the game, initial positions will be assigned.
Solution elements
There are two key basic technologies which must be present in your submitted agent. The first
key technology is adversarial search. Your agent must implement some form of the Minimax
algorithm to find the best possible move in each turn. The second key technology which you must
incorporate is some constructive use of probability to account for the fact that you do not know
what cards the opponents hold.
2
In executing its search, your agent has one important asset, and one important restriction. The
asset is the knowledge of the unseen cards: when your agent is instantiated for a new game, it will
be provided the contents of the entire deck of cards. In this way it has some basis for reasoning
about what plays the other players may make, and can base the opponents’ possible moves on
the actual cards yet to appear. The restriction is time: your agent may run for no longer than
a certain number of seconds in each turn. Agents which exceed this limit will be eliminated from
the game. The techniques which you can implement to let your agent cope with this time limit
include:
1. Limiting search to a certain depth. The need to limit the depth of a Minimax search is a basic
requirement which we discussed in class. As with most games, or really any interesting
search space, an unboundedly deep search is simply not feasible.
2. Using your own timer to terminate search. The agent can set its own timer (let’s say for
one second less than its maximum). Then the agent can record the best-so-far move in a
location whose scope includes the timer control: if the agent’s timer goes off and interrupts
the search, the agent can simply return the best solution which had been found so far before
the controller’s timer expires.
Your agent will also be limited in the amount of time which it may use to initialize itself. The time
limit for both the initialization phase and for each turn will be provided to the factory method
which should return an agent instance.
Beyond the two key solution elements, there are a number of techniques which you can apply to
improve your agent’s performance. The remainder of this section presents a few ideas, but you are
free to bring any technique of artificial intelligence into your agent. The book discusses extensions
to most of the techniques we have already studied, and I am happy to help you understand this
additional material, or to track down references to other work they mention.
The feasible depth of search will be different at different phases of a Tsuro game. At the beginning
of a game the large number of possible plays by opponents translates to a very large branching
factor, and the possibility of multiple opponents translates to a deeper tree: together, these factors
mean a very expensive search for even a single round of lookahead. But later in the game, with
fewer opponents and unknown tiles, a deeper and possibly complete search will be possible.
Agents might choose a depth of search which is based on the game phase as well as the remaining
time.
One approach to shrinking the search tree in the early game is to consider only a subproblem,
in a similar manner as we studied for constructing heuristics. One can restrict consideration to
certain (or no) opponents, simplify the notion of move associated with opponents, or disregard
other aspects of gameplay to reduce the search space. You can vary your agent’s objective function
in the simplified search, or use a quick simplified search to remove branches of a subsequent full
search.
Soware architecture
Several classes over two projects comprise the Tsuro implementation. Classes which I will provide
to you will live in package uwlcs452552.h5; Figure 1 shows a UML representation of some key entities
of this package.
3
interface AgentFactory
+ Agent getAgent(...)
interface Agent
+ Move play(Board, ...)
+ void receiveTile(Tile)
Move
+ Tile getTile()
+ int getRotation()
History
Tile
+ int getId()
+ int getDest(int)
+ int[] getDests()
Board
+ List