Simulate a Game of Quagmire

Question

Background

Many moons ago, in a galaxy much like our own, a young BrainSteel attempted to invent a board game. He believed that he, too, could find an amazingly simple set of rules that would generate wonderfully strategic gameplay. He drew up the first set of rules--it looked promising. He played with his thoughts, and noticed a minor inconsistency here, or a slight balance issue there. One by one, the rules started piling up, until they were at best arbitrary. Try as he might, the beautiful simplicity of Checkers or Go failed to shine through. His final creation, one bad enough he would only refer to it when speaking in the 3rd person, was given the temporary name "Quagmire." While perhaps not a brilliant board game, it ought to be a fun code golf!

The Rules of Quagmire

The game is played on an 8x8 board, and each player has 10 identical pieces. If player one has O pieces, and player 2 has X pieces, here is a portrayal of the game at the start (where . indicates a blank space):

 a b c d e f g h
+-+-+-+-+-+-+-+-+
|.|.|.|.|X|X|X|X| 8
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|X|X|X| 7
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|.|X|X| 6
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|.|.|X| 5
+-+-+-+-+-+-+-+-+
|O|.|.|.|.|.|.|.| 4
+-+-+-+-+-+-+-+-+
|O|O|.|.|.|.|.|.| 3
+-+-+-+-+-+-+-+-+
|O|O|O|.|.|.|.|.| 2
+-+-+-+-+-+-+-+-+
|O|O|O|O|.|.|.|.| 1
+-+-+-+-+-+-+-+-+

Note that every space on the grid can be named with a letter and number, e.g. there is an O character on c2.

Players take turns in an alternating fashion.

On a player's turn, they may move in two ways:

• The player may move any piece in a straight line vertically, horizontally, or diagonally at most until they meet either another wall or piece. e.g. |X|.|.|O|.| => |.|.|X|O|.| for one move of length 2 horizontally. Note that the X piece cannot move any farther right, because there is a piece in the way.

• The player may use a piece to jump over a single, adjacent, and friendly piece. Jumps, like ordinary moves, may be horizontal, vertical, or diagonal. Under normal circumstances an enemy piece may not be jumped. e.g. |X|X|.| => |.|X|X|

If a piece cannot move to any of its surrounding spaces, and at least one of those adjacent spaces is occupied by an enemy piece, that piece is said to be in a state of Quagmire. If a player ends his turn with a piece in Quagmire, they lose the game.

Now for the more arbitrary rules:

• The bottom left player goes first.

• Each player must make exactly one move per turn. (No pass!)

• A piece may not be moved twice in a row, ever. e.g. if, on the first turn, player one moves the piece on c2, he may not move the same piece on his following turn.

• If the player to move has one or more pieces in Quagmire which may move, they must move one of those pieces.

• A piece may jump an enemy piece in the same way that it jumps a friendly piece if and only if that enemy piece is part of a closed loop (which may or may not start and end at a wall) of pieces of one color, and that loop is impenetrable by normal moves. If a piece jumps in this way, it must jump from inside the loop to the outside, or vice versa. Since this rule is weird, here is an example board:

  
     a b c d e f g h
    +-+-+-+-+-+-+-+-+
    |.|.|.|O|X|.|.|X| 8
    +-+-+-+-+-+-+-+-+
    |.|.|.|.|X|.|.|X| 7
    +-+-+-+-+-+-+-+-+
    |.|.|.|.|X|.|.|.| 6
    +-+-+-+-+-+-+-+-+
    |X|.|.|.|.|X|X|X| 5
    +-+-+-+-+-+-+-+-+
    |O|O|O|O|.|.|.|.| 4
    +-+-+-+-+-+-+-+-+
    |.|.|.|O|X|.|.|.| 3
    +-+-+-+-+-+-+-+-+
    |.|.|.|O|.|.|O|.| 2
    +-+-+-+-+-+-+-+-+
    |O|O|O|O|.|.|.|.| 1
    +-+-+-+-+-+-+-+-+

In this position, the X on a5 may legally jump to a3. In contrast, the O on d8 may NOT jump to f8, since the loop of X pieces is not fully closed -- the inside is accessible through the e5 - g7 diagonal. Also, note that the 'X' on e3 may not jump to c5 because this jump does not cross from outside the loop to the inside.

The Challenge

Your challenge is to allow two players at the same computer to play a game of Quagmire, adhering perfectly to the rules, against each other.

At every point in the game, your program should output the board as shown in the first example board, reflecting the current positions of all pieces on the board. You may choose any characters for the O, X, and . values, but the rest of the characters must be exactly as shown. You should also display, in a reasonable manner, whose turn it is!

Input

On a players' turn, you should accept a string of at least 5 bytes in the form X#<seperator>Y#. You may make reasonable adjustment to this format to suit your programming language. You may also assume that the input, while not necessarily a legal move, will be formatted correctly (no numbers greater than 8, etc). Your program should evaluate whether or not a move from X# on the board to Y# is legal for this player. If it is legal, your program should make the move and output the next board accordingly. If it is not legal, your program should output some falsy value (0 is perfectly reasonable--you do not need an explanation) and receive another input.

Winning

A player wins when the other player fails to relieve one of his pieces from Quagmire. Alternatively, a player wins when it is their opponent's turn and their opponent has no legal moves. Note that the first win condition takes precedence over the second. If I leave a piece in Quagmire at the end of the turn and simultaneously leave my opponent with no legal moves, I still lose the game. If the game is over after a player's move, you should output the winning board, the winning player's piece character (e.g. 'X') and some truthy value (Again, 1 is sufficient). At this point, your program may either terminate or restart the game.

Challenge Rules

• This is code-golf. Smallest code, in bytes, wins.

• Standard loopholes are disallowed.

Answer 1

Ruby 2.7, ^695...618 610 bytes

i=*0..7
t,*b={}
"?>=<765/.'".bytes{b[_1],b[~_1]=A=?X,E=?O}
loop{puts'
 '+[*?a..?h]*' ',a='+-'*8+?+,i.map{|j|"|#{b[8*~j,8].map{_1||?.}*?|}| #{8-j}
"+a}
eval"M,*m=->u,w=p,*s{Q=(0..8).map{c,r=u;z=c+8*r
#{$f='(v=c+=_1/3-1,r+=_1%3-1)-i==[]&&'}(k=#{$g='b[c+8*r]'}
w ?b[z]==A&&(t[A]!=z&&(#$f!#$g&&(k==A||k&&N[u]&N[v]==[])&&s<<u+v
c,r=u;s<<u+v while#$f!#$g);k):k!=E&&s<<v)};s}
N,*q=->o,n=M[o]{n==n|=n.flat_map{M[_1]}||redo;n}
i.product(i){#{h='M[_1,1];A,E=E,A;([p,A]&Q)[0]&&'}(p A;Z);m+=e=#{h}q+=e}
A,E=E,A
($><<A+?>;c,r,_,x,y=gets.bytes.map{~-_1%8})until[[c,r,x,y]]-(m[0]?q[0]?q:m:(p E;Z))==[]
#$g,b[t[A]=x+8*y]=p,A"}

Try it online! (620 bytes because the older Ruby on TIO doesn't support numbered block parameters.) A simple example game is included that illustrates most of Quagmire's rules. Just for clarity, the input is commented and invalid moves are indented.

Input is in the format x# y#, terminated either by newline or EOF. Any single byte is accepted as the separator. The input prompt is O> for player 1 and X> for player 2. (In an interactive terminal the input appears as it is typed, after the prompt.) The prompt is repeated until a valid move is entered, then the updated board is printed. When the game ends, the winning player's symbol is printed in double quotes; I like to imagine it is raising its arms in victory.

Explanation

While perhaps not a brilliant board game, it ought to be a fun code golf!

Steel your Brain

The first 3 lines perform initialisation. i is a fixed list of row/column numbers. The value of each square on the board (O, X, or nil) is stored in the (1D) array b. Empty squares, stored as nil, are replaced by . on output. The starting configuration is encoded by the 10-byte string ?>=<765/.', whose codepoints give the indices of squares containing X's. t is a hash that stores the index of the piece moved on each player's previous turn (this piece cannot be moved on the next turn). A and E store the 'active' and 'enemy' piece symbols and are interchanged each turn.

Being constants (uppercase names), A and E have global scope. Constants are abused throughout the program to avoid scoping issues that would arise with ordinary local variables. A side effect is that whenever a constant is reassigned, warnings are emitted to STDERR. (These warnings may be suppressed by calling Ruby with the -W0 option.)

Now the main loop begins, running until one player wins. Following the 3 lines that display the board, the remainder of the program is enclosed in an eval string, which allows a few chunks of code (stored in the strings $f, $g, and h) to be recycled. The first 5 lines of this string contain the real meat of the program: the lambdas M and N.

Mary had a little lambda

Let's start with N. N finds the set of all squares that are connected to the square at co-ordinates o (co-ordinates are pairs of 0-indexed column and row numbers). Here, connected means that there is a path between all the squares that is not blocked by enemy pieces. Source and destination squares must be unconnected as a prerequisite for jumping an enemy piece. N fans out from the current square, adding its non-enemy neighbours (n=M[o]) and their neighbours (n|=n.flat_map{M[_1]) to the set n by calling M (see below). We redo this process, adding more neighbours of neighbours, until n no longer changes (i.e. until all connected squares have been found).

M probes the board around the square at co-ordinates u. Its exact behaviour is determined by the switch w, which takes a value of either nil (a.k.a. p) or 1:

• When w is nil, M returns an array s of the co-ordinates of all neighbours (8-neighbourhood) of the square at u that do not contain enemy pieces (k!=E). Lambda N uses this information to find the set of all squares that are connected to the current square, as described above. The co-ordinates of each neighbour (column c and row r, stored as the pair v) are obtained by independently advancing c and r by -1, 0, or 1 ((0..8).map...(v=c+=_1/3-1,r+=_1%3-1)), ensuring that c and r both lie within the board ((v=...)-i==[]). This code for finding adjacent squares is required again later, so to save bytes it is stored as a string in $f and interpolated into the eval string. Similarly, the code that returns the value of the square at v is saved in $g ($g='b[c+8*r]').

• When w equals 1 and the square at u contains one of the active player's pieces (b[z]==A), M does two things:

  1. It returns an array s containing all possible moves for the active player originating from this square.

  2. It saves the values of all neighbouring squares in Q, which is used later to test for quagmire.

  Moves are only allowed if the piece was not moved on the previous turn (t[A]!=z). For jumps, the destination square is found by advancing c and r in the same directions a second time (by interpolating $f) and testing whether this square is empty (!#$g). For a jump to be possible, there must either be an active piece to jump over (k==A) or, if an enemy piece is being jumped, the source and destination squares must be unconnected (k&&N[u]&N[v]==[]). For ordinary moves, c and r are reset (c,r=u) and then both variables are advanced in the same directions as before, one square at a time, until no further move along that path is possible (while#$f!#$g). Moves are saved (s<<u+v) in the format [c,r,x,y], that is, the column and row numbers of the source square followed by the column and row numbers of the destination.

Into the quagmire

The last four lines of the program run the game according to the following steps:

1. Loop over all squares of the board by forming pairs of column and row numbers (i.product(i)).

2. For the current square, complete the following steps, all saved in h:

   • Call M in move-finding mode (M[_1,1]). If the square contains an enemy piece, update Q with the values of the neighbouring squares. (Any possible moves for that piece are also returned, but we immediately discard them: it's not the opponent's turn to move, after all!)

   • Interchange the active and enemy pieces (A,E=E,A). The reason for interchanging players is that quagmire checks are performed twice per square, once (here in step 2) to find whether the opponent has left a piece in quagmire and again (in step 4) to find whether the active player has been quagmired by the opponent's previous move.

   • Test whether the current square contains a quagmired enemy piece (([p,A]&Q)[0]). ([p,A]&Q)[0] is truthy only if there are no empty neighbours and at least one neighbour is an active piece.

3. If the current square contains a quagmired enemy piece then the game is won. Print the active player's symbol (p A) and terminate by throwing a tantrum (Z is not defined).

4. Repeat step 2, reading 'active' for 'enemy' and vice versa, but this time add all possible moves (neglecting quagmire for the moment) for the active player to m and keep a copy in e (m+=e=#{h}). If the current square contains a quagmired active piece then add e to q as well (q+=e).

5. Outside the loop, interchange the active/enemy pieces to advance the turn (A,E=E,A).

6. Finally it's time for some input!

   • We now have two lists of moves for the active player: m contains all possible moves (neglecting quagmire) whereas q (a subset of m) contains possible moves by any quagmired pieces. (m[0]?q[0]?q:m:(p E;Z)) decides which move list should be used. If m is empty (i.e. the active player has no possible moves) then the game is lost; print the opponent's symbol and terminate (m[0]?...:(p E;Z)). If q is nonempty it takes precedence over m (q[0]?q:m).

   • Until a valid move is entered correctly (until[[c,r,x,y]]-(...)==[]), display the prompt ($><<A+?>) and convert the input to 0-indexed column/row numbers (gets.bytes.map{~-_1%8}).

7. Update the source and destination squares, saving the destination index in t (#$g,b[t[A]=x+8*y]=p,A).