Code War

Thanks to Windward Reporting for sponsoring and CU's Computer Science Depatment for hosting the 2011 Code War.

My team, Team 42, composed of Luke Jeter, Trystan Brinkley-Jones, and me) divided the problem into simpler components:
- Take the cards given to our robot and create a large number of randomly-shuffeled sets of them.
- Score each set, keeping track of the set with the best score
- Play the set with the best score

Factors in scoring:

• Does the move get the flag (does doing so also result in death)?
• Does the move result in death?
• Does the move result in damage?
• Does the move get the robot closer to the flag?

The approach is limited by the number of sets that the AI can process in the allocated time.  If time were not a factor, every card combination could be attempted.  The random nature of the cards, however, is preferable to attempting to build a "good" set of turns because it handles possiblities that the human player ignores.  Moreover, our framework includes the ability to plug in strategies (e.g., use 4 moves and 1 rotate if possible).  Our final product did not use any custom strategies because we found that they didn't, in general, improve our solutions over the random ones.

The "Java" (it was J#) code for my team's AI is:

package PlayerJSharpAI;
import RoboRallyAPI.*;
import java.io.File;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.util.*;

//import javax.smartcardio.Card;
/**
 * The sample J# AI. Start with this project but write your own code as this is a very simplistic implementation of the AI.
 *
 * Notes about using this in RoboRally:
 * 1. Best practice here is do import for java.* and explicitly specify any System.* classes
 * 2. You can set breakpoints here when running RoboRally by opening this file in VS 2010 and setting them - but the source must be freshly compiled.
 * 3. A property like player.Damage in C# becomes player.get_Damage() and player.setDamage().
 */
public class Team42 implements IPlayer
{
 private Random rand = new Random();
 /**
  * The name of the player.
  */
 public String get_Name()
 {
  return "Team 42";
 }
 /**
  * The avatar of the player. Must be 32 x 32.
  */
 public System.Drawing.Image get_Avatar()
 {
  return null;
 }
 /**
  * Called when your robot must be placed on the board. This is called at the start of the game and each time your robot dies.
  * @param map The game map. There will be no units on this map.
  * @param you Your player object.
  * @param robotStart The position(s) on the map where you can place your robot. This will be a single point unless another robot is on your archive point.
  * @return Where to place your unit (location and direction.
  */
 public PlayerSetup Setup(GameMap map, Player you, System.Drawing.Point[] robotStart)
 {
  return new PlayerSetup(robotStart[0], MapSquare.DIRECTION.NORTH);
 }

 private class Timer {
  private long start = 0;
  private long maxThreshold = 900;
  public Timer() {
   //start = Calendar.getInstance().getTimeInMillis();
  }

  public boolean areWeShortOnTime() {

   /*
   long now = Calendar.getInstance().getTimeInMillis();
   if(now - start > maxThreshold) {
    return true;
   }
   return false;
   */

   return false;
  }


 }

 private ArrayList bestFoundSolution = null;

 /*private class CardHolder {
  public Card card;
  public int frequency = 1;

  public CardHolder(Card card) {
   this.card = card;
  }

  public boolean equals(Object o) {
   CardHolder other = (CardHolder) o;

   return new Integer(card.get_Move()).equals(other.card.get_Move());
  }
 }

 private ArrayList distinctCards(ArrayList allCards) {
  HashMap distinctCards = new HashMap();

  for(int i = 0; i < allCards.size(); i++) {
   CardHolder thisCard = new CardHolder(allCards[i]);
   CardHolder existingCard = distinctCards.get(thisCard);

   if(existingCard == null) {
    distinctCards.put(thisCard, new Integer(0));
   }
   else {
    existingCard.frequency++;
   }
  }

  return new ArrayList(distinctCards.keySet());
 }*/

 private boolean isMove(Card card) {
  if(((int) card.get_Move()) <= 3) {
   return true;
  }
  return false;
 }

 private class CardsPair {
  public ArrayList moves = new ArrayList();
  public ArrayList rotates = new ArrayList();

  public CardsPair(ArrayList cards) {

   for(int i = 0; i < cards.size(); i++) {
    Card card = (Card) cards.get(i);
    if(isMove(card)) {
     moves.add(card);
    }
    else {
     rotates.add(card);
    }
   }

  }
 }

 class RandomSorter implements Comparator {
  Random random = new Random();
  public int compare(Object o1, Object o2) {
   if(random.nextDouble() < 0.5) {
    return -1;
   }
   return 1;
  }
 }

 private ArrayList generateMovesAndRotations(CardsPair pair, int moves, int rotations) {

  if(pair.moves.size() < 4 || pair.rotates.size() < 1) {
   return new ArrayList();
  }

  //ArrayList solutions = new ArrayList();
  //for(int i = 0; i < 10; i++) {

  ArrayList moveCards = chooseX(moves, new ArrayList(pair.moves));
  ArrayList rotateCards = chooseX(rotations, new ArrayList(pair.rotates));

  if(moveCards == null || rotateCards == null) {
   return null;
  }
  moveCards.addAll(rotateCards);

  //Collections.sort(moveCards, new RandomSorter());
  return moveCards;
   //solutions.add(moves);
  //}

  //return solutions;
 }


 private ArrayList chooseX(int x, ArrayList list) {
  ArrayList aSolution = new ArrayList();
  for(int i = 0; i < x; i++) {
   int cardIndex = choseCard(list);
   if(cardIndex < 0) {
    return null;
   }

   Card aCard = (Card) list.get(cardIndex);
   aSolution.add(aCard);
   list.remove(cardIndex);
  }

  return aSolution;
 }


 private ArrayList preprocess(ArrayList cards, int numLockedInCards, int maxSets) {

  if(cards == null) {
   return new ArrayList();
  }

  boolean first = false;
  ArrayList cardSets = new ArrayList();
  for(int j = 0; j < maxSets; j++) {
   ArrayList possibleCards = new ArrayList(cards);
   ArrayList chosenCards = new ArrayList();
   for(int i = 0; i < 5 - numLockedInCards; i++) {
    int chosenIndex = choseCard(possibleCards);
    Card card = (Card) possibleCards.get(chosenIndex);
    chosenCards.add(card);
    possibleCards.remove(chosenIndex);
   }

   cardSets.add(chosenCards);
   if(first) {
    first = false;
    bestFoundSolution = chosenCards;
   }
  }

  return cardSets;
 }

 private int bestPossibleScore = 0;
 private int bestAchievedSolution = 1000;
 private ArrayList bestCards = null;

 private int laserDamage(Utilities.MovePoint mp) {
  //BoardLocation point = new BoardLocation(mp, MapSquare.DIRECTION.NORTH);
  //return Utilities.CalcLaserDamage(map, mp.get_Location());
  return mp.get_Damage();
 }

 private int distanceToFlag(Utilities.MovePoint mp) {
  return Math.abs(currentFlag.get_X() - mp.get_Location().get_MapPosition().get_X())
  + Math.abs(currentFlag.get_Y() - mp.get_Location().get_MapPosition().get_Y());
 }

 public static final int gotFlagAndDied = -1;
 public static final int getFlagAndLived = 1;
 public static final int noFlag = 0;

 private class ScoreHolder {
  public int flagScore = noFlag;
  public int conveyerScore = 0;
 }

 private ScoreHolder getFlagScore(Utilities.MovePoint[] pointsOnPath) {

  ScoreHolder scoreHolder = new ScoreHolder();

  for(int i = 0; i < pointsOnPath.length; i++) {
   Utilities.MovePoint thisPoint = pointsOnPath[i];
   if(distanceToFlag(thisPoint) == 0) {
 
    if(pointsOnPath[pointsOnPath.length - 1].get_Dead()) {
     scoreHolder.flagScore = gotFlagAndDied;
    }
 
    scoreHolder.flagScore = getFlagAndLived;
   }

   if(map.GetSquare(thisPoint.get_Location().get_MapPosition()).get_Conveyor() != null) {
    if(scoreHolder.conveyerScore == 0) {
     scoreHolder.conveyerScore = 500000;
    }
   }

  }

  return scoreHolder;
 }


 private int healthScore(Utilities.MovePoint thisPoint) {
  Object o = map.GetSquare(thisPoint.get_Location().get_MapPosition()).get_Type();
  return 0;

 }

 private int valueOfSolution(ArrayList cards) {

  //Utilities.cardDestination(you.)
  Utilities.MovePoint[] pointsOnPath = Utilities.CardPath(map, you.get_Robot().get_Location(), toArray(cards));
  Utilities.MovePoint mp = pointsOnPath[pointsOnPath.length - 1];
   //Utilities.CardDestination(map, you.get_Robot().get_Location(), toArray(cards));

  int diff = Math.abs(currentFlag.get_X() - mp.get_Location().get_MapPosition().get_X())
  + Math.abs(currentFlag.get_Y() - mp.get_Location().get_MapPosition().get_Y());
  int laserDamage = this.laserDamage(mp);
  int diffScore = 100 * diff;
  int damageScore = 10000 * laserDamage;
  int flagScore = 0;
  int deadScore = 0;
  int healthScore = healthScore(mp);

  if(mp.get_Dead()) {
   deadScore = 1000000;
  }
  boolean dieToGetFlag = true;
  ScoreHolder pathScoreHolder = getFlagScore(pointsOnPath);
  switch (pathScoreHolder.flagScore) {
   case getFlagAndLived : flagScore = 1000000; break;
   case gotFlagAndDied : flagScore = (dieToGetFlag ? 10000000 : 0); break;
   case noFlag : flagScore = 0; break;
   default : flagScore = 0; break;
  }

  int value = diffScore + damageScore + pathScoreHolder.conveyerScore + deadScore - flagScore - healthScore;
  return value;

  //return 999999;
 }

 private void processSolutions(ArrayList setOfSolutions, ArrayList lockedInCards) {
  int solutionsToCheck = setOfSolutions.size();
  for(Iterator i = setOfSolutions.iterator(); i.hasNext(); ) {
   try {
    ArrayList solution = (ArrayList) i.next();
    solution.addAll(lockedInCards);
    int score = this.valueOfSolution(solution);
    if(score < bestAchievedSolution) {
     bestAchievedSolution = score;
     bestCards = solution;
     if(bestAchievedSolution <= bestPossibleScore) {
      return;
     }
    }
    else {
     int y = 121221;
    }
   }
   catch(Exception e) {
    e.printStackTrace();
   }
  }
 }

 private int choseCard(ArrayList cards) {
  if(cards == null || cards.size() == 0) {
   return -1;
  }

  int cardSize = cards.size();

  double randNumBetween1and0 = new Random().nextDouble();

  double x = randNumBetween1and0 * cards.size();
  long rounded = Math.round(x);

  int index = new Double(rounded).intValue() % cards.size();
  if(index >= cardSize) {
   return cardSize - 1;
  }
  return index;
 }

 private ArrayList choose5of9(ArrayList setOfCards, ArrayList lockedInCards) {
  processSolutions(setOfCards, lockedInCards);
  return bestCards;
 }

 private Card[] toArray(ArrayList list) {
  int size = list.size();
  Card[] cards = new Card[size];
  for(int i = 0; i < list.size() ; i++) {
   cards[i] = (Card) list.get(i);
  }

  return cards;
 }

 private ArrayList toArrayList(Card[] cards) {
  ArrayList x = new ArrayList();
  for(int i = 0; i < cards.length; i++) {
   x.add(cards[i]);
  }

  return x;
 }

 private GameMap map;
 private Player you;
 private System.Drawing.Point currentFlag;


 /*
 private ArrayList buildMoveLast(int numLockedCards, CardsPair thisPair) {
  for(int i = 5 - numLockedCards; i >= 1; i--) {
   choseCard(cards)
  }
 }
 */


 private ArrayList generatePreprocessedSolutions(int numLockedCards, CardsPair thisPair) {
  ArrayList possibleSolutions = new ArrayList();

  ArrayList allCards = new ArrayList();
  allCards.addAll(thisPair.moves);
  allCards.addAll(thisPair.rotates);

  if(true) {
   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 10000));
   return possibleSolutions;
  }

  if(numLockedCards == 0) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 10; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 4, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 10; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 3, 2), numLockedCards, 50));
   }
   for(int i = 0; i < 10; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 3), numLockedCards, 50));
   }
  }
  else if (numLockedCards == 1) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 3, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 2), numLockedCards, 50));
   }


  }
  else if (numLockedCards == 2) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 1, 2), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 3, 0), numLockedCards, 50));
   }

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 0, 3), numLockedCards, 50));
   }



  }
  else if (numLockedCards == 3) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 1, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 0), numLockedCards, 50));
   }

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 0, 2), numLockedCards, 50));
   }






  }
  else if (numLockedCards == 4) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 1, 0), numLockedCards, 50));
   }

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 0, 1), numLockedCards, 50));
   }







  }

  return possibleSolutions;
 }

 private void printOutput(Card[] cards, Card[] lockedInCards, ArrayList chosenMoves) {
  try {
   OutputStream outputStream = new FileOutputStream(new File("c:\\output\\output.txt"));
   write(outputStream, "Dealt cards:\n");
   for(int i = 0; i < cards.length; i++) {
    write(outputStream, cards[i].ToString());
    write(outputStream, "\n");
   }
   write(outputStream, "Locked in cards:\n");
   for(int i = 0; i < lockedInCards.length; i++) {
    write(outputStream, cards[i].ToString());
    write(outputStream, "\n");
   }

   write(outputStream, "Chosen cards:\n");
   for(int i = 0; i < chosenMoves.size(); i++) {
    write(outputStream, chosenMoves.get(i).ToString());
    write(outputStream, "\n");
   }

   outputStream.close();
  } catch(Exception e) {
   e.printStackTrace();
  }

 }

 private void write(OutputStream outputStream, String x) throws Exception {
  outputStream.write(x.getBytes());
 }

 private ArrayList getLockedInCards(int numLockedInCards, Card[] cards) {
  ArrayList lockedInCards = new ArrayList();
  for (int ind = 5 - you.get_NumLockedCards(); ind < 5; ind++) {
   lockedInCards.add(cards[ind]);
  }

  return lockedInCards;
 }
 /**
  * Called each time the system needs another turn. If you do not return a valid turn, the game will randomly move one of your units.
  * This call must return in under 1 second. If it has not returned in 1 second the call will be aborted and a random move will be assigned.
  * @param map The game map with all units on it.
  * @param you Your player object. This is created for each call.
  * @param allPlayers All players including you. This is created for each call.
  * @param priorityNumbers The priority numbers that will be assigned to the cards you return. This order is fixed.
  * @return Your requested turn.
  */
 public PlayerTurn Turn(GameMap map, Player you, Player[] allPlayers, Card[] cards)
 {
  this.map = map;
  this.you = you;

  bestAchievedSolution = 1000000;
  bestCards = null;

  //Timer timer = new Timer();
  // if hurt bad, consider power down
  boolean powerDown = false;
  if ((you.get_Damage() > 5) && (rand.nextInt(3) == 0))
   powerDown = true;
  // get 40 sets, pick the one that's closest to the flag
  Card[] best = null;
  int bestDiff = Integer.MAX_VALUE;
  int okDiff = rand.nextInt(3);
  Player.FlagState fs = null;
  for (int ind = 0; ind < you.get_FlagStates().length; ind++)
   if (!you.get_FlagStates()[ind].get_Touched())
   {
    fs = you.get_FlagStates()[ind];
    break;
   }
  System.Drawing.Point ptFlag = fs == null ? new System.Drawing.Point(5, 6) : fs.get_Position();
  currentFlag = fs.get_Position();
  for (int turnOn = 0; turnOn < 1; turnOn++)
  {
   // pick 5 (or fewer if locked) random cards
   Card[] moveCards = new Card[5];
   //boolean[] cardUsed = new boolean[cards.length];

   int numLockedCards = you.get_NumLockedCards();
   ArrayList myCards = toArrayList(cards);
   CardsPair thisPair = new CardsPair(myCards);


   //possibleSolutions.addAll(preprocess(myCards, numLockedCards, 500));

   ArrayList possibleSolutions = generatePreprocessedSolutions(numLockedCards, thisPair);
   ArrayList chosenCards = choose5of9(possibleSolutions, getLockedInCards(numLockedCards, you.get_Cards()));
   //printOutput(cards, you.get_Cards(), chosenCards);

   /*
   for (int ind = 0; ind < 5 - you.get_NumLockedCards(); ind++)
    while (true)
    {
     int index = ind; // rand.nextInt(cards.length);
     if (cardUsed[index])
      continue;
     moveCards[ind] = cards[index];
     cardUsed[index] = true;
     break;
    }
    */
   // add in the locked cards
   /*
   for (int ind = 5 - you.get_NumLockedCards(); ind < 5; ind++)
    moveCards[ind] = you.get_Cards()[ind];
   */

   return new PlayerTurn(toArray(chosenCards), false);
   /*

   Utilities.MovePoint mp = Utilities.CardDestination(map, you.get_Robot().get_Location(), moveCards);
   if (!mp.get_Dead())
   {
    int diff = Math.abs(ptFlag.get_X() - mp.get_Location().get_MapPosition().get_X()) + Math.abs(ptFlag.get_Y() - mp.get_Location().get_MapPosition().get_Y());
    if (diff <= okDiff)
     return new PlayerTurn(moveCards, powerDown);
    if (diff < bestDiff)
    {
     bestDiff = diff;
     best = moveCards;
    }
   }
   */
  }
  return new PlayerTurn(best, powerDown);
 }
}