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.
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