What's your next move?

Question

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)

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.

Answer 1

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

Answer 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?}