A More Involved Example: Running an automated tournament
By Kyle Garms and John Luetke
Minor edits by Craig Struble
If you haven't already, please read the short Introduction to MUGrid article.
This tutorial assumes that you:
Background
topIn January of 2010, the ACM Queue held a programming challenge in which contestants were to write an agent that competed in a game called "Capture". Given two bumpers and a sled, the agent needed to convert as many pucks to their color as possible. Each player controls 2 bumpers, which interact with pucks and other bumpers, and 1 sled, which is used to "capture" pucks, earning the player points.
Programs compete against each each other and interact with the game environment with text input and output. At specified intervals, the game environment sends information about itself to each of the players, such as the location of each puck, the color of each puck, the location of the 4 bumbers and the locations of the two sleds. Players then respond by sending information back to the game environment, which in turn will apply the new information to the game state, and repeat the process. Players send 5 pieces of information to the game: the dx and dy values for each bumper's path of motion, and the radian angle that the sled should turn at.
This example takes agents written by students in COSC 4600: Introduction to Artificial Intelligence (Spring 2010) and pits them against each other in an automated single-elimination tournament using Condor.
Designing the Tournament
topIn order to have a tournament, some prerequisites are needed, such as a list of players participating, and some determination of who will be competing against who.
First off, let's tackle the list of players. This is something that will remain static throughout the entirety of the tournament. Let's create a file that contains this information:
players.txt
java,Player1,Player1.java java,Player2,Player2.java java,Player3,Player3.java java,Player4,Player4.java java,Player5,Player5.java java,Player6,Player6.java java,Player7,Player7.java java,Player8,Player8.java
Each line above represents a different player that will be participating. Each line contains 3 pieces of information:
- the language that the player (agent) is written in
- the readable name of the player
- the source file of the player
The Capture game allows for players to be written in either C, C++, or Java. We will be using players written in Java for this tutorial. Due the the Java assumption, we will also be ignoring the language specification and the source file specification. As you will see later, we assume that player source files carry the same name as the player designated here.
Next off, we need to determine who will be playing against who in the tournament. This is typically done via seeding: each player is given a different rank based on how well they performed in some prior competition, say, the regular season. The best player is matched against the worst player, the second best against the second worst, and so on. At this point in time, we don't know how good Player1 is, and we also have no idea if Player1 is better than Player2. So it seems like we are going to have to determine this somehow. Let's do it with a Condor DAG.
Creating the Season
topWe already know how many players will be participating, so we could just pit each player against each other player once, rank them with this information, and call it a day. But that's not exciting, is it? What if during the basketball season, Marquette only played against Notre Dame one time, and Notre Dame was down for the entire game, then they make a miraculous basket which results in them winning the game by 1 point. Notre Dame would be view as the better team since their record is 1-0 and Marquette's is 0-1, even though Marquette led for the entire game. Now if Notre Dame and Marquette played 2 more times in the season, and Marquette won both, Notre Dame is now 1-2, and Marquette is 2-1. Given the additional opportunities, Marquette proved to be a better team than Notre Dame, and Marquette's ranking in the NCAA tournament should reflect this.
The total number of games in the regular season is determined by the number of players and number of games the players will play against each other. There is an advantage given to the player that goes first in the game, so for fairness, players will play the same number of games being the first or second player to move. The number of player pairs is given by the formula C(x,2) = x(x-1) / 2; that is, the number of ways 2 players can be chosen from x total players. If we let n, which must be even, represent the number of games played by a pair of players, the total number of games is n x(x-1) / 2.
So, we know that we have 8 players. Let's assume there will be 6 games between players (3 going first, 3 going second) in the regular season. This results in 168 games, since x = 8, n = 6 and 6 * 8 * 7 / 2 = 56 * 3 = 168.
Recall that a DAGman file defines each node on a separate line:
JOB <JOB NAME> <JOB FILE>
While possible, it would get extremely cumbersome to generate a unique job file for each match that we were to run between two players. We could write a script to generate a unique job file, but there is a much better approach. Using the VARS keyword, we can have one job file that simple runs a game, but pass it different parameters. Using the VARS keyword, we would adjust our DAG file like so:
JOB <JOB NAME> <JOB FILE> VARS <JOB NAME> <VAR LIST>
Given the approach of using a single job file, and just changing variables in the job, our job file will look like this:
onegame.submit [download]
Universe = vanilla Log = $(ERRF).log Output = $(ERRF).out Error = $(ERRF).error Requirements = (Arch == "INTEL" || Arch == "X86_64") && (OpSys =="LINUX") && (HasJava =?= True) should_transfer_files = YES when_to_transfer_output = ON_EXIT transfer_input_files = scripts/run_game.sh, java/capture.jar, players/$(ONE).java, players/$(TWO).java, scripts/parse_results.pl Executable = scripts/run_game.sh Arguments = $(ONE) $(TWO) $$(NAME) Queue
In a job file, variables are wrapped in $( ). There are 4 variable inputs into the job file: ERRF, ONE, TWO, and NAME. ERRF is the name of the file that the job's log, output, and errors should be written to; ONE and TWO are the names of the players that will be competing in this match, and NAME is the name of the machine in the condor pool that will execute this match. Notice how NAME has two dollar signs in front of it: $$(NAME). This indicates that we will not be passing a variable called NAME explicitly, and the job file should look for a variable with this handle in the Condor environment. NAME is set by Condor as the name of the machine that is executing the job. Taking a look at the other variables, we see that ERRF will only be used by the job file, whereas ONE, TWO, and NAME will be passed to the executable behind this job, which we see is run_game.sh
run_game.sh [download]
#!/bin/bash
p1=$1
p2=$2
hostname=$(hostname)
host=$3
javac $p1.java
javac $p2.java
java -jar capture.jar -player java $p1 -player java $p2 -view turns Turns.txt > temp.txt
RESULT=result.txt
tail temp.txt -n 1 > $RESULT # Final line contains result
./parse_results.pl $RESULT $p1 $p2 > ${p1}_${p2}_$(date +%m.%d_%H.%M.%S)_${host}_${hostname}.Score
rm -f Turns.txt temp.txt $RESULT *.class
exit 0
This script compiles the Player source files sent to it, creates and executes an instances of the Capture game, and saves two output files: one, Turns.txt which contain the individual moves and sent to the environment for each player, and temp.txt, which contains the results of the instance, which is the player's scores. We will be ignoring Turns.txt, as it is only used to keep the JAR file from running in GUI mode. After the match has completed, we read the last line of temp.txt, and save it in temp2.txt. Lastly, before deleting the files we no longer need, we pass temp2.txt to a second script, which will parse the score from each player into a format to be used later, and we direct that output into a hopefully unique file name, ending in .Score.
parse_results.pl [download]
#!/usr/bin/perl
use strict;
use File::Find;
my $raw_scores = $ARGV[0];
my $player_1_name = $ARGV[1];
my $player_2_name = $ARGV[2];
# This file should only have a single line in it, so are are going to assume that
open (SCORES, '<', $raw_scores) or die ("Unable to open scores file: $raw_scores\n");
my $line = <SCORES>;
$line =~/^Score: ([0-9]*) \[[0-9]*\] ([0-9]*) \[[0-9]*\]$/;
print "$player_1_name $1 $player_2_name $2\n";
This script's output will be similar to this:
Player1 15 Player2 9
Putting the Pieces Together
topWe previously saw a player file which defined the 8 players that would be competing in this tournament. We also stated that we needed to have some background information on each player in order to determine how to match them up during the tournament. To do that, we said we needed a regular season to run first and that each player would be matched against each other player 3 times during the season. Let's now put all of those pieces together.
We've pre-created a script called create_dag.pl to create an appropriate Condor DAGman file for us. All we have to do is give this script our known information outlined above as parameters:
# Player definitions Players source file Number of matches between # location players in the season ./scripts/create_dag.pl players.txt players/ 3
This script will create the following DAG for us:
JOB GAME1 submit/onegame.submit VARS GAME1 ONE="Player1" TWO="Player2" ERRF="GAME1" RETRY GAME1 10 ... JOB GAME40 submit/onegame.submit VARS GAME40 ONE="Player2" TWO="Player8" ERRF="GAME40" RETRY GAME40 10 ... JOB GAME80 submit/onegame.submit VARS GAME80 ONE="Player4" TWO="Player7" ERRF="GAME80" RETRY GAME80 10 ... JOB GAME120 submit/onegame.submit VARS GAME120 ONE="Player6" TWO="Player5" ERRF="GAME120" RETRY GAME120 10 ... JOB GAME160 submit/onegame.submit VARS GAME160 ONE="Player8" TWO="Player5" ERRF="GAME160" RETRY GAME160 10 ... JOB GAME168 submit/onegame.submit VARS GAME168 ONE="Player8" TWO="Player7" ERRF="GAME168" RETRY GAME168 10 JOB RANKING submit/rank.submit SCRIPT PRE RANKING scripts/cat_scores.sh SCRIPT POST RANKING scripts/tournamentprep.pl tournament.seeds PARENT GAME1 CHILD RANKING ... PARENT GAME40 CHILD RANKING ... PARENT GAME80 CHILD RANKING ... PARENT GAME120 CHILD RANKING ... PARENT GAME160 CHILD RANKING ... PARENT GAME168 CHILD RANKING
There are 3 distinct groups of lines in the code above; let's examine them.
The first group defines the jobs for this DAG. We mentioned earlier that 3 games between all 8 players would be a total of 168 games, so there are 168 job definitions here. We also have the VARS keyword for each job, which we mentioned earlier. But the RETRY, what does that do? If a Condor job should fail for any reason (bad machine, code crashes, etc) it will just stop by default. RETRY tells Condor to try and re-execute this job X times. If it still fails after X times, then exit.
The second group of code is the Ranking node of the DAG, which we have not covered yet. In brief, this node will take all the .Score files generated from the games, sum them up, and seed the players appropriately for the tournament.
The third group is the most vital, and it defines the structure of the DAG, mainly job dependencies. The RANKING job depends on all of the regular season jobs. Therefore, the RANKING job will not execute until all of the regular season games have complete successfully. It may be easier to visualize these dependencies.
Ranking
topWe've already given a high-level overview of the RANKING node, so lets takes another look in more detail.
RANKING makes use of PRE and POST script functionality provided on Condor DAGs. PRE scripts are run before a node is executed, and POST scripts after. In this example, this node is the only to make use of this functionality, so we will only be talking about it briefly. The PRE script for RANKING helps by addressing a downfall of Condor. Since Condor cannot transfer an arbitrary number of files, we need to consolidate them somehow: this is the purpose of the cat_scores.sh script, which is defined as the PRE script for RANKING. This script takes all of the .Score files generated by the games, and consolidates them into a new file called total.scores, which will be used by the node to appropriately rank the players for the tournament. After the node has completed, the POST script will be run: tournamentprep.pl. This script takes the output file of the node, tournament.seeds, and copies / renames player source files based on their seed. Before we go any further, lets explain how the tournament is set up.
The Tournament
topWe know that there are 8 players in this tournament. Given that this is single elimination, that results in 7 tournament games: 4 in the first round, 2 in the second round, and the championship game. We got 7 games from the following equations:
F(N) = ⌊log2N⌋, (read: floor of log2 N) where N is the number of players. This gives the number of rounds in the tournament.H(X) = 2X-i, where X is F(N) and i is a round number. This gives the number of games in that particular round of the tournament.
Combined, they are 2⌊log2N⌋-i, plugging 8 in for N, and 1 into i, we see:
2⌊log28⌋-1 -> 2⌊3⌋-1 -> 22 -> 4
By looping from 1 to the number of rounds, and putting the round number in for i in H(X), we'll get the 4, 2, and 1 described earlier. Using the DAG PARENT CHILD dependency relationship, we visualize this as:
The next step is to determine who will be playing against who in each game of each round. Using the graph above, it becomes obvious that the winners of a particular node's two parents will compete in that node. For example, the two competitors for ROUND2_GAME1 are the winner of ROUND1_GAME1 and the winner of ROUND1_GAME2. However, what about the ROUND1_GAME* nodes? Where do the players for those nodes come from? Before we get into that, we must decide how the name of the winning player will be passed to the next node. Since our tournament nodes all know where their players will come from, it would seem reasonable to reference the winning player of a particular node by the name of that node. For example, the winner of ROUND1_GAME4 would be named ROUND1_GAME4.java. A concern that arises is how to preserve the original name of the player. Our solution is to list the original players in a comment block at the top of the file, specifically the second line. When a node prepares to execute the code for a match, it reads in this name, and renames the source file so javac will compile the source files correctly. Therefore, our solution for passing players between tournament nodes is to copy and name the player source file to the name of the node that it was victorious in, and have the child node look for source files with the names of its two parent nodes.
Recall the POST script on the RANKING node--tournamentprep.pl--and our problem of ROUND1_GAME* nodes not having standard parent nodes. How do we pass the names of the players that are to compete in round 1 nodes? Simple: we use the same strategy of looking for source files of with the names of the parent nodes. Given our convention, ROUND1_GAME1 would search for ROUND0_GAME1 and ROUND0_GAME2: its logical, but nonexistent, parents. Enter tournamentprep.pl. Using the seeds determined by the RANKING node, this script names the appropriate players files in a fashion such that they will be picked up by the round 1 nodes that they are to compete in.
Because of this added complexity, we cannot use the same Condor job file and executable to run a tournament game as we did a regular season game. The job file needs to pass two additional VARS to the executable, $(ROUND_NUM) and $(GAME_NUM) (so the script know how to correctly name the winner), and the executable needs copy the winning players source file to a new file named for the round and game that the player won. We can see these changes below:
tournamentgame.submit [download]
Universe = vanilla
Log = $(ERRF).log
Output = $(ERRF).out
Error = $(ERRF).error
Requirements = (Arch == "INTEL" || Arch == "X86_64") && (OpSys =="LINUX") && (HasJava =?= True)
should_transfer_files = YES
when_to_transfer_output = ON_EXIT
transfer_input_files = scripts/run_tournament_game.sh, java/capture.jar, $(ONE).java, $(TWO).java,
scripts/parse_results.pl, scripts/present_winner.pl
Executable = scripts/run_tournament_game.sh
Arguments = $(ONE) $(TWO) $(ROUND_NUM) $(GAME_NUM)
Queue
run_tournament_game.sh [download]
#!/bin/bash
fname="$1.java"
exec<$fname
read line
read line
line=${line:0:${#line}-1}
lines=$line".java"
cp $1 $lines -f
p1=$line
fnames="$2.java"
exec<$fnames
read line
read line
line=${line:0:${#line}-1}
lines=$line".java"
cp $2 $lines -f
p2=$line
round=$3
game=$4
javac $p1.java
javac $p2.java
java -jar capture.jar -player java $p1 -player java $p2 -view turns Turns.txt > temp.txt
RESULT=result.txt
tail temp.txt -n 1 > $RESULT
winner=`./scripts/present_winner.pl $RESULT $p1 $p2`
cp "$winner.java" ROUND${round}_GAME${game}.java
We've already seen the structure of the regular season, and how it feeds into the RANKING node, and we've seen the tournament structure, and how it starts with the RANKING node. Let's visualize those two halves together:
The last node to cover is WINNER. The purpose of this node is rather simple: it merely takes the name of the player that won the game in its parent game, and outputs it into a file named tournament.champion.
Conclusion
topThe purpose of this tutorial was to show the power of Condor in an easy to understand way: that of a sports tournament. We hope that our work inspires you to utilize MUGrid to learn the usefulness of distributed computing. The code used for this tournament is available for your use under the GPL License. This basically means that you can do whatever you want to it, along as your give us credit and your work is also release under the GPL. You can download the code here.
References top
Campus Grids
