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).


  • 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



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)



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.

  • \$\begingroup\$ Sorry DJMCMayhem, I actually tried to tag those things but I couldn't, as I am new here. \$\endgroup\$ Sep 9, 2016 at 19:53
  • \$\begingroup\$ Bonus also removed, added nothing but tedium. \$\endgroup\$ Sep 9, 2016 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, 2016 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, 2016 at 12:30
  • \$\begingroup\$ Edited, good catch. Don't know what I was thinking, that was the negative example. \$\endgroup\$ Sep 10, 2016 at 17:53

2 Answers 2


Perl, 101 98 bytes

Includes +4 for -0p

Run with the input on STDIN


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


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)


#!/usr/bin/perl -0p

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
  • \$\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\$ Sep 10, 2016 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\$
    – user58988
    Sep 27, 2016 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, 2016 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\$
    – user58988
    Sep 27, 2016 at 12:51
  • \$\begingroup\$ It's been long enough, you win my man, sad we didn't get more attempts though. \$\endgroup\$ Sep 30, 2016 at 16:44

Javascript (ES6), 320 294 bytes



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


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


In the following example, X is guaranteed to win by playing [1, 2].

let f =



  • \$\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\$ Sep 10, 2016 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, 2016 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, 2016 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, 2016 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\$ Sep 10, 2016 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.