Build a perfect AI for the game 15

In the game 15, two players take turns selecting numbers from 1 to 9 (without choosing any number that either player has already selected). A player wins if he or she has three numbers that add up to 15. If all the numbers have been selected and no combination of either player's adds up to 15, then the game is a tie.

Your task is to build a function that takes the state of a game of 15 (represented in any form you like) and returns which number to move next, which will act as an AI to play the game with another player. You may assume that the position is legal (no player has more than one number more than the other player, and no player already has three numbers that add up to 15).

The AI must be perfect - that is, if it's given a winning position, it must force a win, and if it's given a non-losing position (a position where its opponent does not have a winning strategy), it must not allow its opponent to give it a losing position (which is possible, as 15 is a solved game).

The shortest code wins.

(note: I will accept the currently shortest answer and change it if a shorter answer appears.)

• Do I understand correctly we are allowed to lose if we get into a winnable position that our AI couldn't have got into? Aug 5, 2013 at 1:50
• Yes, that is correct. If the AI is presented with a game state that it cannot win or tie (e.g. a double trap), then it is allowed to lose. However, the AI should never allow the game to get into said losing state from an empty board. Aug 5, 2013 at 3:17
• do I assume correctly the AI is always the first to play? Aug 5, 2013 at 4:07
• hmm... it seems we are allowed to draw even if we can force a win. Is that true? Aug 5, 2013 at 6:34
• Hah. I just learned about this game, and the first thing when I got home was to post it here. Alas, I've been beaten to it. Nov 24, 2013 at 7:02

GolfScript (129 86 81 85 75 chars)

{:C[{.{1$-\{+15\-}+%}:T+/}/10,1>C~+-:^{.{^T&}+C/,2<*T}/5^{1&}$][]*^&0=}:N;


Expected input format: [[int int ...][int int ...]] where the first list is my numbers and the second list is my opponent's numbers. For interactive testing, add ~N to the end of the script and supply a string in that format: e.g.

$golfscript.rb 15.gs <<<"[[5][2 8]]" 9$ golfscript.rb 15.gs <<<"[[2][5 8]]"
6


Heuristics:

1. If I can win this turn, do it
2. If opponent would win next turn, block
3. If I can force opponent to a square which prevents them from creating a fork, do it
4. 5 is the only number which can contribute to winning in 4 ways, so grab it if available.
5. Favour evens over odds

Test framework:

{:Set;[1 5 9 1 6 8 2 4 9 2 5 8 2 6 7 3 4 8 3 5 7 4 5 6]3/{.Set&=},!!}:isWin;
{
# Mine His
.isWin{
"Lost "@@++puts
}{
# If there are available moves, it's my move.
# If I won before my move, I've still won after it.
1$1$+,9<!!{
# my move
1$1$[\\]N 2$\+ # Mine His Mine' .isWin!{ # his move 10,1>2$2$+-{ 2$\+1$\ # Mine His Mine' Mine' His' fullTest # Mine His Mine' }/ }*; }*;; }if }:fullTest; # I move first '[][]fullTest'puts [][]fullTest # He moves first '[][1]fullTest'puts [][1]fullTest '[][2]fullTest'puts [][2]fullTest '[][5]fullTest'puts [][5]fullTest  • Can you run this input through for me: [5][3] (should return either 4 or 8). Aug 7, 2013 at 2:14 • 9 - but then you seem to have changed the rules. Aug 7, 2013 at 7:22 • Also, why only 4 or 8? Aug 7, 2013 at 7:41 • Oh wait, never mind, I was wrong. Anything except for 7 should work, so 9 is acceptable. Aug 7, 2013 at 11:51 • Also, I didn't mean to change the rules; it's just that I'd phrased them wrong the first time around. Aug 7, 2013 at 11:51 Ruby, 330 315 341 characters def m i$_=i.join
l='159258357456168249267348'.scan /(.)(.)(.)/
return 1 if /^5(28|46|64|82)$/ return 4 if /^[258]{3}$/
return 2 if /^[456]{3}$/ i.each{|i|l.map{|l|return l if(l-=i).size==1&&!/[#{l=l[0]}]/}} .map{|i|l.map{|m|l.map{|l|return (l&m)[0] if(z=l-i|m-i).size==3&&l!=m&&!/[#{z.join}]/}}} "524681379".chars{|z|return z if !/#{z}/} end  I'll withhold the details for now, but let's say that it is based on the optimal algorithm to a similar problem that has been solved as well and whose optimal algorithm happened to work just as fine here. Assumptions have been made - this will choose bad moves in situations that cannot be produced by this algorithm playing against another player, only by two players against each other. Input: an array of two arrays of one-digit strings. Each array represents the values taken by one player - the first one is the AI, the second one is the opponent. Output: either a number, or a single-digit string. They are semantically equivalent. Normalisation to strings would cost 8 characters. Three more characters can be saved if we assume the order of numbers given by the caller - change the regex in L5 to /^285$/ or /^258$/ depending on the order produced from the game (opponent)5-(ai)2-(opponent)8. • Looks like you have an easy saving in the last three lines by simply moving 5 to the start of your preference order. Aug 5, 2013 at 14:32 • @ah, yes, thanks. I had another step in between that I removed (special-cased to the top) and I forgot to merge the surrounding steps. I'll edit when I get home (unless you volunteer to before). Aug 5, 2013 at 14:47 GolfScript (90 85 84 chars) {.~.,3/*..2%.@^++3*3/{~++15=},,*10,1>2$~+-@{([2$+]+v[0=~)\]}+%[1,]or$0=+}:v{1=}+:N;


This takes a completely different approach, but is potentially susceptible to optimisations to beat the heuristic one. Here we do a full game tree analysis, incredibly slowly. (No, I mean it. It takes several hours to run the full test, mainly because of the {...}+ which adds the current state to the next-move loop). Note that the hard part is identifying a winning state (a third of the code, at present).

There are some ugly hacks in the non-recursive sections. In particular, when the position is identified as a losing one we take our positions as the [value move]` array, relying on the move being irrelevant and the value being non-zero.