Build a perfect AI for the game 15

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.