3
votes
How hard is Hex from a symmetric position?
Finding a winning move in symmetric positions in Hex is PSPACE-complete
First, let's define our problem, and call it SYMHEXMOVE:
Take as an input: a symmetric Hex position
Output: any move which is ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
combinatorial-game-theory × 30gt.game-theory × 16
board-games × 6
cc.complexity-theory × 4
reference-request × 4
co.combinatorics × 4
ds.algorithms × 3
np-hardness × 3
pspace × 3
mechanism-design × 3
graph-theory × 2
two-player-games × 2
approximation-algorithms × 1
optimization × 1
time-complexity × 1
sat × 1
lower-bounds × 1
pr.probability × 1
turing-machines × 1
it.information-theory × 1
np-complete × 1
communication-complexity × 1
np × 1
nt.number-theory × 1
application-of-theory × 1