What's your next move?
Perl, 101 98 bytes
Includes +4
for -0p
Run with the input on STDIN
tictactoe.pl
OXO
---
--X
^D
Output is the same diagram, but with each move updated with its status, 1
represents a win, 2
represents a draw and 3
represents a loss. For this case that would be
OXO
223
21X
so 3 moves draw, 1 wins and 1 loses (I'll update the solution if this output format is unacceptable, but the basic code will remain the same)
tictactoe.pl
:
#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
This is already painfully slow and uses lots of memory for the empty 3*3 board (why actually, the recursion doesn't go that deep. Must be some memory leak). Adding memoizing costs 6 bytes but is a lot saner:
#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
Javascript (ES6), 320 294 bytes
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))
Input
1) An array of array of characters describing the current board, such as:
[['X', '-'], ['-', 'O']]
2) An integer describing the current turn: 1 = X
, -1 = O
Output
An array made of:
- an array describing the best move in
[x, y]
format - the outcome of the game as an integer: 1 = win, -1 = loss, 0 = tie
Example
In the following example, X
is guaranteed to win by playing [1, 2]
.
let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))
console.log(JSON.stringify(f(
[['O','X','O'],
['-','-','-'],
['-','-','X']],
1
)));
A STRANGE GAME. THE ONLY WINNING MOVE IS NOT PLAY.
HOW ABOUT A NICE GAME OF CHESS?