MegaMinerAI 12: Mars 20 Oct 2013
Discover Segfaults on other Planets!
We at Missouri S&T ACM SIG-Game are excited to announce our newest game: Mars! Mars will be the twelfth MegaMinerAI hosted by ACM SIG-Game.
MegaMinerAI is an artificial intelligence (AI) programming competition held in Rolla, Missouri on the campus of Missouri S&T. Competitors are given 24 hours to learn the new game, develop a strategy, and implement their AI. At the end of 24 hours, an automated tournament is run, and prizes are awarded to the top three student teams. Non-student teams are welcome to participate as well, but will be ineligible to win prizes.
Registration is $24 per team. This semester, teams will receive a $4 discount for each of their team members that is also a paid member of Missouri S&T’s ACM student chapter. Interested in joining Missouri S&T ACM? Check out their website!
Mars will begin at noon on Saturday November 9th, 2013 and will end at noon on Sunday November 10th, 2013. Check out the tentative schedule below for details. A campus map is available here.
Saturday November 9th
- 12:00 PM Meet in 199 Toomey Hall for Game Kickoff
- 12:30 PM Migrate upstairs to computer labs (follow the signs!)
- 12:35 PM Begin coding!
- 6:00 PM Dinner tournament (Winners are given back registration fee)
- 6:30 PM Dinner!
Sunday November 10th
- 8:00 AM Breakfast!
- 12:00 PM Code submission closed. End of competition
- 12:15 PM Lunch!
- 1:00 PM Migrate downstairs to 199 Toomey Hall to watch the Final Tournament
- 1:30 PM Winners determined and prizes awarded
Smarter Arena Scheduler 17 Apr 2013
Going through the survey responses, I see some things that I can respond to. I’m going to respond to one thing per post, and these posts will be spread out over several days. First: A smarter arena scheduler.
A Smarter Arena Scheduler
As it happens, I’m writing this blog entry in a big comment at the bottom of a file where I’m testing the algorithm for a smarter arena scheduler. To explain the algorithm, first I have to go back to the reason the arena exists.
The arena has an impossible task. It exists to determine a total ordering of AIs. How is this an impossible task? Rock, paper, scissors. Imagine three AIs. Call them Rock, Paper, and Scissors. Rock always beats Scissors. Paper always beats Rock. Scissors always beats Paper. Who is first place? This example is contrived only in the use of the word ‘always’. For the top three student teams in our most recent MegaMinerAI, Team A beat Team B almost exactly 50% of the time, Team B beat Team C almost exactly 50% of the time, and Team A beat Team C ~65% of the time. Were the arena required to rank teams A and B in isolation, it would be forced to call them equal. Only the inclusion of Team C allowed me to distinguish between A and B, and rank A above B. Multiply by 30 more teams, all with various non-transitive win ratios, and you can see the difficulty with establishing a total ordering.
But nobody really cares about a total ordering. Not really. They may say that they do, but they don’t. What they really care about is the ordering as seen from their point of view. “Who do I beat?” “Who beats me?” “By how much?” If I can provide each team with a list of their predicted win ratio against every other team, that’s probably good enough.
So. How do I propose to schedule games in such a way as to maximize the accuracy of a list of predicted win ratios? By focusing on the close ones.
Let’s say you’re a comfortably middle-of-the-pack team. Every time you play a game with the leader, you get smashed. Your win ratio there is 0.0. There’s this other guy that you sometimes play a game with, who still has ShellAI running, and this isn’t one of the MegaMiners where ShellAI did well. Every time you play that guy, you smash him. Your win ratio there is 1.0. Experience suggests that your win ratio against either of those guys is unlikely to change very much, except for some edge cases that I will cover later. Once I’ve established your record with those guys, I shouldn’t run very many games with them.
There’s this other guy in the arena with you though. The two of you are nearly equal, primarily because you’re sitting right next to each other and keep copying each other’s code every time anyone gets up and goes afk for more than a minute. Your win ratio with that dirty cheater is 0.5, and that’s where the arena should be focusing its effort, when it’s playing games for you.
So that’s part of it. Focus on the close ones. But there’s a problem there. Let’s say it’s midnight and you’ve never pushed. You’re still running ShellAI, and everyone beats you. The arena has run something like 400 games on your behalf so far, and you’ve lost most of them. But it’s midnight now, and you just pushed an AI that beats everyone, every time. Notwithstanding the lunacy of going 12 hours without pushing, how long does it take the arena to realize you’re beating everyone?
Forever! The arena will need another 12 hours just to figure out that you’ve pulled even, if it uses the total win ratio to predict current win ratio. So it doesn’t do that. Instead, it uses a concept called Q-learning to establish a sort of moving average of predicted current win ratio. The predicted current win ratio is less stable than the total win ratio, wobbling around with every win and loss. This dynamic instability is what allows the scheduler to react quickly to changes in AI behavior.
###Displaying Win/Loss Ratio
One consequence of all of this is that your win/loss ratio will be meaningless. Unless you’re the very best (or the very worst), the system will forever be finding challenging games for you, and your win/loss ratio should hover around 50%.
###When Can We See It In Action?
Soon. As of this writing, the MegaMinerAI 11 extended arena is still running, and I hope to switch it over before it ends. After that, the chess arena continues for a few more weeks.Posted by: Nuckolls
Arena Mishmash 17 Apr 2013
Today I’ll talk about a mishmash of small topics. Arena related, all.
###Smarter Arena Scheduler Yesterday’s news, literally. It’s running. Feedback appreciated, as always. As is normal, I’m getting the majority of my feedback from former devs, who have their own biases. I don’t get enough feedback from The Typical User.
###Push to Git During Tournaments Our current procedure disallows alterations of the competitor git repositories during tournament runs. This can be a problem for competitors who are actually using their repo as a version control repo, and not just as some crazy submit system that the devs seem to be excited about. After a careful examination of our tournament startup procedure, I’m sorry to report that we still need to lock you out of your repos. For about 90 seconds. Right at tournament startup. After that we can immediately let you back in. I have updated our procedure for tournament startup to reflect the shorter lockout time.
###Game Injection This comes up once in a while. Competitor A wants to play a game against Competitor B. He would like to go to somewhere on the website and select Competitor B from some sort of dropdown list and have a game run immediately. Of course some sort of mechanism would need to be in place to keep people from abusing such a feature.
This already exists. The antiabuse mechanism is that only arena devs have the necessary login info get to the page with the dropdowns. You want a game run? Ask an arena dev. We got your back. If you ask too often I’ll make you do pushups.
###Chess Arena Falls Apart During MegaMiner Yeah, sorry about that. Our manpower pool is limited. When MegaMiner is running, it’s the priority. A Bad Thing happened the day before MegaMiner, and we had to scramble like crazy to ensure MegaMiner happened at all. In the confusion we didn’t get certain backend doodads restarted. Woops!
###Final 4 of Global Division Someone suggested that immediately after the final sequence of the triple elim for the Student Division, we could show the Final 4 of the Global Division. I like it. We’ll look into it.
###Visualizer Arena Autolink There was a visualizer feature request that went something like this: I have this visualizer window open in front of me, on my computer. When I’m not actively debugging a specific game, it’d be neat if my visualizer could show the games that the arena played for me.
The first technical challege for that is on the visualizer. If the visualizer hits the beanstalk looking for a gamelog URL, and the beanstalk doesn’t have one ready to go immediately, the visualizer hangs and crashes. Anyone want to fix that? Please? It’s really annoying.
The second technical challenge is ensuring that nobody else can access your stream. The website already has a low-security password for you, used to access your git repo. Perhaps we can use that. Anyone want to join the dev team and implement this?
That’s it for today. Tomorrow I’ll talk about tournament structure, and why we do a triple-elim (hint: you asked for it).Posted by: Nuckolls
Reef Winners! 15 Apr 2013
After running a zillion games, we’re happy to announce the winners of Reef!
- 1st Place: Men of War
- 2nd Place: Balls Deep
- 3rd Place: Unbendable Steel Clouds
Hope everyone enjoyed the game and competition, we hope to see you back in Fall for MegaMinerAI 12.
Also, we’ll be sending out a sheet for competitor feedback, please fill it out as best you can.
Thank you everyone, couldn’t do it without you!Posted by: Kellogg
Welcome 13 Apr 2013
We’re having orientation at 12pm in Toomey 199, this is our chance to unveil the game. This is also your chance to ask any and all questions you have.
Sea you all there!Posted by: Kellogg