18
\$\begingroup\$

This challenge is to write a minimax function in a language of your choice, to output the next best move in an NxN game of tic-tac-toe given the current board state. The board input can be accepted as a Matrix, 2D Collection or anything else that makes sense to you, but adheres to the rules. The output being the next best move for whoever's turn it is currently, where X is considered to have started.

Quick Background on the Minimax Algorithm

The basic idea of the minimax algorithm is to enumerate all possible outcomes as a DAG then weight them by the benefit that the sequence of moves has to the player, keyed by the first move made. All possible outcomes are then 'bucketed' by the first move, and are scored based on the sum of all outcomes (-1 for a loss, 0 for a tie and a 1 for a win). In implementations that require multiple players to play, you enumerate all possible moves by the player, and all possible responses by the opponents as well. For instance, in a game of tic-tac-toe (after the first move) there are 8 possible first moves you can make, and they all may seem equal when only analyzing the next turn. But by iterating through all possible outcomes for each possible set of moves that results in a final outcome and summing them all up, we can get a score for our next move, and have a basis for our choices.

For a better, more in-depth and contextual summary of the mini-max algorithm in terms of tic-tac-toe, read more here: http://neverstopbuilding.com/minimax

XKCD (3x3 Solution Only)

All possible moves for a 3x3 game of tic-tac-toe.

The Rules

  • Any language can be used, but no external minimax libraries are allowed.
  • Output can be a coordinate (0-n,0-n) or a number (1-n*n) indicative of the best next move.
    • In addition to this, you must be able to identify when the best case scenario is a loss or a tie instead of a win.
    • The way you denote a loss or a tie is, once again, up to you.
  • Input must use the traditional X and O, and you must assume X moves first; blank spaces can be represented by anything.
  • You may assume any inputs coming into your program have n O's and n+1 X's, in other words you may assume you're getting a well-formed board.
  • The current state of the board must be the only input to your program, if you are using recursion, helper methods must be made to facilitate the input requirements. See https://codegolf.stackexchange.com/a/92851/59376 for clarification.
  • Any value of 10 >= n >= 1 must be supported; if your program "times out" for n > 10, I find this acceptable as well, as some languages have significantly lower processing power (Especially using web-facing consoles).

Judging

  • This is code-golf, so the lowest byte-count of the program wins and standard loopholes are universally disallowed.
  • In the case of a tie, the program that supports the largest 'n' will win.

Example Inputs

2x2

[[X,O]
 [-,-]]

Output: 2 or [0,1] (3 or [1,1] would also be arguably correct) (Some form of indication of the location, arbitrary as long as you can easily explain the format you used)


3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Output: -1 (Loss)


Once again any input format you want is allowed, but X's and O's must be used, the examples provided were not meant to constrain to that format, just to inspire.

\$\endgroup\$
  • \$\begingroup\$ Sorry DJMCMayhem, I actually tried to tag those things but I couldn't, as I am new here. \$\endgroup\$ – Magic Octopus Urn Sep 9 '16 at 19:53
  • \$\begingroup\$ Bonus also removed, added nothing but tedium. \$\endgroup\$ – Magic Octopus Urn Sep 9 '16 at 21:16
  • \$\begingroup\$ Is the following output format allowed: a diagram of the board position with on each originally empty space a unique character indicating if playing there leads to a win/loss/draw (e.g W, L and D) \$\endgroup\$ – Ton Hospel Sep 10 '16 at 6:46
  • 1
    \$\begingroup\$ In the 3x3 example,O should lose no matter what he plays, but you say output should be [2,1], why is that? \$\endgroup\$ – Dada Sep 10 '16 at 12:30
  • \$\begingroup\$ Edited, good catch. Don't know what I was thinking, that was the negative example. \$\endgroup\$ – Magic Octopus Urn Sep 10 '16 at 17:53
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Wow, overlooking that it's pl and likely would absolutely not run for n=10 with lots of empties... You did both of the things i was hoping to see someone do. A string input and mapping the outcome for all moves, not just the best. Bravo. \$\endgroup\$ – Magic Octopus Urn Sep 10 '16 at 23:51
  • \$\begingroup\$ If one recursive function 'leak' how can be ok??? Too high language make not see the 32 bit register in the CPU (or something as that the simple instruction) \$\endgroup\$ – RosLuP Sep 27 '16 at 9:35
  • \$\begingroup\$ @RosLup Leak in this context doesn't necessarily mean unreachable lost memory. Perl is rather peculiar in when it releases memory, quite often doing this later than you would expect and so using a lot more memory than you would expect. It also tends to allocate more than directly needed in the expectance that you will grow your datastructures. In this case using "normal" recursion with a function instead of the abuse of do$0 would use 10 times less memory. Mind you, this case is so extreme it might actually be a real memory leak. \$\endgroup\$ – Ton Hospel Sep 27 '16 at 11:39
  • \$\begingroup\$ Not only one not see the registers or the base instructions (from the hlls instructions) but lose the control of memory use... For me they not scale... \$\endgroup\$ – RosLuP Sep 27 '16 at 12:51
  • \$\begingroup\$ It's been long enough, you win my man, sad we didn't get more attempts though. \$\endgroup\$ – Magic Octopus Urn Sep 30 '16 at 16:44
2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Well done, good first entry. Only remarks I have are the potential to save bytes with the given information 'X will always move first'. And have you tried with a non 3x3 board ;)? \$\endgroup\$ – Magic Octopus Urn Sep 10 '16 at 2:31
  • \$\begingroup\$ @carusocomputing - Not sure to understand what you have in mind with 'X will always move first'. It could be used to deduce which side is on move given the board alone, but computing that would actually cost more bytes; so I guess you're talking about something else. Ans yes, I did some tests with slightly bigger boards. That should work as expected as long as ... err ... there aren't too many empty positions. :-) \$\endgroup\$ – Arnauld Sep 10 '16 at 11:57
  • \$\begingroup\$ The challenge says The current state of the board must be the only input to your program. Your code needs two inputs, which breaks this rule. \$\endgroup\$ – Dada Sep 10 '16 at 12:42
  • 1
    \$\begingroup\$ @Dada - I was wondering about that, but I assumed the active color is part of the state of the board (just like a chess position always comes with active color + en passant square + castling availability). So I guess the OP should clarify that point. (And if you're right, that sounds like an unnecessary additional difficulty, IMHO.) \$\endgroup\$ – Arnauld Sep 10 '16 at 14:06
  • 1
    \$\begingroup\$ Mmm.. i really like the explanation of board state in his response. Thinking on it, some lanagues may only use strings as input, having a board like XXOOXO-OO would be hard to decipher in low byte counts without additional information like board dimensions. Ill allow any additional inputs that contribute to board state, though I still think the information 'assume X moves first' is different than 'given whos turn it is'. Some languages will take advantage of that as an assumption ;). \$\endgroup\$ – Magic Octopus Urn Sep 10 '16 at 17:18

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.