4
$\begingroup$

Here is the game's setup:

You're given a formula for a binary expression using and or not as the connectives. The connectives are combining many variables for which two players will assign truth values to them in the order specified beforehand.
For Example: 

formula: ((x and y) or ((y and z) or (not y and not z)))
turns: AAB
variables: xyz

In this example Player A will assign a truth to x first, then y, then Player B will assign a truth to z. (The variables will always show up in the order of appearance in the formula).
After all of the truth values are assigned to each variable, the formula is evaluated and the truth is returned and a winner is declared. Player A is trying to make it False and B is trying to make it True.

Assume that the other player and will always choose the best value for his variable on all of his turns. If there is no way for a player to make the formula win during his turn, or if choosing either true or false would lead to winning, then false is returned if it is player A’s turn, and true is returned if it is player B’s turn.

Our job is to give the best move for the current turn given a formula the previous moves and the order of moves for the game.

What would the strategy for approaching something this look like? I know this is a homework question but I've spent a week trying to figure this out without any avail. If you need further clarification about the problem as I know it's a big pill to swallow just comment below I'll be sure to reply.

EDIT: For further clarification, variables can show up more than once in the formula

Improve this question
$\endgroup$
6
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – D.W. ♦
    Commented Mar 18, 2017 at 3:23
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/71693/755, softwareengineering.stackexchange.com/q/344406/34181. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Commented Mar 18, 2017 at 3:25
  • $\begingroup$ Is this a homework problem? I ask because there is only 2 plys (Player A sets some things, then Player B sets some things) and only 3 variables. In this case, brute force is pretty much the only option to care about. If you need to have more variables and more plys (such as each player alternates making moves 5 or 6 times), then tools like alpha-beta pruning become worth talking about. $\endgroup$
    – Cort Ammon
    Commented Mar 18, 2017 at 3:49
  • $\begingroup$ the ordering of the variables and the order of the players that assign the truth values can be up to 26 (can only have lower case letters as variables). And yes this is a homework problem but we have to code it, I just can't figure out how to approach coding up the algorithm without it being super cancer. But to clarify there are only two players. $\endgroup$
    – Krio
    Commented Mar 18, 2017 at 3:55
  • $\begingroup$ The idea I was thinking of was something where we just assume all of our future moves will also be in our favor giving this problem a recursive nature and a very simple answer but I don't think that's how I should be approaching the problem... $\endgroup$
    – Krio
    Commented Mar 18, 2017 at 4:14

1 Answer 1

Reset to default
3
$\begingroup$

Your game is equivalent to the PSPACE-complete problem TQBF. The quantified Boolean formula corresponding to your example is $$ \forall x \forall y \exists z (x \land y) \lor (y \land z) \lor (\lnot y \land \lnot z). $$ Since it is PSPACE-complete, in particular it is NP-hard, and you there is no efficient general way to find out who wins in this game.

There is an exponential time strategy which involves constructing the game tree. While this strategy is feasible when the number of variables is small (like in your example), it is not practical when there are many variables.

Improve this answer
$\endgroup$

Your Answer

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

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