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