Homework 5 — a game-playing agent
UWL CS452/552 Artificial Intelligence Fall 2019
For your fifth 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 leftmost 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 after turn, Green’s stone advances along its path as it grows. The rightmost picture above shows Player Green’s position after 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 leftmost 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 after 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.
Software 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, …)
TilePosition
+ int x()
+ int y()
Tile
+ int getId()
+ int getDest(int)
+ int[] getDests()
+ void receiveTile(Tile)
Move
History
+ Tile getTile()
+ int getRotation()
AgentPosition
+ int slot()
Board
+ List
Preparing your submission. Since all of the code you create will reside in the same package, you need to submit only one directory of Java files. You should submit to Autolab a ZIP archive which expands to a single directory whose name is the same as the name of package for your code, but without the “h5.” prefix. That directory should contain all of your Java source files. So if Jane Smith were working by herself, she would declare her code to be in package h5.smith. The ZIP file she would submit would expand to directory smith, and this directory would contain Factory.java plus her other Java source files.
Documentation submission. Part of the take-home component of the final examination will be a short white paper on the implementation of AI concepts in your project. You should discuss the AI tools which you applied for your agent, and alterations to the basic techniques you made to suit this particular application. I will ask you to evaluate your choices in retrospect, discuss the properties of your approach both in theory and in your observations, and weigh alternative approaches which you believe (and justify) would improve your agent’s performance and behavior.
Additional technical details
• As in previous projects, I expect you to document your source code to identify the class- relevant techniques you use, making clear how you have translated the algorithms you have selected from idealized pseudocode in the text or other references for this particular implementation.
• The provided source code, plus JAR files of compiled code, and generated API documentation will all be available via links on Canvas. I expect to make several incremental deliveries of the provided code, so you should give some thought to arranging your build so that you can easily update package uwlcs452552.h5 entities without disrupting or erasing your progress in package h5. In particular, you might consider using the JAR files of compiled code in your project instead of the source code for your actual project build, using the source only for reference.
There will be separate JAR files for the main classes and for test code which I will use to test those classes. The test code will require several additional libraries to compile and run. You should not need to run the test code (although looking at it may be a useful source of examples), so installing the test code into your project may not be worth your time.
• Your solution may use any part of the standard Java SDK except for reflection methods — the innards of the model, and of the other agents, are strictly off-limits. This homework is not a Kobayashi Maru. And although there are electives in our curriculum about security and about low-level hackery, this class is not one of them!
✷✷✷✷✷
5
Reviews
There are no reviews yet.