CSCE 782: Problem Set 3

Due: Tuesday, 19 October 2004, before class

Upload Problem Set

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:

  1. The board is 21 by 21.
  2. There is a slider for the number of players which ranges from 2 to 10.
  3. There is a slider for the number of colors which ranges from 2 to 10.
  4. The colors of the patches (board squares) are chosen randomly.
  5. There is a slider for the number of tiles given to each player which ranges from 2 to 40. Their colors are chosen randomly.
  6. There is one goal patch for each player. Both the players' and the goals' initial position are chosen randomly.
  7. 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.
  8. Players can exchange tiles, as stated in the paper. The exchange need not be 1-for-1.
  9. 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.
  10. Players are selfish so you must be careful that every action your agent takes is rational.
  11. Players can only move in the four cardinal directions.
  12. Players do not know the color of the other players' chips.
  13. 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