Can you win with two more moves at Three Men's Morris? Bounties

No. 1 (awarded)


  I'll throw in 50 rep for the first valid answer


No. 2 (awarded)


  I'll throw in another 100 rep for the shortest valid answer.


No. 3 (open for submissions)


  I'll throw in 200 rep for the first one with a significant shorter valid answer.
  Significant being at most 45% of currently shortest answer (564 bytes x 0.45 = max 254 bytes).




The Game

You remember the classic game "Nine Men's Morris" or simply "Mill"? There's a variation called Three Men's Morris which is a bit like a mutable tic-tac-toe.

Rules

This is the blank board of the game:

   a   b   c
1 [ ]–[ ]–[ ]
   | \ | / |
2 [ ]–[ ]–[ ]
   | / | \ |
3 [ ]–[ ]–[ ]


[ ] is a field and |–/\ represent routes between those fields.

The game is played by two players 1 and 2 who each place 3 tokens on the board. This actually happened already and we are in the game. The game is won if one player can form a mill which is a vertical or horizontal row of the player's 3 tokens.

Tokens can be moved on the board along the connecting lines, according to this rule:


  To any adjacent empty position (i.e. from an edge position to the center, or from the center to an edge position, or from an edge position to an adjacent edge position


A player must make a move unless there's no adjacent empty position, in which case the move is skipped.

The Challenge

You're player 1 and your move is next. Write a program or a function, that determines whether:


you can force a win with 2 or less moves (definite win)
you can win with 2 or less moves, if your opponent makes a mistake (possible win)
you cannot win with 2 or less moves, because you'll need more moves or because forced moves lead your opponent to win (impossible to win)


Requirements


Even though you definitely win when you bore your opponent to death, your program must finish in finite time.
You can write a program or a function.


Input

The players are represented by 1 and 2. 0 defines a free field. You can take input as a matrix or an array.

Definite

A         B         C         D
2 1 0  |  2 1 0  |  1 0 1  |  1 2 2
2 1 2  |  0 1 0  |  1 0 2  |  2 1 O
0 0 1  |  2 2 1  |  0 2 2  |  O O 1

A: [2,1,0,2,1,2,0,0,1]
B: [2,1,0,0,1,0,2,2,1]
C: [1,0,1,1,0,2,0,2,2]
D: [1,2,2,2,1,0,0,0,1]


Possible

A         B         C
1 0 1  |  1 0 1  |  1 2 2
1 2 2  |  1 2 0  |  0 0 1
2 0 0  |  2 0 2  |  2 1 0

A: [1,0,1,1,2,2,2,0,0]
B: [1,0,1,1,2,0,2,0,2]
C: [1,2,2,0,0,1,2,1,0]


Impossible

A         B    
1 0 0  |  1 2 0
1 2 2  |  2 1 0
2 0 1  |  1 2 0

A: [1,0,0,1,2,2,2,0,1]
B: [1,2,0,2,1,0,1,2,0]


Output

Your program should output/return a smiley:


Definite win: :)
Possible win: :|
Impossible to win: :(


Examples

Definite win in two moves:

[2][1][ ] 1. [2][1][ ]
[2][1][2] -&gt; [2][1][2]
[ ][ ][1]    [ ][1][ ]

[2][1][ ] 1. [2][1][ ]    [ ][1][ ] 2. [ ][ ][1]
[ ][1][ ] -&gt; [ ][ ][1] -&gt; [2][ ][1] -&gt; [2][ ][1]
[2][2][1]    [2][2][1]    [2][2][1]    [2][2][1]

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][ ][2] -&gt; [1][ ][2] -&gt; [1][ ][2] -&gt; [ ][ ][2]
[ ][2][2]    [ ][2][2]    [2][ ][2]    [2][ ][2]


Possible win in two moves:

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][2][ ] -&gt; [1][2][ ] -&gt; [1][2][2] -&gt; [ ][2][2]
[2][ ][2]    [2][ ][2]    [2][ ][ ]    [2][ ][ ]

[1][ ][1] 1. [ ][1][1]    [ ][1][1] 2. [1][1][1]
[1][2][ ] -&gt; [1][2][ ] -&gt; [1][2][2] -&gt; [ ][2][2]
[2][ ][2]    [2][ ][2]    [2][ ][ ]    [2][ ][ ]

[1][2][2] 1. [ ][2][2]    [2][ ][2] 2. [1][2][2]
[ ][ ][1] -&gt; [1][ ][1] -&gt; [1][ ][1] -&gt; [1][1][1]
[2][1][ ]    [2][1][ ]    [2][1][ ]    [2][ ][ ]


Impossible to win in two moves:

[1][ ][ ]
[1][2][2]
[2][ ][1]


Bonus

In case a definite win is possible and your program outputs the moves of one way to success as well like a1:a2 (1 move) or a1:a2,a3:b2 (2 moves), you can withdraw 30% of your byte count.



This is code golf – so shortest answer in bytes wins. Standard loopholes are disallowed.



Thanks to Peter Taylor who fixed some flaws and improved wording in the Sandbox.
C# - 739 663 bytes

Complete program, reads input from argv, and appears to work. Run it like

ThreeMill 1 2 1 1 2 0 0 0 2


If this method of input is unacceptable, I'll be glad to change it (never like using argv).



using System;using System.Linq;class P{static void Main(string[]A){var I=new[]{0,3,6,1,4,7,2,5,8};Func&lt;string[],string&gt;J=S=&gt;S[0]+S[1]+S[2]+" "+S[3]+S[4]+S[5]+" "+S[6]+S[7]+S[8]+" ";Func&lt;string[],string,int&gt;W=(B,p)=&gt;(J(B)+J(I.Select(i=&gt;B[i]).ToArray())).Contains(p+p+p)?1:0;Func&lt;string[],string,string[][]&gt;V=(B,p)=&gt;I.SelectMany(a=&gt;I.Where(b=&gt;a!=b&amp;B[a]==p&amp;B[b]=="0"&amp;(a==4|b==4|a-b==3|b-a==3|((a-b==1|b-a==1)&amp;a/3==b/3))).Select(b=&gt;{var N=(string[])B.Clone();N[b]=p;N[a]="0";return N;})).DefaultIfEmpty(B).ToArray();int h,G;Console.WriteLine(":"+"(|))"[V(A,"1").Max(z=&gt;((h=0)&lt;(G=V(z,"2").Sum(j=&gt;V(j,"1").Max(q=&gt;W(q,"1")-W(q,"2"))+h++*0))?1:0)+(h&gt;G?W(z,"1")*2:2))]);}}


I was disinclined to post this yesterday, because I've not been able to golf it down much (not had all that much time, and I might be out of practice), but since there hasn't been a response yet, I'll post it anyway, I certainly don't expect the bounty, I'd rather it went to someone who's put a bit more effort into theirs before posting!

Edit: replaced all the bools with ints, which meant I could make better use of Linq, and managed to collapse both foreach loops, giving big savings. I am slightly amazed that the h counter works... ++ is such a subtle utility.

The program is very simple, it just explores every possible set of moves (stores board state in a string[]). It iterates over all of our possible moves (the boards that result thereof), and counts the number of responses by our opponent that we can successful beat (G) (i.e. those that we win, and he doesn't). It also counts the number of possible responses (h). If we can win any, then it's a possible, and we add 1 to the sum, if we can win them all, it's a definite, and we add 2 to the sum. The maximum some is therefore our best possible outcome, and we index into the string "(|))" to return the appropriate face. Note that we need the extra ")" because the sum can be 2 or 3 if it's a definite (it's possible that we don't appear to be able to beat any responses having already won on the first go, so the possible check is a tad misleading).

The program checks for a victory by producing a string from the board, that is space-separated rows and columns, and just looks for a string of 3 of the player's character in this string (e.g. "201 201 021 220 002 111 " is a win for us)

using System;
using System.Linq; // all important

class P
{
    static void Main(string[]A) // transform to int?
    {
        var I=new[]{0,3,6,1,4,7,2,5,8}; // vertical indexes
        Func&lt;string[],string&gt;J=S=&gt;S[0]+S[1]+S[2]+" "+S[3]+S[4]+S[5]+" "+S[6]+S[7]+S[8]+" "; // joins the strings up, so that there is a space separating each group of three (including at end)
        Func&lt;string[],string,int&gt;W=(B,p)=&gt;(J(B)+J(I.Select(i=&gt;B[i]).ToArray())).Contains(p+p+p)?1:0; // checks if a particular player wins
        Func&lt;string[],string,string[][]&gt;V=(B,p)=&gt;I.SelectMany(a=&gt;I // for each imagineable move
            .Where(b=&gt;a!=b&amp;B[a]==p&amp;B[b]=="0"&amp;(a==4|b==4|a-b==3|b-a==3|((a-b==1|b-a==1)&amp;a/3==b/3))) // where it's legal
            .Select(b=&gt;{var N=(string[])B.Clone();N[b]=p;N[a]="0";return N;}) // select the resulting board
        ).DefaultIfEmpty(B) // allow not-moving
        .ToArray();

        int h, // h stores the number of responses the opponent has to each move
        G; // G stores the number of responses by the opponent we can beat

        Console.WriteLine(":"+"(|))"[ // we index into this to decide which smiley
            V(A,"1").Max(z=&gt;
                    ((h=0)&lt;(G=V(z,"2").Sum(j=&gt;V(j,"1").Max(q=&gt;W(q,"1")-W(q,"2"))+h++*0))?1:0) // if there is atleast 1 reponse by the opponent we can beat, we can possibly win
                    +(h&gt;G?W(z,"1")*2:2) // if there are moves which we can't win, then if we have already won (one-move), else, we can definitely win
                   ) // sum is therefore 0 if impossible, 1 if possible, &gt;2 (no more than 3) if definite 
            ]);

    }
}


Here is my test script:

ThreeMill 2 1 0 2 1 2 0 0 1
ThreeMill 2 1 0 0 1 0 2 2 1
ThreeMill 1 0 1 1 0 2 0 2 2
ThreeMill 1 2 2 2 1 0 0 0 1

ThreeMill 1 0 1 1 2 2 2 0 0
ThreeMill 1 0 1 1 2 0 2 0 2
ThreeMill 1 2 2 0 0 1 2 1 0

ThreeMill 1 0 0 1 2 2 2 0 1
ThreeMill 1 2 1 1 2 0 0 0 2
ThreeMill 1 0 1 2 0 2 1 0 2


Which outputs

:)
:)
:)
:)
:|
:|
:|
:(
:|
:)