Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Gizogin]

I've been working on a problem in combinatorial game theory for some time now, and I thought I'd share it with the world in hopes of getting some new insight.

My work so far can be found here: https://docs.google.com/spreadsheets/d/1cmIpntT8tm8hSIkLohbFh06Gd6-PaxIxGChgC4viDDE/edit?usp=sharing

As part of a Game Theory class back in spring, I developed a game which I called "Negative". The rules are simple: Two player take turns removing black or white squares from a rectangular grid. One player, whom I will name Alice, may remove only black squares; her opponent, Bob, may only remove white squares. During a player's turn, that player removes one square of their color, then inverts the color of all orthogonally adjacent squares. Play ends when one player is unable to remove any squares of their color; the last player to make a move wins.

Spoiler: Example of play (click to show/hide)

Black squares are represented by "A", white squares by "B"; Alice is to move:

Code: [Select]

ABA     -AA
BBB -A> ABB
ABA     ABA


The rules are not complicated, but the game itself explodes quickly. For the moment, let's restrict ourselves to games on a 1xn grid, which we can represent as a number like so:
Convert the number to its binary representation, and ignore any leading zeroes. Remove the most-significant (left-most) one, then convert any zeroes to black squares and any ones to white squares. For example, 13 is 1101, which represents the game {BAB}.
Obviously, some games will be represented twice (5 = {AB}, 6 = {BA}). The number of unique (up to reflection) games of n squares is given by OEIS sequence A005418.

The first few terms of this sequence are: 1, 2, 3, 6, 10, 20, 36, 72, 136, ...
As you can see, the number of unique games nearly doubles every time you add another square.

I have thus far been unable to find any general winning strategy, even on games containing less than seven squares. For any strategy I can devise, there is at least one game that causes this strategy to fail; a simple strategy to maximize the number of squares of one's own color fails as early as {AABB}, for example (the winning move for Alice is to move to {BBB}, not {B}+{AB}).

Spoiler: Some observations (click to show/hide)

All of these are true for games with seven or fewer squares.
1) If Alice can win moving first on a contiguous game X, Alice can win moving first on at least one of XAB or ABX. This requires that X is formatted to match the lowest number of any that are equivalent.
2) If Alice can win moving second on a contiguous game X (formatted as in 1), then Alice can win moving first on at least one of XAB or ABX.

[MoonyTheHuman]

Neat!

[Gizogin]

New observation:
I got the idea for this game from those light puzzles you see in a lot of other games. You know, the ones where you have a square grid of lights and you have to make them all one color by inverting groups of them at a time? The rules for inverting colors are exactly the same here.

That game is called "Lights Out", specifically when it is a grid of 5x5 or another odd square. In Lights Out, assuming the initial configuration is solvable, each square needs to be pressed (flipping it and the squares around it) either once or zero times, and order doesn't matter. In fact, a winning strategy exists for all solvable configurations of 5x5 Lights Out, with a simple extension to other square grids, though it may require pressing certain squares multiple times; it is not the optimal solution.

To get from that to the two-player variant, "Negative", is not a simple task; Lights Out does not restrict the squares you may press, so that must be added as a stipulation.

We can analyze a simpler, impartial variant of Negative, which more closely resembles Lights Out. This time, both players may only play on white. Each square may be pressed at most once, as before. Also as before, play ends when either player is unable to press a white square, though in this case this is equivalent to all unpressed squares being black.

I can't be certain, but I have a suspicion that "solving" this simpler game might lead us to a better understanding of Negative. If, for example, we can prove that an optimal solution to a given Lights Out configuration never requires pressing a black square, we might be able to directly show that the same solution leads to a winning solution for one player of that same configuration in impartial Negative.

Spoiler: Elaboration: (click to show/hide)

In an optimal solution to Lights Out, each square will be pressed at most once. In Lights Out, the order of moves does not matter, but this is not necessarily the case in white-only Lights Out; certain moves will be called for on squares that change color because of other adjacent moves. In our optimal solution that does not require us to press any black squares, then, we have both a set of squares to be pressed and a partial order on those squares. At any point in the game, there may be white squares that are not in our set of winning moves; by definition, pressing any of these squares will cause our optimal solution to fail, requiring that we either press that square again, if possible, or that we find a new solution from the new configuration.

Note that any configuration that is solvable in Lights Out is part of a closed set of all solvable configurations. No move on any solvable configuration can lead to an unsolvable configuration, since any move can be undone by making it again. This is not necessarily the case in white-only Lights Out, where order matters.

Impartial Negative can be a little bit more forgiving with the order. Since we only care about running out of playable white squares, we can asume that every square that has already been pressed is black and cannot be changed.

What's important to note in the transition from one-player white-only Lights Out to two-player impartial Negative is that two players have no reason to cooperate. In fact, if a solution to a white-only Lights Out board takes, for example, six moves, the first player will never cooperate with that strategy, as it would cause the second player to win. The first player will take the first opportunity to sabotage the strategy by taking a white square not in the winning set, as it cannot be any worse for her than cooperating would be.

"Solving" impartial Negative, then, would require showing that certain configurations can always be solved in a certain number of moves (or a set of numbers of moves with the same parity), regardless of the losing player's actions.

I'm going to work on adjusting my algorithm to handle the impartial game.

By the way, if anyone knows how to work cgsuite (an application designed to aid in the analysis of combinatorial games), I'd love to know what it says about Negative (partial or impartial).

[Antsan]

PTW.

I'm sorry for not contributing anything for now.

[Reelya]

That's certainly interesting, are you working on making a playable version of this?

[Sir Knight]

You say you're looking for help; you mean to solve this game?  Because it sure looks like there's interest in playing it.

If there's no general winning strategy, then you've come up with something salable.

[MoonyTheHuman]

I may implement this in JS+HTML for practice in the future, then you all could play it :p

[Reelya]

I have thus far been unable to find any general winning strategy, even on games containing less than seven squares. For any strategy I can devise, there is at least one game that causes this strategy to fail; a simple strategy to maximize the number of squares of one's own color fails as early as {AABB}, for example (the winning move for Alice is to move to {BBB}, not {B}+{AB}).

Well the winning strategy is probably more along the line of "if you see pattern X, do move Y", so the job of the strategist is to determine what those patterns are, as you would in a game like Othello/Reversi.

Obviously games of less than 3 tiles left are trivial. The game is then deterministic based on who goes first and what the board configuration is. We can assume "A"lice always goes first for the purposes of designing strategies.

AA - Bob wins.
AB - Alice Wins.
BB - Bob wins.

So player 2 always wins 2/3 random games for length 2 boards.

AAA - Alice can go on the left or middle. If she goes on the left, you get BA, then bob wins, otherwise you get B_B and Bob wins.
AAB - alice can go on the left or middle.  If she goes on the left, you get BB, and alice wins, otherwise you get B_A and Alice wins.
ABB - Alice has no choices at all. She goes on the left => AB, bob goes on the right => B. Bob wins.
BAB - Alice has no choices at all. She goes in the middle => A_A, Alice Wins
BBB - Bob wins
ABA - Alice can go on the left. Then you get AA, Alice wins.

I've ignored mirror-image games. From what I can tell, none of the 3x1 games actually have a choice that allows the current player to affect winning or losing. But I can tell you something about the strategy now.

"Islands" are separated 1x1 areas. Since they are either A or B, you want to prevent making 1x1 "islands" for your opponent. Also the 2x1 areas can be exploited, because knowing what color they are and who's turn it is gives you a deterministic evaluation of who will win them. Note, you can ignore any solid-color ones and only have to worry about the AB ones.

So ... AABB with Alice to move (With bob to move is a mirror image of this game, but with B instead of A)

Alice can move AABB -> B_AB. But this creates two separate low-level pieces Bob can exploit. He can flip the AB => B or eliminate the "island B". Notes, that if he flips the "island B", then Alice can flip AB => _A creating her own Island. So when you see an AB and it's your turn you should always flip that before any Islands. Alice shouldn't move AABB -> B_AB because you don't want to create AB's on your opponent's turn or give them islands of their color. That's your strategy.

Alice can alternately flip AABB -> BBB. But as you'll notice from my evaluation above, when you have 3x1 of your own color and its your turn, your opponent always wins. Alice as an experienced player knows this and creates a BBB that bob needs to move on during his turn, which results in an Alice win.

Let's see if this same logic can be applied to other 4x1 games. Obviously ones with only one "A" are trivial since there's only one choice, they devolve straight to the lesser puzzles. So it needs to be alternate 2A, 3A or 4A puzzles:

ABAB. (result: not a game)
- ABAB => AAB. Rule: Someone (bob) forced to go on the end of a 3x1 loses, so Alice wins.
- ABAB => AA_A. Alice wins this easily, no question.

ABBA (palindrome) => _ABA. Someone forced to go in the middle of a 3x1 wins, so Alice wins. Not a game.
BAAB (palindrome) => A_BB. Bob goes to the BB => A giving Alice two islands so Alice wins. Not a game.

AAAB has more choices (but none of them favor the A player)
 => _BAB. Rule: someone who can pick from left or right of a 3x1 wins. So bob wins
 => B_BB: alice made islands for bob, so he wins.
 => AB_A: better, alice made an island for herself. But still, bob flips AB=>B, alice flips her island, then bob flips his and wins.

Well, I think the strategy for 1xn could just be memorizing the patterns for 1x3 then avoiding making patterns that favor your enemy while trying to make islands that favor yourself. Also, always flip ABs before islands, because ABs favor whoever flips them first.

[MaximumZero]

How is this different than Go?

[Reelya]

I don't think it's simlar to Go at all. In this one the board starts full, and you delete tiles, also flipping over adjacent tiles. That's not how Go works.