New contest type proposal.

Question

I'd like to suggest that to date we have missed a class (or maybe two) of programming puzzles.

ai-player would indicate a game played against a defined (but initially unknown) input or against a specified (but initially undisclosed) AI. The goal is to write the most successful program.

king-of-the-hill would indicate a one-on-one game played in a round-robin all-against-all. The game would need to have well defined rules and scoring, and the goal would be to write a maximally competitive program. Existing example can be seen in iterated prisoners dilemma contests and corewars. Example on codegolf.SE.

Problem these face on codegolf.se:

1. Keeping the game simple enough without letting it be trivial
2. Having someone to run the heats
3. Specifying the execution environment for the contestants
4. In the case of the AI player problem, when to reveal the contest input, and what to do if it is either too hard or too easy

---

Aside: I realize that these may be harder to write and police than code-golf, but we have had a number of complaints that the site is too close to all golf all the time. I hope to encourage enough diversity to maintain the interest of the people issuing those complaints, and to give them enough room to offer some non-golf puzzles.

Answer 1

Write-up for a possible king-of-the-hill: Iterated Prisoner's Dilemma.

Answer 2

Possible king-of-the-hill idea: Roshambo tournament.

It would be of similar format to IPD. Given that similarity, I'll keep it on the backburner.

After doing a little research, I question whether this would be actually be fun. Predictive roshambo strategies are very complicated.

Answer 3

Possible ai-player competition.

The Black Box

Give the link a quick read, it explains the game very well. (TBD: short summary of the game)

This would work on CG.SE as follows.

There would be two components.

1. The judge's Black Box program
2. Player submitted Seeker programs

Seeker programs would communicate in an interactive fashion with the Black Box program via stdout/in.

The Black Box will call the seeker program (similar to the IPD scorer) and then enter the following loop:

• The Seeker will designate which border cell to shine a ray into.
• The Black Box will respond with the appropriate response result
  • Hit, Reflection, Detour, or Miss and the grid cell
• The Seeker will indicate it is ready to solve the puzzle OR indicate it is ready for another iteration.
  • If the Seeker is ready to solve, it will output the deduced location of the atoms and the game ends.
  • If it is not ready, this process loops.

The game ends when the Seeker gives its best guess at the location of the atoms or some iteration threshold is reached (to prevent infinite loops).

One iteration is defined as one ray shining and response from the Black Box.

Scoring

Only Seekers that successfully deduce the location of the atoms are considered in scoring. They are ordered according to the fewest number of iterations. The program that has the lowest score wins.

Possible Variations

• Varying the grid size
• Varying number of atoms
• Using 'mirrors' or 'prisms' instead of atoms (affects reflection, hit rules)

---

Obviously there are a details that need to be determined, such as I/O formats. Before we get to that though I'd like some comments on the idea in general.

I haven't given much thought to how to create an effective seeker, but since this game is similar to the game Mastermind which has been proven to be NP-Complete, I wonder if it is to challenging/hard of a problem for CG.SE? As far as I know (via a 2 min Google search), this is an unstudied problem.

Some other considerations are how to facilitate testing, accept submissions, etc. Should the Black Box judge be freely available from the beginning? If not how else could testing be done? If so, is this really an AI game? (does it matter?)

Thoughts?

Answer 4

Reversi

To those who don't know it: Wikipedia entry.

This was a task for first-term students at our university a few years ago (I was responsible for grading the players).

Something that proved to be quite complex there was detecting end-game positions, avoiding illegal moves and in general adhering to the interface specification. Since the programs were piped into each other this created some situations where they would simply become stuck.

I guess if we want to do this here we'd need a game master that is responsible for maintaining the game state and simplify the protocol as much as possible (I'm not sure whether the players should be left running or simply can parse the game state on each turn. The latter might work as well and maybe better than with the CIPD).

Answer 5

PID tuner

A possible ai-player challenge.

A unreasonably large fraction of problems in control theory can be addressed with a simple PID controller. Well, they can if the thing is properly tuned, which is harder than it looks.

This challenge would provide an interface to driver for connecting the entrant to (in principle unknown) system which should be manageable with a properly tuned PID. The metric for success would be getting the output of the system to remain within a prescribed tolerance for fixed period of time, and determining when this condition was met would also be a function of the driver.

Several "test" systems would included so that entrants could check that they understand the interface and that their contribution works with it.

At some point the author would run entrants against the "official" black-box system and declare the winner.