What's your next move?

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)

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.

Magic Octopus Urn

Posted 2016-09-09T16:52:35.220

Reputation: 19 422

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

Answers

8

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

Ton Hospel

Posted 2016-09-09T16:52:35.220

Reputation: 14 114

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. – Magic Octopus Urn – 2016-09-10T23:51:25.140

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) – RosLuP – 2016-09-27T09:35:02.317

@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. – Ton Hospel – 2016-09-27T11:39:42.477

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... – RosLuP – 2016-09-27T12:51:44.483

It's been long enough, you win my man, sad we didn't get more attempts though. – Magic Octopus Urn – 2016-09-30T16:44:19.750

Thank you... Good explanation in how represent result, I understand that better than minimax function theory... My code after some days in debugging is in assembly it is too much long for this place – RosLuP – 2016-10-05T11:14:44.307

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?

Arnauld

Posted 2016-09-09T16:52:35.220

Reputation: 111 334

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 ;)? – Magic Octopus Urn – 2016-09-10T02:31:28.997

@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. :-) – Arnauld – 2016-09-10T11:57:06.487

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. – Dada – 2016-09-10T12:42:32.967

1@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.) – Arnauld – 2016-09-10T14:06:20.507

1Mmm.. 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 ;). – Magic Octopus Urn – 2016-09-10T17:18:49.927

The input would be 1) the board 2) who is the next to move – RosLuP – 2016-09-24T22:01:32.120

The input can just one string of nxn dimension of X <space> or O; if the length is not nxn => error; if there is already a tris, error; if number of X - Number of O==0 move X, if number of X - number of O==1 move O; otherwise error... – RosLuP – 2016-10-05T12:33:38.823