Robson's Proof that GO is EXP-time Hard
J.M. Robson proved that GO is EXP-time hard by reducing any instance of a certain EXP-time complete problem to a GO position involving a capturing race. In the following you will see how the reduction is done using ladders instead -- this (aesthetic at least) improvement on Robson proof was part of a master thesis "PSPACE vs EXP-time and the game of Go" by "crasmarum".
Consider the following problem: White to move, is the bottom group alive?
It is relatively easy to see that the only move that makes the group alive is to capture the upper KO.
This move will make either the left l ladder or the right r ladder to work for White. Moreover, there is no local KO threat for White nor for Black due to shortage of liberties of some groups.
Now consider the following diagram, White to play:
We can see that the ladder coming from the lower left corner either turns to left if Blacks plays a or continues in the same direction if Black plays b.
In the following diagram is White turn to chose the ladder's path:
Using the above path changing configurations you can create ladders that have as many paths as desired, for example:
The above ladder has 4 possible paths: a,b,c,d. You can see that the ladder works for White if (a path works AND b path works) OR (c path works AND d path works).
Using the above observations and increasing the board size as much as required, we could modify Position 1 as follows:
- add as many KO gadgets as needed, say K1,K2,...,Kn
- add path changing configurations on the left side to make the ladder connect all KO gadgets -- that is, the left ladder will have n possible paths: l1 to K1, l2 to K2, etc.
- keep the position symmetric by mirroring the left path changing configurations on the right ladder.
If we do as explained, in the obtained position we will have that:
- the only moves that may make White's bottom group alive or kill it are the Kos
- White is alive if she can play a sequence k_i1, k_i2, ... of KOs that forces Black to respond on say k_j1, k_j2, ... KOs and she can drive the left ladder to a won ko no matter what Black plays.
What it remains to be done is the difficult part to show that any EXP-time computation can be reduced to an abstract game with some rules like:
- the "board" of the game is a certain positive Boolean formula F over the K1,..., Kn variables.
- the initial position is a an assignment to the K1,..., Kn variables;
- White moves by choosing a variable Ki and changing its assignment to (Ki -> true)
- Black moves by choosing a variable Kj and changing its assignment to (Kj -> false)
- The rule of KO applies, that is, a player cannot immediately revert the opponent's last move
- White wins if she is to move and the current assignment makes formula F true.
See "Exponential time decision problems relating to KO-like transition rules" for more details.