18

1

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.

Sorry DJMCMayhem, I actually tried to tag those things but I couldn't, as I am new here. – Magic Octopus Urn – 2016-09-09T19:53:10.047

Bonus also removed, added nothing but tedium. – Magic Octopus Urn – 2016-09-09T21:16:17.383

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) – Ton Hospel – 2016-09-10T06:46:08.033

1In the 3x3 example,O should lose no matter what he plays, but you say output should be [2,1], why is that? – Dada – 2016-09-10T12:30:16.980

Edited, good catch. Don't know what I was thinking, that was the negative example. – Magic Octopus Urn – 2016-09-10T17:53:46.430

In the 2x2 example above [x,o][-,-] will win the one make the next move... So the result of evaluation routine must be 1 win... Or I understand wrong? – RosLuP – 2016-09-24T21:57:12.733

In a 4x4 board will win the one write first xxxx or oooo in columns row or diagonal? – RosLuP – 2016-09-25T16:49:58.147

Traditional tictacyoe rules, so yes. – Magic Octopus Urn – 2016-09-30T15:04:45.480