# Noughts and Crosses (aka Tic-Tac-Toe)

Write a Notes and Crosses application.

User interface is optional.
You can output the computers move in text: eg 1x1 (meaning center square)

The computer must play an intelligent (extra marks for optimal) game.
Apart from its first move which should be random.

Player computer take turns at first move.
First player to win two games in a row wins.

Score:

• Lowest strokes wins.
• If equal best computer move algorithm (as I see fit)
• If equal submitted date.
• I believe it's spelled tic-tac-toe or tic-tack-toe, minor issue but the tag should be properly spelled.... – st0le Feb 19 '11 at 6:06
• And in en-gb it's Nought's and Crosses. – Peter Taylor Feb 19 '11 at 8:00
• @Peter: It's actually Noughts and Crosses, without the apostrophe. – Chris Jester-Young Feb 20 '11 at 6:43
• @Chris, indeed. I'm not sure where the apostrophe came from. – Peter Taylor Feb 20 '11 at 8:32
• Do you want full code version as well? I guess you do since you want to look at algorithm. – philcolbourn Mar 5 '14 at 13:33

c99 -- 1229 characters (and needs nucrses)

#include <ncurses.h>
#include <string.h>
#define R return
#define A char
#define M mvprintw
#define I int
#define O "%c wins a game, press any key to %s."
A*s=" XOCHT";FILE *r;
I W(A*b){I i,p,q,r,w[]={0,1,2,0,3,6,0,2,3,3,3,1,1,1,4,2};if(!memchr(b,0,9))
R 3;for(i=0;i<16;i++){p=w[i/2];q=w[i/2+8];r=i%2+1;if((b[p]==r)&&(b[p+q]==r)
&&(b[p+q+q]==r))R r;}R 0;};
I C(A*b, I s){A c[9];for(I i=0;i<9;i++){memcpy(c,b,9);if(c[i]==0)c[i]=s;
if(s==W(c))R i;}R -1;};I P(A*b){I i;while(b[i=fgetc(r)%9]);R i;};
I D(A*b){A*p=" |-+";I i=0,j;for(;i<5;i++)for(j=0;j<5;j++)
b[i]?s[b[i]]:'1'+i);refresh();};
I G(A m){I u=1,i,j;A b[9];memset(b,0,9);M(1,9,"Computer %c",s[m]);M(2,9,
"Human %c",s[m%2+1]);do{M(4,9,"Up %c",s[u]);D(b);if(u==m){if((i=C(b,m))<0&&(i=C
);}while(i>10||i<1||b[i-1]!=0);b[i-1]=m%2+1;};u=u%2+1;}while(0==W(b));M(8,0,O,
s[W(b)],"continue");D(b);getch();M(8,0,"%44c",*s);R W(b)==3?5:u==m?4:3;}
I main(I c,A**v){A d=0, m=v[1][0]-'x'?2:1;r=fopen("/dev/random","r");
initscr();for(;;){c=G(m);if(c==d&&c-5)break;else M(4,25,"Previous winner %c",
s[c]),d=c;m=m%2+1;}M(9,0,O,c,"quit");getch();endwin();}


It gives away characters for the users convenience by using curses and having actual English prompts and informative lines. The obvious macro golfs have been made, but there are probably some comma and conditional operator improvements still available.

Is it smart? Well, it takes one move wins and blocks one move losses, but is otherwise quite random. (I may take the weekend to repair my interrupted CS education and learn about A* trees...) The "random first move" condition is met automatically as no one has the option to win at that point. Despite this obviously deficient AI I have yet to beat it when it holds X, so I have not defeated it by the "two in a row" rules.

Structurally we have a "is there a winner" function and a "can I win with a single play" function which works by coping the board and trying each position in turn with the isWon function. The single canWin function serves first to search for winning opportunities (by passing the computer's symbol) and then to search for things than need blocking (by passing the human's).

It declares Computer, Human, or Tie the winner on each game and only C or H for the series.

Now respects the spec as to winning conditions And plays well enough that you have to let it win or Ctrl-C to get out.

The version below differs from the above in prompts as well as macroization, but still represents the approach.

#include <ncurses.h>
#include <string.h>

char*s/*ymbols*/=" XOCHT";
FILE *r/*dev/random*/;

/* return the index of the side that wins, 0 if un-won or 3 if cat's game */
int W/*on*/(char*b){
int i,p,q,r,w/*inning matrix*/[]={0,1,2,0,3,6,0,2,
3,3,3,1,1,1,4,2};
if(!memchr(b,0,9))return 3; /* detect cat games by lack of open positions */
for(i=0;i<16;i++){
p=w[i/2];   /* starting position of the winning sequence to check */
q=w[i/2+8]; /* step size of the winning sequence to check */
r=i%2+1;  /* winning value to check */
if( (b[p]==r) &&
(b[p+q]==r) &&
(b[p+q+q]==r) )
return r;
}
return 0;
};
/* returns the first square in which the current side can win or -1 if none*/
int C/*an win?*/(char*b, int s/*ide to play*/){
char c[9];
for(int i=0;i<9;i++){
memcpy(c,b,9);
if(c[i]==0)c[i]=s;
if(s==W(c))return i;
}
return -1;
};
/* returns a random unoccupied square */
int P/*ick a random move*/(char*b){
/* assumes a move is possible and will loop forever if this
condition is violated */
int i;
while(b[i=fgetc(r)%9])
;
return i;
};
int D/*raw the board*/(char*b){
char*p=" |-+";
int i=0,j;
for(;i<5;i++)
for(j=0;j<5;j++)
for(i=0;i<9;i++)
refresh();
};

/* Play a single game with the computer taking s[m] and return the winner
*
*  3 -- computer
*  4 -- human
*  5 -- tie
*/
int G(char m){
int u/*p*/=1,i,j;
char b/*oard*/[9];
memset(b,0,9); /* initalized to 0 (empty) */
mvprintw(1,9,"Computer uses %c",s[m]);
mvprintw(2,9,"Human uses %c",s[m%2+1]);
/* main loop */
do {
mvprintw(4,9,"To play %c",s[u]);
D(b);
if(u==m){
// my turn to move
if( (i=C(b,m))<0 &&    /* move to win */
(i=C(b,m%2+1))<0 ) /* 2%2+1 == 1,  1%2+1 == 2 so, the other side */
i=P(b);
b[i]=m;
} else {
// user's turn
/* get user selection */
do {
refresh();
scanw("%d",&i);
} while (i>10||i<1||b[i-1]!=0);
b[i-1]=m%2+1;
};
u=u%2+1; /* Here u is switched to the *next* player, so if the
game is one u denotes the *loser*  */
} while(0==W(b));
/* Print out the winner */
mvprintw(8,0,"%c wins a game, press any key to continue.",s[W(b)]);
D(b);
getch();
mvprintw(8,0,"%44c",*s);
return W(b)==3?5:u==m?4:3;
}

/* first argument is required and expected to be x or o
*
* x always goes first
*/
int main(int c,char**v){
char d=0, /* previous winner, starts on an impossible value */
m=v[1][0]-'x'?2:1; /* select my symbol by index into s */
/* /dev/random intialization */
r=fopen("/dev/random","r");
/* curses intialization */
initscr(); /* start curses */
for(;;){
c=G(m);
if (c==d&&c-5) // same *player* wins two in a row
break;
else
mvprintw(4,25,"Previous winner %c",s[c]),d=c;
m=m%2+1;
}
mvprintw(9,0,"Final winner is %c, press any key to quit.",c);
getch();
endwin();
}


## Bash, 591 670, 812(excluding #!/bin/bash)

x is computer. x goes first and then alternates with o for each new game. x never looses so game ends when x wins twice in a row. UI is a simple 3x3 board. Positions are numbers from 0 to 8. Occupied positions are x's or o's. x (now) plays a boring game. Although x never looses, it will randomly pick between a set of best moves to be a little bit interesting.

The code:

W()for q in 1 28 55 3 12 21 4 20;{ [[ w**3 -eq B[f=q/8]*B[g=q%8]*B[g+g-f] ]]&&$r;} B(){ local -i p R t=9 S;for((;p<9;p++)){ [[ B[p] -eq p ]]&&{ B[p]=w;W&&$e 98&&$r$p;R+=S[B[p]=p]=98-$(M+=-1;w=w^3;B);t=$((S[p]<S[t]?t:p));V=R/M;};};$e$V;$r$t;}
T()(for q in {1..9};{ $e -en${P[B[q-1]]}${N[q%3]};};W=${P[w^=3]};q=$([$w = 9 ]&&for((;B[q]!=q;)){ read -sn1 -p? q;}&&$e$q&&$r;[$M = 9 ]&&$e$RANDOM||(B>1;$e$?))%9;B[q]=w;M+=-1;$e$W..$q;W&&$e $W!&&$r $w;[$M = 0 ]&&$e Ty||T);P=({0..8} o x);N="\n";e=echo;r=return;declare -i V=49 q w=9 M=9 B=({0..8});for((;(J&(J=K))<9;w^=3)){ T;K=$?;};$e Won  I have just noticed that I use W as a function and variable. Bash does not seem to mind. Dialogue is minimal: ? means it is waiting for o to play. means it is thinking about next move. x! means X wins. Ty means a Tie. W determines if$w won.


It uses a code in $q to identify lines of positions to test. Let a line of positions be F, G, and H. Code is 8F+G. H can be derived from F and G: H=G+(G-F). eg. From 28, F=3, G=4, H=5. If board positions B[F]+B[G]+B[H]=3*w then$w has won

B $1 finds best move for player$1.
T controls a game and gets user move if $w is 0 or computer's move.  Full source code: # Players # o is opponent # x is computer # Player symbols are stored in Player array. # Board B has 9 board positions numbered 0 to 8 # 0-8=unoccupied # 9=o in position # 10=x in position # Winning line encoding # if a winning row is positions f,g, and h then these are encoded as f*8+g # h is derived as g+(g-f) Win() for q in 1 28 55 3 12 21 4 20;{ # for each code [[ w**3 -eq B[f=q/8]*B[g=q%8]*B[g+g-f] ]] && return # w won if 3 in row } # F=49 # F sets a resolution for determining value of a move. # Since AVG=sum(Score[*])/M then larger scores mean better fixed point real number. # Score is 0 to 2F. Larger F, larger score accuracy. # F is set to largest number such that 2F is 2 digits. # A move probability to win is returned in AVG. # AVG=0 o wins this move (if they play rationally) # AVG<F means o more likely to win # AVG=F means most likely a tie # AVG>F means x more likely to win # AVG=2F means x wins # p must be integer or it does not get initialised to 0 # R must be integer and it gets initialised to 0 # t needs a starting default value of 9 if there are no empty positions Best(){ # here we have to silently play lots of games to choose best move local -i p R t=9 Score # save board and move count for((; p<9; p++)){ [[ B[p] -eq p ]] && { # empty position B[p]=w # occupy it Win && echo 98 && return$p                # if w won then restore board, set score to 2F
R+=Score[B[p]=p]=98-$(M+=-1; w=w^3; Best) # restore board, inc move & what is opponents best move? t=$((Score[p]<Score[t]?t:p))               # if score is better then restart list with this position
AVG=R/M                                    # average scores
}
}
echo $AVG # set score return$t                                      # return first best position
}

# Take Turns.
#   Starting with other player (w^3), take turns and count down remaining turns.
#   Get a move from opponent or computer. Ensure opponent move is legal.
#   If there is a winner, return winner (9=o 10=x).
#   If game over, return tie (0)
#   Else take next turn
#   Changes w, W, M, B, p

Turn()(
for q in {1..9};{
echo -en ${Players[B[q-1]]}${N[q%3]}  # show position or player and newline every 3rd
}
W=${Players[w^=3]} # W is symbol of other player # if o, get move. else if game start, random move. else get best move for x q=$([ $w = 9 ]&&for((;B[q]!=q;)){ read -sn1 -p? q;}&&echo$q&&$r;[$M = 9 ]&&echo $RANDOM||(Best>1;echo$?))%9
B[q]=w                                  # move and occupy board position
M+=-1                                   # dec move count
echo $W..$q                             # show move
Win        && echo $W! && return$w     # w has won
[ $M = 0 ] && echo Ty || Turn # return 0 tie after 9 moves and no winner or another turn ) # Play a game. # Board can be configured as you like. Ensure M represents number of moves remaining. # AVG is used by Best to return value of best move. # Loop for competition to declare winner after 2 wins in a row. # Turn returns 9=o win, 10=x win, and 0=tie # w is non-starting player: 9=o 10=x # w swaps between 9 and 10 for subsequent games # AVG is a global used to calculate/store average value of a move. # Since Best() is called in a subshell, it will always be 49. # q is a globally used integer # M is number of moves remaining. Starts at 9 and when 0 board is full and game over. Players=({0..8} o x); N="\n";e=echo;r=return declare -i AVG=49 q w=9 M=9 B=({0..8}) # player=H, empty board, 9 moves to go for((; (J&(J=K))<9;w^=3)){ # start with X (9^3); while tie or not 2 in a row Turn K=$?                                  # K=who one
}
echo Won                                # I should cheat and just say x won to save more characters


# Javascript 271

This is not a real entry in this competition, but i just wanted to share this interesting algorithm with the other (potentional) competitors.

b=[[8,8,8,8],[8,0,0,0],[8,0,2,0],[8,0,0,0]]
m=[2,2]
for(n=0;n<4;n++){
i=prompt(m).split(",")
r=+i[0]
c=+i[1]
b[r][c]=1
if(!b[r][c+1]){b[r][c+1]=2;m=[r,c+1]}
else if(!b[r][c-1]){b[r][c-1]=2;m=[r,c-1]}
else if(!b[r-1][c]){b[r-1][c]=2;m=[r-1,c]}
else{b[r+1][c]=2;m=[r+1,c]}}


It takes input of the form r,c where r is the row and c is the collumn, and it outputs in the same format. It does not output the last move since it's not a choice. This algorithm is sooooo simple that you can probably implement it in less than 100 chars if you do it right! It works as follows:

1: The computer takes the first move (2,2)
2: The user makes any move
3: The computer checks if he can make a move on the square to the right of the user, if he can't he checks for the left, if he can't he checks for the square above and if he still can't he puts it on the square below.
4: Go to step 2

Try to beat it!

• 1) Trouble is this does not implement the question. 2) 2,2 (center square is not the best move (it is the simple move if you want to force a draw). But you can not force a win from that starting point. The best first move is a corner. If the second player makes a mistake on their first move you can force a victory (if they play anywhere but the center). If they play the center you can still force a draw. – Martin York Mar 3 '14 at 17:21
• @LokiAstari "This is not a real entry in this competition, but i just wanted to share this interesting algorithm with the other (potentional) competitors." – Jens Renders Mar 3 '14 at 18:26
• Asked 3 years ago and only had one response until yesterday. – Martin York Mar 4 '14 at 1:24
• @LokiAstari May have something to do with meta.codegolf.stackexchange.com/questions/1137/… – dmckee Mar 5 '14 at 5:33
• @LokiAstari, Actually I posted my entry on March 2. – philcolbourn Mar 8 '14 at 9:25

# Java 1801 1691 1467

So yeah, this is definitely a revival, but as a new participant on codegolf I hope you won't hold it against me.

Edit: Changed from multidimensional array to single dimension array, also stripped out a bunch of unnecessary parenthesis. Next step will be to write a different "brain" for the computer. Even as it is, although not perfect, it does pretty well. I'm probably going to set up a version that has the computer play itself, for kicks. When I do, you can find it in my github.

Edit2: Replaced q and b methods with a single d method that performs all the work of q and b based on a flag passed in that chooses the "mode", 1 for win or block (prior q method), 0 for future-move-win choice (prior b method). Saved more than two hundred characters, hurray.

I spent some time golfing in Java, and this is what I came up with:

import java.util.*;class W{public static void main(String[]a){(new W()).t();}void p(String k,int i){System.out.print(k+(i<1?"":"\n"));}int[]M;int P;int c(){int m,a,b,i;for(a=b=i=0;i<3;i++){a=M[i*3];b=M[i];m=a==M[i*3+1]&&M[i*3+1]==M[i*3+2]&&a>0?a:b==M[i+3]&&M[i+3]==M[i+6]&&b>0?b:0;if(m>0){return m;}}m=M[4];return M[0]==m&&m==M[8]||b==m&&m==a?m:0;}void g(){for(int i=0;i<9;)p(w(M[i]),i++%3/2);p("",1);}int x(int i){return(new Random()).nextInt(i);}String w(int i){return(i<1)?".":((2*i-3)*P<0)?"X":"O";}int y(){return(new Scanner(System.in)).nextInt();}void Z(){int i;do{i=x(9);}while(!s(i,1));}int o(int a,int b,int c,int z,int x){return a==b&&c==x&&a==z?2:a==x&&b==c&&b==z?0:a==c&&b==x&&c==z?1:-1;}int d(int z,int y,int k){int i=0,j;for(;i<3;i++){if((j=o(M[i*3],M[i*3+1],M[i*3+2],z*k,z*(1-k)))>=0?s(k>0?i*3+j:i*3+2-j/2,y):(j=o(M[i],M[i+3],M[i+6],z*k,z*(1-k)))>=0?s(k>0?i+3*j:i+(2-j/2)*3,y):0>1)return 1;}if((i=o(M[0],M[4],M[8],z*k,z*(1-k)))>=0?s(k>0?i*4:8-(i/2)*4,y):(i=o(M[2],M[4],M[6],z*k,z*(1-k)))>=0?s(k>0?i*2+2:6-(i/2)*2,y):0>1)return 1;return 0;}void z(){if(!(d(1,1,1)>0||d(2,1,1)>0||s(4,1)||d(1,1,0)>0))Z();}boolean s(int i,int z){if(M[i]<1){p(w(z)+" to "+i%3+","+i/3,1);return(M[i]=z)==z;}return 0>1;}void t(){while(1>0){M=new int[9];int m=9,x;if(x(2)<1){P=1;Z();g();m--;}else P=-1;do{do{p("x?",0);x=y();p("y?",0);}while(!s(y()*3+x,2));m--;g();x=c();if(x>0||m<1)break;z();g();m--;x=c();}while(m>0&&x<1);if(x<1)p("No winner!",1);else p(w(x)+" wins!",1);}}}


Ungolfed, with comments (and perhaps some longer variables/method names):

import java.util.*;
public class TicTacToeGolf {
public static void main(String[] args) {
(new TicTacToeGolf()).start();
}
/** Wrap System.out.print to avoid all that typing */
void p(String k, int i){
System.out.print(k +((i<1)?"":"\n"));
}
/** Game board */
int[][] gg;int P;
/** Check all possibilities for winner, return 0 for no winner, 1 for X, 2 for O */
int c(){
for(int[]i:gg)
if((i[0]==i[1])&&(i[1]==i[2])&&i[0]>0)
return i[0];
for(int i=0;i<3;i++)
if ((gg[0][i]==gg[1][i])&&(gg[1][i]==gg[2][i])&&gg[0][i]>0)
return gg[0][i];
int m=gg[1][1];
return (((gg[0][0]==m)&&(m==gg[2][2])||(gg[0][2]==m)&&(m==gg[2][0]))?m:0);
}
/** Print game board */
void g(){
for(int[]i:gg){
for(int j:i)
p(w(j),0);
p("",1);
}p("",1);
}
/** Generate a random value */
int x(int i) {
return (new Random()).nextInt(i);
}
/** Convert 1 to X, 2 to O */
String w(int i) {
return (i<1)?".":((2*i-3)*P<0)?"X":"O";
}
/** Get a number from the input */
int y() {
return (new Scanner(System.in)).nextInt();
}
/** Pick the next move for the computer */
void Z() {
int i,j;
do{
i=x(3);
j=x(3);
}while(!s(i,j,1));
}
/** Check for win or board condition for player z based on an ordered set of values a,b,c having one space with player x */
int o(int a, int b, int c, int z, int x) {
return (a==b&&c==x&&a==z)?2:(a==x&&b==c&&b==z)?0:(a==c&&b==x&&c==z)?1:-1;
}
/** Check for win over rows, cols, and grids for user z, place for user y based on findings.
*  Means will block z if z != y */
int q(int z,int y){
int i=0,j;
// check for win or block
for (;i<3;i++){
j=o(gg[i][0],gg[i][1],gg[i][2],z,0);
if (j>=0){s(i,j,y);return 1;}
j=o(gg[0][i],gg[1][i],gg[2][i],z,0);
if (j>=0){s(j,i,y);return 1;}
}
i=o(gg[0][0],gg[1][1],gg[2][2],z,0);
if (i>=0){s(i,i,y);return 1;}
i=o(gg[0][2],gg[1][1],gg[2][0],z,0);
if (i>=0){s(i,2-i,y);return 1;}
return 0;
}
/** Check for placement options over rows, cols, and grids for user z, place for user y based on findings.
*  Means will block z if z != y */
int b(int z,int y){
int i=0,j;
// check for placement or block
for (;i<3;i++){
j=o(gg[i][0],gg[i][1],gg[i][2],0,z);
if (j>=0){s(i,2-j/2,y);return 1;}
j=o(gg[0][i],gg[1][i],gg[2][i],0,z);
if (j>=0){s(2-j/2,i,y);return 1;}
}
i=o(gg[0][0],gg[1][1],gg[2][2],0,z);
if (i>=0){s(2-i/2,2-i/2,y);return 1;}
i=o(gg[0][2],gg[1][1],gg[2][0],0,z);
if (i>=0){s(2-i/2,i/2,y);return 1;}
return 0;
}
/** Pick the next move for the computer, smartly */
void z() {
// Check for win
if (q(1,1)>0)return;
// Check for block
if (q(2,1)>0)return;
// check for best
if (s(1,1,1))return; // try to take center.
// take whatever would win the subsequent turn if the other person is stupid.
if (b(1,1)>0)return;
Z(); // take anything.
}
/** Check if move is possible, if so do it, otherwise return false */
boolean s(int i, int j, int z){
if (gg[i][j]<1){
p(w(z)+" to "+j+","+i,1);
return (gg[i][j]=z)==z;
}
return 0>1;
}
/** Play the game, Computer gets first  move. */
void start() {
while(true){
gg = new int[3][3];
int moves=9,x;
if (x(2)<1) { // Computer starts.
P=1;
Z();
g();
moves--;
}else P=-1;
do{
do{
p("x?",0);
x=y();
p("y?",0);
}while(!s(y(),x,2));
moves--;
g();
if (c()>0||moves==0)
break;
z();
g();
moves--;
}while(moves>0&&c()==0);
if(c()<1) p("No winner!",1);
else p(w(c()) + " wins!",1);
}
}
}


Some usage notes:

• 50/50 chance for who takes first turn.
• Move of "X" or "O" announced before displaying the game board.
• Choice of cell is specified as column, then row, indexed from 0.
• Entering something outside [0,2] will cause a index exception and end the game.
• If computer goes first, takes a random move (no preference for any board location).
• Computer will take one move wins, block one move losses, plays conservatively (prefers center if available), tries to set up a two-turn win (hope other player doesn't block), and if that fails? Picks a random spot. So doesn't play a perfect game, but plays a great game. I can force a win due to the random start possibilities, but computer will force a win as well if I start badly.
• Wins are detected immediately.
• Impossible-to-win is not detected; you must play every game to the end or let the other player win.
• At the end of each game, a new game begins, again with a randomly chosen starting player.
• Took a few hits to character length by including a usable UI.
• Use Ctrl+c to end.

Example game (with computer starting, so first placement is random):

\$ java W
X to 1,2
...
...
.X.

x?1
y?1
O to 1,1
...
.O.
.X.

X to 2,2
...
.O.
.XX

x?0
y?2
O to 0,2
...
.O.
OXX

X to 2,0
..X
.O.
OXX

x?2
y?1
O to 2,1
..X
.OO
OXX

X to 0,1
..X
XOO
OXX

x?0
y?0
O to 0,0
O.X
XOO
OXX

X to 1,0
OXX
XOO
OXX

No winner!


There's definitely room for improvement. One place is likely replacing the multi-dimensional array with a one-dimensional array(done), and replacing the more complex decision logic with either a reduced form of the same(done), or a more concise best-choice solver.

Play around with it and let me know what you think. I've got this hosted over on my github so feel free to fork, clone, and create pull requests with improvements.

• Glad to see some competition. My answer should have been beaten ages ago. – dmckee Mar 5 '14 at 4:38
• Your answer is pretty golfed! But yeah, I was surprised to see so little attention to this problem, given the straightforward nature of the question. – ProgrammerDan Mar 5 '14 at 5:20
• Why import java.util.* when you can import java.*? – proud haskeller Aug 7 '14 at 6:02