Tic Tac Toe page 2

In a effort to carry on the "smallest program" mandate, I have written the JavaScript version as compactly as possible.

Description of Program

The following descriptions cover the purpose of each function and their general operation. It does not explain fine details of logic flow, formulae and coding techniques.

The Tic-Tac-Toe square assignments are as follows:

124
128 256 8
643216

The numbering sequence starts at 1. Double that integer every square. Start at top left and proceed clockwise in a spiral fashion ending up in the middle.

This scheme was chosen for its several advantages:

  • Tracking which squares have been played is done by examining their sum. Each configuration gives a unique number.
  • Board corner and side positions occur in alternating sequence. This consistency makes them easy to access.
var j, c, i, w, m, r, a, u, q = [7,392,112,193,290,28,273,324]

q - an array that maps squares to rows. There are eight (8) rows: 3 horizontal. 3 vertical, and 2 diagonal. The elements are the totals of the square numbers that make up that row.

a ("all") - holds 9 bits indicating which squares have been played by either player. 1 means empty, 0 means taken.

u ("user") - holds 9 bits indicating which squares have been played by user only.

w ("wait") - non-zero used to block the input during the 'thinking' delay computer's move and when a game is completed.

m ("move") - indicates which player. It alternates between 1 (person) and 4 (computer).

r ("row") - an array of eight (8) sums corresponding to the eight rows.

i, j, c - miscellaneous counters and temporary stuff

Function 'p' ("ply"). Ply is game theory terminology. Click link for definition.

function p(s) {
a ^= s
u |= s * (w = (m ^= 5) & 1)
for (c = 8; c--;)
    q[c] & s && (r[c] += m)
eval("s" + s + ".src='" + (w ^ z.checked) + ".gif'") }

This is called for each move made by either player. The parameter 's' is the square number played: 1, 2, 4, 8, 16, 32, 64, 128 or 256. Several states are updated. The "row" sums are updated. They maintain potential two-in-a-row of either player that must be considered for future 'win' or 'block'. Place "X" or "O" on the screen.

Function 'n' ("any")

function n(j) {
if (a >> 8)
    p(256)
else for (;;) {
    for (c = [], i = j++; 256 > i; i *= 4)
        a & i && c.push(i)
    if (c.length)
        return p(c[0 | Math.random() * c.length])
    }
}

This is the fallback strategy if nothing more important such as 'winning' or 'blocking' was needed.

In the following priority order:

  1. play centre if possible
  2. play any available corner chosen at random
  3. play any available side chosen at random

The parameter selects whether to look for empty corners and sides in that order ('j' is 1), or just the sides ('j' is 2).

Function 'e' ("response")

function e() {
for (i = 8; 0 < i && 0 > (j = r.indexOf(i)); i -= 6);
0 < i ?
    (p(a & q[j]), w = i & 8 && (g.innerHTML = "Computer Wins!"))
    : 0 <= (j = [66,132,9,18,36,72,33,144,17,37,68,73,82,148].indexOf(u)) ?
        8 > j ? p(1 << (j & 6)) : n(2)
        : (0 > (j = [40,160,130,10].indexOf(u)) ?
            j = 0
            : a ^= j = 1 << 2 * j, n(1), a ^= j) }

This contains the logic for the computer's response.

First look for any possible 'win' or necessary 'block' in that order. We do this by looking for any rows' sums that equal 8 (computer has two in a row) or 2 (person has two in a row). If so then play the remaining square. Otherwise the play-strategy is employed.

The arrays are possible person's occupancy patterns. The following tables list the patterns and corresponding responses of the computer.

PatternOccupiedResponseStrategy
66top side, bottom lefttop leftC2
132left side, top righttop leftC2
9right side, top lefttop rightC2
18top side, bottom righttop rightC2
36bottom side, top rightbottom rightC2
72right side, bottom leftbottom rightC2
33bottom side, top leftbottom leftC2
144left side, bottom rightbottom leftC2
17top left & bottom right (opposing corners)any sideC1
37top left, top right, bottom sideany sidespecial
68top right, bottom left (opposing corners)any sideC1
73top left, bottom left, right sideany sidespecial
82bottom left, bottom right, top sideany sidespecial
148top right, bottom right, left sideany sidespecial

PatternOccupiedResponseStrategy
40right side, bottom sideany corner except top leftC2 modified
160left side, bottom sideany corner except top rightC2 modified
130top side, left sideany corner except bottom rightC2 modified
10top side, right sideany corner except bottom leftC2 modified

Function 't' ("take")

function t(b) {
v.disabled = 1
w || ~a & b || (p(b), a ? setTimeout(e, 800) : g.innerHTML = "Tie Game") }

This function is triggered whenever the person clicks on a square. The parameter is the square number played. This click may be rejected if the square is already played or the game is blocked due to the game being completed (either computer has won or it's tied).

We use 'setTimeout' to allow the screen to be updated as the browser's JavaScript does not multitask. An 800 millisecond delay makes game play feel more natural.

Function 's' ("reset")

function s() {
v.disabled = w = u = i = 0
m = 4
a = 511
g.innerHTML = ""
r = []
for (; i < 9; r[i++] = 0)
    eval("s" + (1 << i) + ".src='b.gif'")
}

Initializes the board graphics to all black squares. Resets the arrays and status bits.