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:
- Input from STDIN, output to STDOUT.
- Input as one command line argument, output to STDOUT.
- Input as 16 single-character command line arguments, output to STDOUT.
- 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:
- A zero-based index (as used in the above picture).
- A one-based index.
- The input string with one
E
replaced by whichever ofW
orB
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.
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.
I should have won long ago, or am I wrong? \$\endgroup\$