CSCE 782: Problem Set 3
Due: Tuesday, 19 October 2004, before class
The Colored Trails Game
For this problem set you will implement your own version of the
Colored Trails game as described in Section 1.2 of
along with automated selfish players that can play the game. The
implementation of the game itself should be easy. You should
devote most of your time to developing an appropiate negotiation
strategy for the selfish agents. The strategy should work well
across all parameter settings and should result in the approximate
maximization of social welfare.
Specifically, your implementation must obey the following
specifications:
- The board is 21 by 21.
- There is a slider for the number of players which ranges from 2 to 10.
- There is a slider for the number of colors which ranges from 2 to 10.
- The colors of the patches (board squares) are chosen randomly.
- There is a slider for the number of tiles given to each player which ranges from 2 to 40. Their colors are chosen randomly.
- There is one goal patch for each player. Both the players' and the goals' initial position are chosen randomly.
- Each player receives a utility of 100 for reaching the goal plus 1 unit of utility for every tile that it still has in its possession when it gets there.
- Players can exchange tiles, as stated in the paper. The exchange need not be 1-for-1.
- At each time step all players can engage in negotiation with all other players (there is no cost to communication) and then move one step.
- Players are selfish so you must be careful that every action your agent takes is rational.
- Players can only move in the four cardinal directions.
- Players do not know the color of the other players' chips.
- Once an agent reaches its goal it can no longer engage in any negotiation (that is, it keeps its tiles).
When each player gets a lot of tiles this game is easy, with very
few tiles its impossible, with just enough tiles it is only
possible with negotiation. I will be most interested in these
borderline cases.
And, finally, make sure you provide adequate documentation
of your negotiation protocol.
Submission Instructions
This problem set is to be done individually. You cannot ask or
receive help from anyone. As will all the problem sets, you will
hand them in using our department's dropbox. You will hand in only one
file, your .nlogo file. You will use the information tab of the
program for writing your detailed explanation of the techniques you
used, how the program works, how to set the controls to obtain the
different behaviors you want to show, etc. The information tab needs
to start with:
Name:
email: (I will email your grade and comments to this address)
I understand that it is the responsibility of every member of the
Carolina community to uphold an maintain the academic standards and
integrity of the University of South Carolina. Any member of the
University community, who has reasonable grounds to believe that an
infraction of the Code of Student Academic Responsibility has
occurred, has an obligation to report the alleged violation.
I certify that I have neither given nor received unauthorized aid on
this problem set.
José M. Vidal
Last modified: Sat Oct 16 13:57:16 EDT 2004