Build a perfect AI for the game 15

8

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

Joe Z.

Posted 2013-08-04T23:19:19.900

Reputation: 30 589

Do I understand correctly we are allowed to lose if we get into a winnable position that our AI couldn't have got into? – John Dvorak – 2013-08-05T01:50:23.153

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. – Joe Z. – 2013-08-05T03:17:24.213

do I assume correctly the AI is always the first to play? – John Dvorak – 2013-08-05T04:07:44.663

No, the AI can play second as well, but either way the game is solved (with perfect play, the game will always end in a tie). – Joe Z. – 2013-08-05T04:12:08.050

1hmm... it seems we are allowed to draw even if we can force a win. Is that true? – John Dvorak – 2013-08-05T06:34:01.013

Well, I guess it should win if given the opportunity. – Joe Z. – 2013-08-05T13:50:43.660

well, mine does :-) – John Dvorak – 2013-08-05T13:57:55.880

I should clarify: "the AI should never allow the game to get into said losing state from an empty board" or from any other non-losing position. – Joe Z. – 2013-08-06T04:30:24.753

"Do I understand correctly we are allowed to lose if we get into a winnable position that our AI couldn't have got into?" – Jan Dvorak yesterday "Yes, that is correct. ..." – Joe Z. yesterday – John Dvorak – 2013-08-06T04:52:13.897

I think I misunderstood your question then. What I meant is, if the AI is presented initially with a position that's "winnable" from the other side, it's allowed to lose because the other side has a winning strategy and there's absolutely nothing the AI can do. Otherwise the AI must prevent a loss if possible, including taking full advantage of the other player screwing up a winning position by making a wrong move. – Joe Z. – 2013-08-06T14:36:09.493

what is the intention of the word "initially" in that statement? I will update my answer, however – John Dvorak – 2013-08-06T14:44:25.830

If the AI is given a garbage input like [6 7 9][1 2 4 8] (in which case 3 and 5 is a double trap) without having made any moves itself (but just having [6 7 9][1 2 4 8] as a starting position), that's considered an "initial losing position". Then it's allowed to make a losing move because it has no other choice. But from an empty board, the AI should never allow [6 7 9][1 2 4 8] to be reached. – Joe Z. – 2013-08-07T02:12:56.483

2Hah. 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. – boothby – 2013-11-24T07:02:53.483

Answers

6

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

Peter Taylor

Posted 2013-08-04T23:19:19.900

Reputation: 41 901

Can you run this input through for me: [5][3] (should return either 4 or 8). – Joe Z. – 2013-08-07T02:14:26.833

9 - but then you seem to have changed the rules. – Peter Taylor – 2013-08-07T07:22:53.870

Also, why only 4 or 8? – Peter Taylor – 2013-08-07T07:41:35.247

Oh wait, never mind, I was wrong. Anything except for 7 should work, so 9 is acceptable. – Joe Z. – 2013-08-07T11:51:19.537

Also, I didn't mean to change the rules; it's just that I'd phrased them wrong the first time around. – Joe Z. – 2013-08-07T11:51:37.990

@JoeZ., including a good set of test cases is a good way to ensure that if you misphrase something it gets picked up early. – Peter Taylor – 2013-08-07T11:53:09.730

Alright, I'll include the test suite that I personally use as a strategy for 15. – Joe Z. – 2013-08-07T12:14:39.273

4

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.

John Dvorak

Posted 2013-08-04T23:19:19.900

Reputation: 9 048

Looks like you have an easy saving in the last three lines by simply moving 5 to the start of your preference order. – Peter Taylor – 2013-08-05T14:32:36.377

@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). – John Dvorak – 2013-08-05T14:47:42.960

1

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.

Peter Taylor

Posted 2013-08-04T23:19:19.900

Reputation: 41 901