A Game of Logic
I've been thinking about a game which I haven't named yet. The rules are simple. The playing board is a logical expression built from the binary connectives 'and' and 'or', the logical constants 'true' and 'false', and atoms 'A', 'B', 'C', ... For example (A and B) or C. To make things easier I'll use abuttal for 'and' and + for 'or'. The previous example is just AB+C.
There are two players, False and True, who take turns. A legal move for False consists of replacing all occurences of one atom with 'false' and you can guess what True's moves are. True wins if the expression evaluates to 'true' with the obvious interpretation of the symbols I've given and False wins if the expression evaluates to false. There is no possibility of a tie.
For example consider the game (A+B)(C+D)(E+F). This is a win for True whoever plays next. Any time False sets an atom to 'false' True merely has to set the other atom in the same factor to 'true' making the factor 'true'. Eventually all of the factors will have the value 'true'.
So here are some questions:
There are two players, False and True, who take turns. A legal move for False consists of replacing all occurences of one atom with 'false' and you can guess what True's moves are. True wins if the expression evaluates to 'true' with the obvious interpretation of the symbols I've given and False wins if the expression evaluates to false. There is no possibility of a tie.
For example consider the game (A+B)(C+D)(E+F). This is a win for True whoever plays next. Any time False sets an atom to 'false' True merely has to set the other atom in the same factor to 'true' making the factor 'true'. Eventually all of the factors will have the value 'true'.
So here are some questions:
- Has this game already been studied? If so, what's it called?
- Is there a nice way to evaluate any position in the game? A partial answer is given by some papers by Anshelevich on the subject of Hex. All Hex positions are positions in this game and many interesting Hex positions and subproblems can be approximated well by simple positions in this game. (Note that a good strategy for this game might not be a good strategy for Hex because a Hex game corresponds to a very large expression.)
- Can you assign Conway numbers to positions in this game? What is the value of 'true'?
- What happens if you allow the unary operator 'not' and allow the two players to replace an atom with either 'true' or 'false'.
- What other games, besides Hex, are special cases of this game? (All combinatorial games I guess.) What games are special cases in an interesting way?
Labels: mathematics
posted by sigfpe at Wednesday, November 30, 2005
10 Comments:
Interesting.
At first I thought the value of "true" would be zero, if I understand the question properly, since it is a terminal position (there are no available moves).
But that's not right, I'm sure you want "true" to be a win for True.
I guess the question is, how would you define an addition of your logical expressions in this game.
One way to make it well defined is to add separate components disjunctively, without any logical connectives between them, and say that a component ending in "true" is a +1 value, and one ending in "false" is a -1 value; play continues until all components have a value, and then the +1 and -1's are added up. If you like that, then "true" is +1, and "false" is -1 as logical expressions. This would allow a combinatorial game value for every logical expression, and a notion of a sum.
'true' really wants to have the value +infinity because no matter how many turns goes you let False have True still wins.
I was hoping to be able to assign a value to positions in such a way that the values of XY and X+Y can be found from the values of X and Y (at least in the case where X and Y contain no common atom, the general case is more complex). But I don't think the assignment of -1 and +1 helps with that.
In pure Conway-style counting, all that matters is whether you can make a move. So the game as you described under Conway's idea of who wins and who loses depends only on the number of atoms.
So I propose a slight variant: True can place any atom with T (true), or any expression that evaluates to True with T. So, in particular, the game can end at the symbol T, where True can always replace T with T, and False has no moves.
Of course, such a replacement will never be an optimal strategy for True, unless that's all she can do; it's always better to replace some atom by T.
This isn't quite good enough, though... the game T is then larger than _every_ Conway Nimber, and F smaller, as Sigfpe said, and you can't add them Conway-style. In short, it's not immediately obvious to me how to dissect this game into a combinatorial game.
I'm assuming by "Conway's numbers" you mean the theory of disjunctive sums of combinatorial games as described in On Numbers and Games, or Winning Ways. One of the many things that makes this theory attractive is that it permits games with different rules to be analyzed together in a disjunctive sum. On a player's move in a disjunctive sum, he's required to select a single component and move in that component, only. Play ends when no move is available.
When you're asking for a "conway number" for this logic game, the natural interpretation (I think) is that you're looking for values that would permit them to be included in the general disjunctive CGT sum theory; ie you would be able to say "add" a logic game position to a Nim position, or a Chomp position, or apply thermography, or whatever; you could bring all the heavy machinery to bear on the problem.
One way to do it is to take the convention that a Logic Game ending in True is the number 1 by convention; and a Logic Game ending in False is by convention -1. Then all logical expressions will have a well defined game value, and can be included in the broader theory.
It's actually a nice game and there are interesting values; it doesn't boil down to the number of atoms. (I've worked out a few, but enough for one comment...)
Hi Thane,
I was hoping that X or Y might be closely related to the disjunctive sum of A and B (at least when there are no atoms in common between A and B) but it looks like not. Assigning +1 and -1 to 'true' and 'false' were the first thing I tried actually, but it doesn't seem to capture the notion that a position might always be a win for one particular player no matter how many moves they might waste in the other half of a disjunctive sum (if you see what I mean). Now I'm beginning to think the 'surreal number' approach is a red herring.
There are two "sum-like" things present here, if this game is to brought into the CGT theory (as I believe it can be, in a reasonable way). One is the logical ors that can be present inside the LogicGame positions. You've used the notation + for that. The other is the idea of a general combinatorial game sum (which is called 'disjunctive' but doesn't have to much to do with logical or). It also uses the + notation, usually.
If you take the +1 / -1 convention previously described, and know the CGT values for X and Y, I guess you're interested in whether that tells you anything about the LogicGame CGT value of X v Y (ie, "X or Y"). My guess is that there is no simple relationship, but it's worth thinking about what can be said...
0xDE has some comments on the complexity of this game, FYI
This is basically a description of the standard game-theoretic approach to semantics. Most students are only exposed to the truth-table method of proving validity, but in some logics (such as Quantum Logic) that option isn't available and so the semantics are given in terms of a game much like what you describe. If you look for some books on Quantum Logic, I'm sure you'll find more information.
See also http://cstheory.stackexchange.com/questions/25671/is-this-variation-of-tqbf-still-pspace-complete
See also http://cstheory.stackexchange.com/questions/25671/is-this-variation-of-tqbf-still-pspace-complete
Post a Comment
<< Home