Find an algorithm to balance this game

Question

I've tried to extract just the part of the problem where I'm having trouble, this is part of a bigger project that I'm doing (not homework). I think it's easiest to describe it as a game (since I need it to finish a game I'm working on). This is a one player game the way I'm describing it.

START You start with one of two positions:

• weight (2,0,-1) and one red play
• weight (3,1,-1) and two red plays

END The game ends when you have no more plays. The goal is to end the game with weight (0,0,0).

There are two types of plays red and blue. Given a play, you choose one of four pieces: A,B,C,D that give you additional weight and possibly additional plays. Here are the rules:

• On a red play:

  • A adds weight (0,-2,-1)
  • B adds weight (1,-1,-1) and adds one red play
  • C adds weight (2,0,-1) and two red plays
  • D adds weight (0,2,1) and two blue plays

The rules for blue plays are similar but the first two columns for weights are swapped and the last column is reverse and the types of plays are reversed, so you get this instead:

• On a blue play:

  • A adds weight (-2,0,1)
  • B adds weight (-1,1,1) and adds one blue play
  • C adds weight (0,2,1) and two blue plays
  • D adds weight (2,0,-1) and two red plays

QUESTION Can this game be won?

I'm trying to write a program that wins the game by choosing plays so that the final balance is (0,0,0) when you have no more plays. Only I can't seem to do it. So now I think that maybe there is no algorithm to win the game. I'd really like to know why that is. If anyone has any ideas how I can prove that, then please let me know!! Or, if you try it and find a way to win, then please tell me that, too. Thanks!!

Answer 1

Probably I'm missing something, but just by inspection, it looks like this sequence of steps should work? :

• start with "weight (2,0,-1) and one red play"
• take a red play, piece C, which "adds weight (2,0,-1) and two red plays", leaving you with weight (4,0,-2) and two red plays.
• take a red play, piece A, which "adds weight (0,-2,-1)", leaving you with weight (4,-2,-3) and one red play.
• take a red play, piece D, which "adds weight (0,2,1) and two blue plays", leaving you with weight (4,0,-2) and two blue plays.
• take a blue play, piece A, which "adds weight (-2,0,1)", leaving you with weight (2,0,-1) and one blue play.
• take a blue play, piece A, which "adds weight (-2,0,1)", leaving you with weight (0,0,0) and no plays.

A bit more schematically:

move        weight         plays
------      ---------      -------
            (2,0,-1)       red
red C       (4,0,-2)       red x2
red A       (4,-2,-3)      red
red D       (4,0,-2)       blue x2
blue A      (2,0,-1)       blue
blue A      (0,0,0)        -

. . . no?

---

Edited to add:

How I Found This:

Since this question has garnered a lot of interest, maybe I should explain how I found the above solution. It was basically luck; I happened upon two key observations:

• red A and red D cancel each other out weight-wise (the former adds (0,-2,-1), the latter adds (0,2,1)), and add a total of two blue plays (both from red D) and no red plays; so if you play one right after the other, you "convert" two red plays into two blue plays.
• blue A cancels out the initial weight (it adds (2,0,-1)) and adds no plays, so the entire problem can be solved by "converting" one red play into one blue play.

That gave me a good start. I started with red C so as to get the two red plays that I could "convert" to two blue plays, and I immediately saw that red C was also the "opposite" of blue A weight-wise, so could also be canceled with a blue A. In my head, it all seemed to cancel out perfectly; then I wrote it down to make sure.

Proof That It's Minimal:

Also, while I didn't bother to reason through it at the time, I can also prove that this is a "minimal" winning sequence for that starting position — by which I mean, that if a sequence starts with "weight (2,0,-1) and one red play" and ends with weight (0,0,0) and no plays, then the sequence must contain at least five moves. To do so, assume that we have a sequence that meets this condition and has fewer than five moves. Then:

1. Since the first component of the weight starts out positive, and no red play decreases it, the sequence will require at least one blue play, which means that it will necessarily include red D at least once (since that's the only way to acquire a blue play if you don't start out with one).
2. Since the sequence includes red D at least once, and red D gives us two blue plays, the sequence will necessarily include blue at least twice (since the game doesn't end until no plays remain).
3. Since the sequence includes red D at least once, and red D adds 2 to the second component of the weight, it will necessarily either contain red A at least once, or else contain red B at least twice (since there is no other way to decrease the second component of the weight by at least 2). But clearly, if it contains red D at least once, blue at least twice, and red B at least twice, then it will contain at least five moves, which is forbidden by assumption; so it must use the red A approach.
4. So, the sequence contains red D at least once, blue at least twice, and red A at least once. And by assumption, it contains fewer than five moves. So it must consist of exactly one red D, two blues, one red A, and zero other moves.
5. The starting position gives us only one red play, and the sequence includes exactly two red plays. Therefore, the sequence must contain a move that yields exactly one red play. But the only possible move that could do that is red B, which the sequence doesn't contain.

Therefore, no such sequence is possible.

The Other Starting Position:

I can also prove, using similar sorts of arguments, that any solution starting with the "weight (3,1,-1) and two red plays" option must also contain at least five moves. One such five-move solution is:

move        weight         plays
------      ---------      -------
            (3,1,-1)       red x2
red A       (3,-1,-2)      red
red B       (4,-2,-3)      red
red D       (4,0,-2)       blue x2
blue A      (2,0,-1)       blue
blue A      (0,0,0)        -