Game for Next Contest

[Zannick]

In preparing for the next contest (which may be starting in February 2011, so I've heard), we have to settle on a game. The earlier this is done, the better, so we can nail down rules specifics (and map generators, if necessary). There are already some new ideas being discussed and drawn out in the Suggestions forum, and the google repo contains a couple of wiki pages that are good to read: http://code.google.com/p/ai-contest/wiki/GameCriteria and http://code.google.com/p/ai-contest/wiki/GameIdeas. I won't copy them completely here, but I will summarize.

Game Criteria: We want to pick a game that is Easy (to write a bot for), Familiar (people have seen it before), Interesting (fun to think about/read about/watch), Technically Feasible (with our finite time and machine resources), and Non-trivial (there shouldn't be an obvious best strategy). Obviously "Familiar" is the weakest requirement. I would venture a guess that many people didn't know what Galcon was before the Planet Wars contest.

Going through the types of games, I find there are three main choices that differentiate them partway: 1v1 or multiplayer, turn-based or simultaneous turns, and fixed layout (like Chess) or randomized starting positions (such as maps or starting pieces). We have to consider each decision carefully against our game criteria to narrow down what would be an acceptable game to choose. The last two games were Tron and Planet Wars, both 1v1 games with simultaneous turns and randomized maps.

Multiplayer games can be more Interesting and Non-trivial than 1v1 games, but our current rating system (ELO) isn't a good metric for multiplayer game rankings, though some people have tried to do so (eg, considering the game as a set of 1v1 games between each player, so a four-player game is three "games" per player). Second, running more bots for a multiplayer game will reduce the number of games per minute we can support.

Simultaneous turns make the game more interesting due to a "real-time" feel it gives. Alternating turns means one player goes first.

Randomized setups are more interesting due to the randomization factor, but sometimes using two different sets of maps can change the order of player rankings.

The following are my personal opinions and not set in stone.

I would recommend a 1v1 simultaneous turn game with randomized setups. My reasoning is that a multiplayer game will have a higher a barrier to create an AI for, will take longer to set up a contest for, and will require much more resources to have a similar rate of games. The second reason is my primary objection to doing a multiplayer game for the next contest; I am not ruling it out for a future contest where we have more preparation time. The simultaneous turn and randomized setups are mostly cosmetic preferences, for more interesting games.

I want to eliminate Chess and Go for being done to death, Arimaa for already going on elsewhere, Least Unique Positive Integer and Maze Escape for being dull. (Mazes are also a popular AI puzzle.) RPS, Tron, and Galcon have been done before. Eliminating all the other fixed layout and multiplayer games from the Game Ideas list leaves Blokus, Scrabble, Multi-Agent Battle, and Billiards, none of which I am particularly enthused about.

Any ideas or opinions?

[Zannick]

Oh, I also recall another type of game Jeff suggested: a massively multiplayer game wherein there aren't strict "games" between players but a global scoreboard based on what a bot "does" during the competition.

This is also something I'd be hesitant about doing due to technical and time constraints.

[antimatroid]

Here are my thoughts on important game criteria, in order of importance:
1. A game that is technically feasible (without that we don't really have a contest). This includes factors like how long a practical game will go for, eg. if a game can go for longer than 5 minutes in the worst case, it may not be feasible to get a half decent ordering of the bots at the end.

2. A game that is easy in concept (easy to pick up the rules and get going with the starter packages) but rich in strategy and actual difficulty, leading to interesting game play and lots of room for strategy variation near the top of the leaderboard (also meaning the game should preferably not be solvable within the time constraints). I think tron maybe lacked on that second part whereas planet wars got it about right.

3. The game should be addictive and fun to watch.

Beyond that, I don't think it really matters what type of game is chosen. I don't see why game familiarity is important at all, using games that have already been studied for ai extensively is a particularly bad idea (people will just go and look up what people did previously).

Below are my personal thoughts on what types of games should be used for these contests, I realise they don't align with everybody else.

There are already at least a couple of sequential game ai contests run each year (Arimaa, and I forget the other one), not to mention all the work that has been done on checkers, chess, hex, go, etc. I don't really see the point of adding yet another one of these types of contests, people can already self select from a few different options there. Some people have also suggested decision based *games* (like infinite mario brothers), where you are trying to solve a particular decision problem rather than actually outdo your adversary, there are already contests that go along these lines, and personally I don't think it's anywhere near as interesting strategy wise.

Some people have expressed interest in a prediction based game, if this were to be based on predicting something independent of the competition, then again I'm not sure I'd really call it a game, and there are already quite a few choices for people interested in these kind of things, cough kaggle cough. What could possibly be interesting here is if the bots are predicting something that is determined by the other bots predictions/actions, the obvious example being guess the average of guesses, but that's got a very trivial optimal strategy. Something like a small economy where bots could interact and make predictions etc. could work well, but not entirely sure how it would be set up.

Other than that, I think this contest has made a bit of a name for itself with simultaneous games, I don't see any particular reason to deviate from that at this point. I also personally feel they lead to faster paced games that are more interesting to watch and lead to cooler strategies.

Fixed layout is less interesting, I'm pretty keen to move to every game is on a new map from the specified generator (although I would be reserved about doing that for a game like tron).

Moving away from 1v1 presents a huge difficulty in ranking bots (would need to move to something like true skill) while also making any game a few orders of magnitude harder as people need to start forming coalitions and working out when to break them etc. While I agree that sounds like a lot of fun, I don't see us running out of interesting 1v1 game ideas any time soon, so I'm reluctant about moving to an actual multiplayer game for the final contest.