6
\$\begingroup\$

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

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.

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 , 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.

\$\endgroup\$
  • \$\begingroup\$ why don't you float example questions of these two types and cite them? \$\endgroup\$ – Jeff Atwood Apr 28 '11 at 7:24
  • \$\begingroup\$ I took your description of 'king-of-the-hill' to fill the tag description (feel free to improve it) but couldn't do so with the ai-player tag (because it isn't used until now?) - however, there is an unfilled tag 'ai'. Since meta-tags aren't very welcomed, I don't know whether I should suggest an 1P5 tag. Having a mouse-over tooltip-text would be comfortable and avoid repeating the meaning of this pseudo-tag in every so marked question. \$\endgroup\$ – user unknown May 1 '11 at 1:07
6
\$\begingroup\$

Write-up for a possible : Iterated Prisoner's Dilemma.

\$\endgroup\$
2
\$\begingroup\$

Possible 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.

\$\endgroup\$
  • \$\begingroup\$ Nice. Simple, and much harder and more deeply evil than is immediately apparent. \$\endgroup\$ – dmckee May 1 '11 at 23:01
1
\$\begingroup\$

Possible 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?

\$\endgroup\$
  • \$\begingroup\$ Joey was of the opinion that games with non-trivial state would be better implemented with the candidate program continuing to run rather than terminating each round and being relaunched. This may be a case where that is true, and it would be nice to have an example on the site, lest people think that the model I used for IPD is the only option. \$\endgroup\$ – dmckee May 2 '11 at 0:43
  • \$\begingroup\$ Actually yes, that is what I had in mind. One entire game session would be accomplished with only a single execution. Otherwise parsing history becomes an unnecessary headache. \$\endgroup\$ – Casey May 2 '11 at 0:45
  • \$\begingroup\$ I gave a little thought to this one early on, but concluded that it was a hard challenge to implement in any language I know. Perhaps Prolog like languages can handle it naturally. I tried to think of a simplified version, but didn't come up with anything I liked. It's a good idea, but... \$\endgroup\$ – dmckee May 2 '11 at 0:45
  • \$\begingroup\$ @dmckee what about Mastermind? I've actually seen an implementation of a solver before. \$\endgroup\$ – Casey May 3 '11 at 21:34
  • \$\begingroup\$ @Casey I think that is reasonable, I have a nearly 100% algorithmic attack on the basic commercial game (and no one will play with me ::pout::), so there doesn't seem to be anything preventing a coded attack. \$\endgroup\$ – dmckee May 3 '11 at 21:37
  • \$\begingroup\$ @dmckee Hm, I'll think about that then. I still want to do something fun with lasers, mirrors/prisms/atoms/cats, and black boxes. \$\endgroup\$ – Casey May 3 '11 at 21:44
1
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$

PID tuner

A possible 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.

\$\endgroup\$
  • \$\begingroup\$ hm, I'm not familiar with control systems to really understand what this task would like in code. I read the hot/cold water faucet example on wikipedia, so could it be a program that is streamed temperatures and has to "mix" them to achieve some desired final temperature? \$\endgroup\$ – Casey May 3 '11 at 21:32
  • \$\begingroup\$ @Casey: I'm working on a proof-of-concept. There are still some bugs to iron out. \$\endgroup\$ – dmckee May 3 '11 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .