Play a Perfect Game of 4x4 Hex

Question

Background

Hex is a two-player abstract strategy game played on a K×K rhombus of hexagonal tiles. Two opposite sides of the rhombus are colored white, and the other two black, and the two players, black and white, take turns in placing a token of their color on an unoccupied tile. The player who first manages to construct a path between the opposite sides of their color is the winner. It is known that the game cannot end in a draw, and that the first player has a winning strategy regardless of the board size (see the Wikipedia page for details).

The Task

In this challenge, we fix the board size at K = 4, and represent the board as the following grid. The thick lines denote adjacent tiles.

Your task is to produce a winning strategy for the first player, which you can choose to be either black or white. This means that whichever legal moves the opposing player makes, your play must result in a victory. Your input is a game position (the arrangement of tokens on the board), and your output is a legal move, in the format specified below. If you want to find a winning strategy yourself, do not read this spoiler:

Outline of one possible winning strategy, assuming white goes first. First select 5. After that, if you have a path from 5 to the bottom row OR black selects 0 or 1 at any point, respond by selecting whichever of 0 or 1 is vacant. If black selects 9 or 13, select 10 and then whichever of 14 or 15 is vacant. If black does not select 9, 13 or 14, then select 9 and next whichever of 13 or 14 is vacant. If black selects 14, respond by selecting 15. Next, select 10 if it is vacant; if black selects 10, respond with 11. If black then selects 6, respond with 7, and next whichever of 2 or 3 is vacant. If black does not select 6, select it, so you have a path from 5 to the bottom row.

Input and Output

Your input is a string of 16 characters WBE, which stand for white, black and empty. They represent the tiles of the board, as enumerated above. You can choose the input method (which also determines your output method) from the following:

1. Input from STDIN, output to STDOUT.
2. Input as one command line argument, output to STDOUT.
3. Input as 16 single-character command line arguments, output to STDOUT.
4. Input as argument of named function, output as return value.

Your output represents the tile on which you place your next token, as it is your turn to move. You can choose from the following output formats:

1. A zero-based index (as used in the above picture).
2. A one-based index.
3. The input string with one E replaced by whichever of W or B you chose for your player.

Rules

Your strategy must be deterministic. You are not required to correctly handle game positions that are unreachable from the empty board using your strategy, or positions that are already winning for either player, and you may crash on them. Conversely, on boards that are reachable using your strategy, you must return a legal move.

This is code-golf, so the lowest byte count wins. Standard loopholes are disallowed.

Testing

I have written a Python 3 controller for validating entries, since it would be extremely tedious to do by hand. You can find it here. It supports the first three input formats and Python 3 functions (functions in other languages have to be wrapped into programs), all three output formats, and both players. If a strategy is not winning, it will output a losing game it found, so you can tweak your program.

Answer 1

Marbelous, 973b

This is a naive implementation of the hinted strategy in the question. It expects the board to be provided as 16 commandline/mainboard parameters like hex.mbl B W E E E W E E E B E E E E E E and it will output the zero-indexed position of white's next move.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

I think I can probably golf about 200 characters out of this with better branching and elimination of code re-use.

Answer 2

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

• Player: BLACK
• Method: STDIN / STDOUT, MODIFIED_BOARD

The strategy is to first search for a B on the board. If there is none this returns -1, which in python is the same as last index. Thus on an empty board my first index will be index=-1, which is where I start to move.

If the field to my left (index-1) is free, my next move goes there. If it is taken, I go up left. I never have to move up: if I do, I lose tempo and will lose the game.

On a full board (no E anywhere) I don't make a move.

The print seems a bit weird at first: I have to construct the new board (which I do via slicing) but then I need to cut out 16 characters. This is a relict since I work with negative indices and b[i+1:] will thus return the hole board and the rest I expect, making it important to cut off the remainder. Another way would have been to work with positive indices, e.g. by taking (b.find('B')+16)%16, but (+16)%16 is one byte more than ()[:16].

Ungolfed:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Test

When running the hex controller test suite, I encountered some strange behaviour:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

I think I either should have won after the 4th turn or answering with the same board to a full board should be a correct response. Not sure what goes wrong there, didn't dive much deeper - I just wanted to check if I got all "special" cases covered. But since I don't have to cover up situations where someone starts on space 4 or so, it doesn't matter anyway.

85b

However, if I allow myself to not check for a full board (i.e. leaving out the 'E' in b I can further simplify the code to only use 85 bytes:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

This will lead to the following though:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

This might or might not be counted, and since I found it wasn't a valid move I decided to go for the longer but more correct answer.