10
\$\begingroup\$

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.

A 4x4 grid.

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.

\$\endgroup\$
4
  • \$\begingroup\$ This challenge reminds me of trying to compress a tic tac toe AI when I was writing calculator programs. ticalc.org/archives/files/fileinfo/354/35408.html \$\endgroup\$
    – Sparr
    Jun 26, 2015 at 17:26
  • 2
    \$\begingroup\$ Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'. I should have won long ago, or am I wrong? \$\endgroup\$ Jun 27, 2015 at 11:11
  • \$\begingroup\$ @SebastianHöffner That looks like a bug in the controller. I'll try to fix it when I have time. \$\endgroup\$
    – Zgarb
    Jun 29, 2015 at 18:16
  • \$\begingroup\$ @SebastianHöffner The bug should now be fixed. \$\endgroup\$
    – Zgarb
    Jun 30, 2015 at 12:53

1 Answer 1

6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I added the option for 16 command line argument and updated the verifier script, so this solution can be tested. \$\endgroup\$
    – Zgarb
    Jun 27, 2015 at 9:53
  • \$\begingroup\$ Marbelous +1 (PPCG thinks adding these characters improved the comment) \$\endgroup\$ Aug 3, 2016 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.