Author:

• Name: Brian Westley
  Location: US - United States of America (United States)

To build:

    make all

There is an alternate version that is supposed to win all the time.

Bugs and (Mis)features:

The current status of this entry is:

STATUS: INABIAF - please DO NOT fix

For more detailed information see 1991/westley in bugs.html.

To use:

NOTE: we have provided a script to perform the below procedure which we include for the interested. See the try section if you just want to play.

Make and then run as follows:

    ./westley [move_location] | tee nextmove.c

where the move_location is a digit from 1 to 9 that represents a move on a tic-tac-toe board:

    1 2 3
    4 5 6
    7 8 9

If you omit move_location, then the computer moves first. For your next move, recompile nextmove.c and play it again:

    make nextmove
    ./nextmove move_location | tee nextmove.c

Try:

We have provided the shell script, ttt.sh, to make it easier to play the game:

    make ttt
    ./ttt [first_move]
    ./ttt next_move

The shell script determines when the game is over, and automatically replaces merlyn.c (copied from westley.c with an improved version after a loss). The ttt script has two other modes:

     # cancel any game in progress,
     # revert to merlyn.c:
    ./ttt quitgame
     # remove all game files,
     # revert to original source:
    ./ttt clobber

For example here is a potentially losing game:

    ./ttt 1
    ./ttt 4
    ./ttt 6

To see what it might look like, try it out.

The script redirects stderr to /dev/null by default. If you need errors or warnings use -e.

Alternate code:

This version is based on the author’s remarks. It is not supposed to lose but it can lose if you cheat. That’s supposed to happen. Can you win any other time?

Alternate build:

    make alt

Alternate use:

Rather than use ttt try the script ttt.alt instead.

Judges’ remarks:

Can you figure out why the board looks different than the westley.c?

What happens if you make a move already made?

Now go try and draw or better yet win (without cheating which is very easy :-) )! Why is win better than draw? Because everyone knows how to draw:

Professor Falken: Did you ever play tic-tac-toe?

Jennifer Mack: Yeah. Of course.

Falken: But you don’t any more.

Jennifer: No.

Falken: Why?

Jennifer: Because it’s a boring game. It’s always a tie.

Falken: Exactly. There’s no way to win. The game itself is pointless. But back at the International Obfuscated C Code Contest judges’ room they believe that you can win tic-tac-toe, that there can be acceptable draws.

Try not to cheat (even though it’s very easy :-) ), the computer has not learned how to catch you doing it.

Author’s remarks:

A tic-tac-toe self-modifying program that “learns”. This C program plays standard tic-tac-toe on itself. The code is written as a tic-tac-toe grid; moves are carried out within the code.

The human is X, the computer 0 [sic, “zero”, not letter “O”].

The program, when run, reproduces itself with both the player’s move and the computer’s move added. Recompile THIS program (using the same compile line) and repeat until the game is finished.

If the computer wins, the “straight face” in the upper right-hand corner, “:-|”, will change into a happy face, “:-)”. If it is a draw, the face does not change. If the computer loses, the board is blanked and the face changes into a sad face, “:-(”. If this happens, the blank board should replace the original program; the computer changes its play and will continue to do so until it no longer loses games.

If you want a program that never loses, simply replace the string "9999999999 :-| " with "9883857753 :-| ".

How it works

The vertical “bars” of the grid are identical functions, with the name of the function as a(), b(), or c(). After each function is called, the global variables X and O contain bitmasks of where all the Xs and Os are placed. The statement:

    X=-   <char>   -1;

evaluates to 1, -1, or -2 when X is 1 and <char> is one of "X", "0", or " ". The function S(&X) sets the appropriate bits in (global vars) X and O and resets the value of &X to 1. This is how the current position is computed.

The player’s move is bitwise ORed into the X mask, and (if it is the opening move) the strategy string’s first character is set to the player’s first move (or 5 if the computer moves first).

The evaluation function y(M) checks if the mask has a winning pattern (any of the first eight bitmasks of the w[N] array), and sets the variable q to 0 if it does.

The player’s move is evaluated to see if the human has won. The smiley is set to “:-)” or “:-(” depending on this. Also, if the human has won, the digit in the strategy string is decremented to change the computer’s play for the next round.

If the human has NOT won, the e(N,M) function evaluates if ANY move not in mask N can produce a win in mask M. The first evaluation e(X,O) checks if O can make a legal winning move. If so, the computer has a winning move and makes it. If not, the smiley is set to “:-|”, and a non-winning move is generated.

A non-winning move first checks if X can win in one move; if so, this move is selected, blocking the win. Otherwise, a move is generated by looking down the list of “move templates”. The first move template that generates a move that is NOT already occupied by an X or O is returned.

The “move templates” are static tic-tac-toe positions that generate possible moves by making the e() function return “winning” moves, e.g. the template:

    . . .
    O , O    (this is the value 40; 2^3+2^5)
    . . .    ("O"s are 1 bits,
              "." and "," are 0 bits)

…will make the e() function return a center move, as this is the only move that produces three in a row. Notice that the computer does not consider which cells contain Xs and Os when making a template move, only which cells are empty and not-empty. This makes for unusual play.

The templates are carefully chosen to eventually block all traps that X can try, by just blundering in the way.

Also note that the winning & strategy templates are part of the compile line, making it possible to change the rules of the game by changing the compile line.

The templates are:

    O , O
    , , ,
    O , O

    , . .
    . O .
    . . O

    . . .
    O , O
    . . .

    . . .
    O O ,
    . . .

    . . .
    O , O
    . . .

    . , ,
    . O .
    O O ,

    O , O
    , , .
    O . .

    , . O
    O , O
    O . ,

    O . ,
    O , O
    , . O

    O , O
    , , ,
    O , O

A digit of 9 means start with the first template, 8 starts at the second, etc. The templates are scanned until a legal move is found. A template is scanned from bottom to top, right to left (i.e. move 9 is tested first, then 8, down to move 1).

Primary files

• westley.c - entry source code
• Makefile - entry Makefile
• westley.alt.c - alternate source code
• westley.orig.c - original source code
• ttt.alt.sh - script to play alternate version
• ttt.sh - play tic-tac-toe

Secondary files

• 1991_westley.tar.bz2 - download entry tarball
• README.md - markdown source for this web page
• .entry.json - entry summary and manifest in JSON
• .gitignore - list of files that should not be committed under git
• .path - directory path from top level directory
• index.html - this web page

Jump to: top