A digest of all things wϋnderful

Monthly archives for February, 2012

Windward Code Wars 2012 – Think You Can Do Better?

Windward Code Wars 2012 – Think You Can Do Better?

This last weekend Windward hosted its first annual code war competition. Many of you may ask what is a code war exactly. As we have defined it a code war is a competition where programmers design an AI (Artificial Intelligence) that must solve a programming problem in a specified amount of time. The goal of the AI is to best the other competitors taking home bragging rights for the leanest, meanest, most intelligent program above all.

Windward asked for submissions from many of the top 25 computer science universities around the world. The code war was setup to run all submissions at each school and then the top 2 finalist would move on to the semifinals and championship hosted on Windward’s servers.

Our basic problem was to build an AI modeled after the game RoboRally (which Windward staff plays frequently). The basic premise of RoboRally is that you are a robot in a factory. You can move forward, backward, left, right in any combination. The goal is for the robot to reach each of the flags on the board without dying. This sounds fairly simple but there are many obstacles that stand in your way such as conveyor belts, pits, lasers, walls and most of all other competing robots that also fire lasers. A basic game starts by the user drawing 9 cards and choosing the best five of those cards to get your robot to the flag. Each time you are hit by a laser, you lose a damage point, lose all 9 damage points and your robot powers down where ever it currently resides on the board (also leaving you open to fire from others, conveyor belts, laser, pits, you get the idea). You have three lives as a robot and when maximum damage is reached or you fall off the board or into a pit, you lose one of these lives. There are chances to heal (by landing on a flag or health square) but these are few and far between.

Windward had to make some changes to bring this game into a digital age as well as makes sense for an AI. For a full description check out the game rules we implemented here. Basically it came down to the decision by the development team if we should reward combat or not. After a few internal code wars, we decided that reward combat was best so AI’s would not turtle in corners away from combat. Our basic game consisted of a server written in C# that presented the game board and accepted network communication from each game client. The clients were written in C#, Java, Python and C++. Each of our developers assisted in getting all of this running and tested. As is with all software, if a bug was found our rule was that you could report it and exploit it. Only the team that reported the bug would be informed if a patch was put in place but we also would not inform the other teams that the bug existed. Tactical advantage depending on the bug and your viewpoint.

On January 28th, we presented the code war in 3 times zones. Logistically this had its challenges. We did not want to make the problem present until 10 AM in each time zone. This meant setting up several different meetings and getting our staff ready to handle each timezone and the questions they may have. In short we used a combination of gotomeeting and UStream for the audio video and several email aliases to handle the flood of questions. Maintaining the FAQ page became a fulltime job. Over the next few hours we kicked off all 3 times zones and then we had a little break before the real chaos hit.

10 AM kicked off and we had the east coast schools up and running after a short description of the problem. About 20 min later the questions started coming in and man did we need everyone there to stay on top of them.

 

As it approached 6 PM east coast time (competition was from 10 AM to 6 PM) the regionals were being run and the final code submissions started pouring in, literally. This is where we will be much more organized next year, we had no standard submission process for the code we received. We received programs in all forms from the single file/files they change (we loved this, drop files to overwrite the stock client and you are off and running) all the way to fully compiled source binaries and other full clients in all (this was the most difficult to find which client was used and then get the code to compile on our servers). Somehow we frantically troubleshot all the programs over the next few hours and were ready for the last regional hosted by our found David Thielen at Harvey Mudd College.

The Mudd finals were hosted live and there were several rounds. From what we heard and saw, all of the students were having a good time cheering as their AI’s drew combats against their fellow classmates. We also received many emails from the regional proctors and professors saying how much fun their students had. When the final Mudd regional aired we then had limited time to test the final programs and get them loaded onto our servers to broadcast live for the championship. We held three semifinal rounds and the top 2 teams from each semi as well as the top two third place aggregate entries were entered into the “elite eight” for a showdown to claim the title of Windward Code War 2010 Champions.

The final turned out with the following placements with the University of Wisconsin – Eau Claire campus taking grand champion, followed by the University of Massachusetts as runner up and Purdue University in third place. The additional results as well as live streaming of the finals can be found here. The contestants were thrilled but I wanted to take a moment to see something that I found in the code.

Now keep in mind that we ran 10 games in the final the best score aggregate out of all ten games was the winner so we did do several runs. Being I have a slightly skeptical nature I went ahead and ran the final with two additional runs. The results are below, and I did find some interesting things.

First Run

HMC_League_of_SmashCraft

72

102

78

74

125

51

55

37

88

51

733

UMASS_Skyward_Nord

80

47

54

47

76

53

71

87

65

68

648

HMC_Trolololol

57

49

76

32

44

39

55

36

74

70

532

UW_Grande_Letra_O

54

32

39

43

51

37

61

80

33

43

473

PU_BotBebo

17

31

83

53

35

78

47

32

40

30

446

GATECH_dBuggers

44

42

37

26

31

57

81

59

10

43

430

CU_PEDOBEAR

11

37

13

26

45

73

41

17

47

31

341

CMU_Siddant

0

53

71

38

4

29

10

10

1

10

226

 

Second Run

PU_BotBebo

70

73

46

38

59

59

32

51

75

34

537

HMC_Trolololol

43

72

65

30

45

53

39

76

43

52

518

UW_Grande_Letra_O

44

40

77

48

73

26

48

48

56

55

515

UMASS_Skyward_Nord

52

69

40

43

42

53

66

31

44

66

506

HMC_League_of_SmashCraft

119

26

38

34

44

39

68

62

31

32

493

GATECH_dBuggers

46

67

25

41

62

39

17

19

62

22

400

CU_PEDOBEAR

34

13

40

38

43

25

19

22

34

41

309

CMU_Siddant

15

4

14

16

58

32

3

20

20

16

198

 

What I found was that the top 5 teams were consistently there just in different order each time so on any given “Saturday” these teams could win. The others were consistently fighting for the bottom slots. This made me wonder what was going on, especially in the first additional run I did where team League of Smashcraft from Harvey Mudd College trounced everyone.

Team LofS had what I think is a great strategy. Watching them I saw their AI was moving from flag to flag but trying to encounter combat all along the way. Remember you are rewarded for combat as well as reaching flags and when a flag is reached you regain health. When team LofS was down at a corner flag and there were lots of other competitors trying for the same flag, they would move off flag, take a shot and then move back on the flag. This yielded maximum points from combat and flags while regaining health each time. As you can see in the first additional run, this strategy ruled. However when this team had to move between flags they ran the risk of getting killed early due to so much combat encountered before a health regeneration could be achieved. End result is that over many runs that LofS usually died ¾ the way through the round but racked up lots of points before doing so, thereby solidifying their place at the top.

Team Grande Letra O from University of Wisconsin – Eau Claire had a much different strategy and I am still trying to see a pattern without diving into the code. From what I could observe from their runs they relied on a combat escape sequence. The escape sequence came into play early, they usually started behind in points, while they avoided intense combat. But as the player pool dwindled down they were then forced to use their combat side of their AI and at that point they would always mount a phenomenal comeback.

So after reviewing these two we at Windward have decided to look at the submissions more closely to see what each of the implantations did. This is where I have a request to the open source community. We got a pretty healthy mix of Python and Java submissions followed by C# and a few C++. I would like to send a challenge for anyone who is willing to do the same and see how you stack up against our finalists.

Keep in mind if you really want to compare yourself you will only work in the eight hour timeframe we allotted for all our teams. I am curios to see how everyone turns out so you if you do take this challenge or host it for a team of your friends, let us know your results at codewars@windward.net

 

http://www.windward.net/codewar/Windward_Code_War_2012.zip