“Does this position win?” has a structure like “Is there a move such that, for each possible reply there is a move such that, for each possible reply… you win.”—where existential and universal quantifiers alternate in the nesting. In a SAT problem on the other hand you just have a nest of existentials. I don’t know about Go specifically, but that’s my understanding of the usual core difference between games and SAT.
Much appreciated! So the NP solution to SAT is basically an OR over all of the possible assignments of the variables, where here (or for alternating move games in general), we’ve got alternating ORs and ANDs on sequential moves.
“Does this position win?” has a structure like “Is there a move such that, for each possible reply there is a move such that, for each possible reply… you win.”—where existential and universal quantifiers alternate in the nesting. In a SAT problem on the other hand you just have a nest of existentials. I don’t know about Go specifically, but that’s my understanding of the usual core difference between games and SAT.
Much appreciated! So the NP solution to SAT is basically an OR over all of the possible assignments of the variables, where here (or for alternating move games in general), we’ve got alternating ORs and ANDs on sequential moves.