Output the correct move as per the XKCD tic-tac-toe cheetsheet!

Overview

This is the XKCD tic-tac-toe cheetsheet:

enter image description here

It's rather big, I know. But it's also your most valuable resource in your challenge.

The challenge

Create a program (in your language of choice) that uses the Optimal Move Cheatsheet (henceforth OMC) to output the optimal move when given a sequence of moves.

The input

Your program will be fed a series of moves in the following fashion:

A3 A2 B2 C2 ...

Where the first combination is always X, the second O, and so on. The letter is the Y coordinate (A-C, A at the top) and the number is the X coordinate (1-3, 1 at the left).

You may assume that the given combination is following the OMC's suggestion for each move at least for the player asking for a recommendation. You can also assume that the input will never be null (at least one move has been made). You must:

Figure out whether the next move is for X or O (you don't need to output this)
Use the OMC to decide the next move
Print the next move in the standard format A3

Optional:

You may also include the player's chance of winning (as a percentage) for 50 character discount on your score.

Undo

Posted 2013-12-16T03:52:52.750

Reputation: 413

– John Dvorak – 2013-12-16T04:54:55.253

1"The letter is the *Y* coordinate, and the number is the *Y* coordinate". Also, do we have to use that sheet, or can we use a different method for optimal moves? Also, your question is a bit confusing. How are we supposed to find the next move if it is already given for us? What is the "percentage chance" bit? Also, should this be tagged code-golf? – Justin – 2013-12-16T05:49:41.473

@Quincunx Ah! I forgot to fix the Y, Y thing in my edit, and now it would be a minor edit. I think, based on the premise of the question, alternate choices for optimal moves are not valid here. The "percentage chance" is probably the percentage of end-game scenarios from the current position (presuming the player takes the output move) in which the player can win. For example: A1, C3 should return A3 (100%). – Iszi – 2013-12-16T21:40:13.950

In fact, it appears that all scenarios should return 100% win chance for X except for those beginning A1, B2. – Iszi – 2013-12-16T21:41:52.380

Another example win percentage: A1, B2, C3, B3 should output A2 (80%) as there are five end-game scenarios from this position and four are wins for X. – Iszi – 2013-12-16T21:46:17.570

@Iszi I fixed the X/Y thing. Thanks! ;) – Undo – 2013-12-16T21:48:03.673

3Myself, I'd have made the positions simply 1 through 9. Top: 123, Middle: 456, Bottom: 789. But I'm not sure whether breaking the X/Y coordinates out might actually help things more than I think. – Iszi – 2013-12-16T21:52:10.813

Must we assume that the incoming list of moves is from the optimal list? What if the first move is B2, not A1? – None – 2013-12-17T00:38:05.410

@LegoStormtroopr You don't have to, but you can. – Undo – 2013-12-17T00:44:07.467

@LegoStormtroopr It is said already that the current player can be assumed to have followed the optimal path thus far. This means that any input where X is the current player will start with A1, but any input where O is the current player may start with anything. – Iszi – 2013-12-17T02:33:56.750

This is seriously making my brain hurt. I'm over 350 characters in PowerShell already, and that's just for A1 A2 and A1 A3 plus some empty top-level switches waiting to be filled in. There's got to be a better way to do this... especially for the O board! – Iszi – 2013-12-17T03:46:57.090

How does the move input vs what I'm supposed to output work? I'm seriously confused. It seems like you are inputting all of the moves, but I have to figure out the next one? But all the moves follow OMC, so what is the percentage thing? How do I know which person is asking for the recommendation? – Justin – 2013-12-17T07:21:02.120

2I'm not sure what's not clear here. Maybe we need to put this on hold while the bugs get worked out in the Sandbox? @Quincunx Only the moves of the current player are assumed to follow OMC. So, any input where X is next to move will start with A1. Any input where O is next to move will start with XY B2 (where XY is any of the possible first moves for X) except for B2 A1. Figuring out whose turn it is is simple. Just take the count of moves in the input, mod 2. Remainder of zero, it's X's turn - remainder of 1, it's O's. – Iszi – 2013-12-17T16:01:20.480

@Quincunx The "percentage" thing is, as I mentioned earlier, the percentage of remaining end-game scenarios in which the player requesting a move can win. You do not assume the opponent will follow the OMC, only the current player. – Iszi – 2013-12-17T16:02:58.487

@Undo Do we have to account for a null input - that is, X wants to know what their first move should be? Also, do we need to just figure out whose move it is, or should that be included in the output as well? – Iszi – 2013-12-17T17:13:09.427

@Iszi You don't need to account for null input (assume that at least one move has been made), and you don't need to show who's move you're solving for (we assume the player already knows that.) – Undo – 2013-12-17T17:18:29.757

@Undo s/a few moves/at least one move for clarity. Otherwise, "a few" is ambiguous and can lead to confusion. – Iszi – 2013-12-17T17:20:35.590

@Iszi Done, thanks. – Undo – 2013-12-17T17:22:05.713

As noted here there is at least one error in the image. At A1 A3 B1 C3, the picture for O moving on B2 is the same as B3. The recommendations are still valid, but the image representing the endgame scene for O moving on B2 are inaccurate. Anyone else got time to go through that with a fine-toothed comb and make sure we don't actually have some bad recommendations?

– Iszi – 2013-12-17T20:20:17.707

Found another bug in the chart. In X's section, after A1 B2 C3 A2 C2 all of the recommendations except for where O moves to C1 point to X moving on C2 (already done in the previous move). The end-game boards all correctly show a win with X going across the bottom, but the last move should be C1. – Iszi – 2013-12-18T23:48:25.473

I think I'm actually going to go ahead and join the VtC party on this one. Apparently, some people think the rules are a little un-clear and there also needs to be a thorough review of the chart so that errors can be addressed. Also, I think it really would be best if the squares would be labeled numerically (top row 123, middle 456, bottom 789). As it is, I've got 73 characters used up at the start of my current draft just to simplify the coordinates so they can be addressed with less characters later. I suggest working out the bugs in Sandbox and re-opening or re-posting this after edit. – Iszi – 2013-12-19T00:00:08.337

Please don't delete just yet, though - at least not until a copy is in the Sandbox. – Iszi – 2013-12-19T00:01:11.090