19
\$\begingroup\$

Write a program in your chosen language which plays a perfect game of tic-tac-toe on a 3 * 3 board against a human player. However, every move has to be a different program, generated from the previous iteration.

How and in what form you evaluate human input, is up to you, but it has to be read from the standard input. Similarly, you are free to choose a method how you will determine which player starts (for example, you ask first, or you allow the human to enter an invalid move to signal that the computer starts, or other ideas).

Validating moves is not necessary, you can assume a fairly playing human opponent.

Basically, you have program which corresponds to a state of the board. The state is printed in any recognizable way, but at least the following level of detail is expected:

X..
00X
x..

After the human player entered his moves, your program has to generate the next iteration of itself as a source file in the same language (either to standard output or to a file) and terminate. You are not allowed to store information anywhere else outside of that source file. (it is not necessary for your program to build and run the generated program, it can be done by the user - however, it's not forbidden). When the generated program is built and run, it will behave similarly, display the state, wait for user input, etc.

At the end of the game, you have to print the result (whether you won or it's a tie) in any unambiguously identifiable way.

By perfect play I mean the program must not lose, and if there is a possibility to force a win, it should win.

Shortest code wins, winner is selected at least 10 days after the first valid entry.

You get a 10% reduction in the score if your program can handle the building and launching of its next iteration. (I know, it's most probably not worth it) Of course, the program itself must be terminated by the time the next iteration accepts the moves from the user.

If you use some strange uncommon tricks, please post a short explanation with your code.

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice challenge, but I think I'm going to opt-out. \$\endgroup\$ – John Dvorak May 22 '13 at 18:59
  • \$\begingroup\$ "Every move has to be a different program". Do you mean, "each game has to be initiated and managed by a new, distinct instance of the original program"? \$\endgroup\$ – DavidC May 23 '13 at 1:58
  • 1
    \$\begingroup\$ @DavidCarraher : No. Every move, not just every game. Check the description below the board example. When the computer has to make a move (so the state of the board changes), your program has to generate a source file, which when built and run, will become the next state. The original program then exits. The newly generated program, when making a move, will behave similarly: it creates a source file, which when built and run, will become the next state, and so on. As no information storage is allowed except in the generated source file, it is like a quine with differences between iterations. \$\endgroup\$ – vsz May 23 '13 at 3:33
13
\$\begingroup\$

Perl, 933 characters

$m=<<'';$_='         ';
sub h{/^(?:...)*(\d)\1\1/|/^.?.?(\d)..\1..\1/|/(\d)...\1...\1/|/^..(\d).\1.\1/&&$1}
sub r{substr($_,$p-1,1)=pop}sub p{my$w=pop;my@b=(0,h==$w||h&&-1);if(!$b[1]&&/ /){$b[1]=-9;
while(/ /g){local($_,$p)=($_,pos);r$w;$r=-(p($w^1))[1];@b=($p,$r)if$r>$b[1]}}@b}
if(($w=h||!/ /)||!@ARGV){$w--&&print+(nobody,X,O)[$w]," wins\n";s/(...)/$1\n/g;
tr/ 23/.XO/;print}else{$w=3;$w^=1for/\d/g;($p=pop)?r($w^1)&&!h&&(($p)=p$w)&&r$w:s/ /2/;
print"\$m=<<'';\$_='$_';\n$m\n$m"}

sub h{/^(?:...)*(\d)\1\1/|/^.?.?(\d)..\1..\1/|/(\d)...\1...\1/|/^..(\d).\1.\1/&&$1}
sub r{substr($_,$p-1,1)=pop}sub p{my$w=pop;my@b=(0,h==$w||h&&-1);if(!$b[1]&&/ /){$b[1]=-9;
while(/ /g){local($_,$p)=($_,pos);r$w;$r=-(p($w^1))[1];@b=($p,$r)if$r>$b[1]}}@b}
if(($w=h||!/ /)||!@ARGV){$w--&&print+(nobody,X,O)[$w]," wins\n";s/(...)/$1\n/g;
tr/ 23/.XO/;print}else{$w=3;$w^=1for/\d/g;($p=pop)?r($w^1)&&!h&&(($p)=p$w)&&r$w:s/ /2/;
print"\$m=<<'';\$_='$_';\n$m\n$m"}

Please note that the blank line in the middle of the script is actually required to be there. (The line breaks at the end of the long lines are not required, other than for legibility, and are not included in the character count.)

Usage: When the program is run without arguments, it displays the current game state. Since at the start the board is empty, the output will be:

...
...
...

Run the program with an argument between 1 and 9 to claim that square as your move. The program will make its own move and then output a replacement script with the new state. Thus, for example:

$ perl ./qttt 5 > ./qttt-2
$ perl ./qttt-2
O..
.X.
...

On the very first turn only, you may give a move of 0 to indicate that the computer should take the first move. Note that the first player will always be X.

When the game is over, the display output will include a note to that effect:

$ perl ./qttt-4 6 > ./qttt-5
$ perl ./qttt-5
O wins
OXX
OOX
X.O

The program works by doing a standard minimax search of the game tree. (Tic-tac-toe is a small enough game that a full game tree can be generated on every run.) The exception to this is when the computer moves first -- in this case the initial move to the upper left corner is hard-coded.

Note that this program works in the fashion of a proper quine -- at no point does the script access its own source file in order to produce its output.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ That is beautiful! I didn't realize I was staring at a huge here-doc for the longest time, then did a double-take. \$\endgroup\$ – Jesse Smith Jul 23 '13 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.