Go! Ladders Go
Yutong Zhang, Yanning Tan, Xiaowen(Winnie) Zong
Go, a traditional Chinese board game with a history of over 2500 years, is now known by more and more young people around the world. Now, let’s take a close look at the crystal of ancestors’ wisdom and figure out its complexity.
Introduction of Go
Go is a two-player strategy board game originated from China. It belongs to one of the four arts of the Chinese scholar — qin (guqin, a stringed instrument), qi (the strategy game of go), shu (Chinese calligraphy), and hua (Chinese painting). To play Go, two players take turns placing stones onto a 19×19 grid board; the pieces walk on the crossing point. One plays black, the other plays white; black plays first, and the two sides alternate their moves. Once a stone is placed on the board, you cannot regret your move. The winner is the one who uses his/her stone pieces to enclose more of that of his/her opponent. Go is considered THE most complex board game in the world.
The rules of Go is differ between countries, but there are two basic rules:
The rule of liberty: Stones or groups of stones which lose their last liberty, or open point, are removed from the board. The two diagrams below start with the same board condition — a White surrounded by three Blacks. If it is Black’s turn, then Black can cut off White’s last liberty by placing a stone below it. If it is White’s turn, then White must play at the position below itself (which is its only liberty) to avoid being captured by Black on the next move.
The rule of ko: The diagram below shows a single ko condition where the Black can capture the red-circled White stone by a play at a. The resulting position is shown on the right. White could have recaptured the red-circled Black stone by playing the next move at b, which reverts to our initial situation on the left, and then Black could also recapture… Note that this process could “loop” infinitely if neither player gave way, and the game would never proceed. However, the ko rule resolves the situation. If one player captures the ko, the opponent is prohibited from recapturing the ko immediately.
Introduction of the Topic
In the paper, Ladders are PSPACE-complete, the author Marcel Crasmaru and John Tromp focus on a subproblem of Go — ladders.
So what are ladders? As shown in the comic, the White piece is surrounded by the Black pieces such that it only has one liberty. Now it’s White’s turn. If White wants to avoid being surrounded by Black at its immediate next move, it must place a stone under the current white stone on the board. We may consider the formation of the ladder shown in this comic as White trying to escape from the trap of Black. Each time when it comes to White’s turn, it has one choice of either moving down or right. Eventually, the players would arrive at the boundary of the chessboard, and White cannot go further down. Then, Black could form a closed loop around White, cutting off its last liberty, and Black wins.
It seems that white could never escape. But don’t worry, ladders are not invincible. One situation where the ladder would fail is when there is a White stone “waiting” along the escape route.
Proof
The theorem this paper wants to prove is that ladders are PSPACE-complete.
According to the definition, PSPACE is the class of languages that are decidable in polynomial space on a deterministic Turing machine. And a Turing machine is a mathematical model of computation that defines an abstract machine that manipulates symbols on a strip of tape according to a table of rules.
A language B is PSPACE-complete if it satisfies two conditions:
- B is in PSPACE
- Every A in PSPACE is polynomial-time reducible to B
According to these two conditions, we divide our prior into two parts correspondingly.
First, we want to prove that ladders belong to PSPACE. According to the definition of PSPACE, to prove that ladders are in PSPACE, we want to prove that we can determine whether the white will be captured in a polynomial-depth-limited search.
Because the Size of the chessboard is definite, if the number of stones in the ladder problem grows larger after every move, it has to stop once it fills the whole chessboard. So that we would prove that ladders are in PSPACE, however, will the number of stones in the ladder problem grow larger after every move?
There might be some special situations like ko. If three kos occur at once, it may seem that white stone and black stone can capture each others’ stones back and forth and make an infinite loop. Like the triple ko situation showed below.
However, since the game of go also wants to prevent itself from running infinitely, there are special rules that prevent an infinite loop from happening. Therefore, the search depth is still limited to approximately the board size. Thus, ladders belong to PSPACE.
Before the second part of our proof, we are going to introduce four gadgets. (Notice: our examples all make Black play the ladder, but these gadgets all work the same when the White plays the ladder)
Black Choice: For this gadget, Black is going to choose the direction of where the game moves, either left or right. The key choice is in step 9.
White Choice: For this gadget, White is going to choose the direction of where the game moves. The key choice is on step 12, and the White would either capture Black or extend to the right.
Join: For this gadget, the ladders would work by approaching from either top left or top right.
Mirror: For this gadget, the ladders will be forced to move in the direction that is symmetrical to where it is from. This gadget is very helpful， for it enables players to direct ladders from one gadget to the next.
After proving that the ladder problem belongs to PSPACE, and showing how gadgets work, we want to prove that QBF, a known PSPACE complete problem, reduces to ladders. QBF, quantified Boolean formulas, are boolean formulas with quantifiers: ∀ and ∃. Because QBF is a PSPACE complete problem, if it reduces to ladders, we know that ladders are also PSPACE complete.
To prove this, we want to construct a QBF from Ladders by assigning universal quantifiers to White Choices and existential quantifiers to Black Choices. Then we will combine all the other gadgets we talked about previously in a special sequence such that for all white moves, there will always exist a black move that can capture it.
An example of the ladder constructed by QBF is shown below, with the corresponding formula. And since a QBF could be constructed from ladders, we’ve proved that Ladder is PSPACE complete.
Since ladders belong to PSPACE and QBF is polynomial-time reducible to ladders, we’ve proved that ladders are PSPACE-complete.
Now we’ve proved that ladders are PSPACE-complete! If you want to learn more, check out the following papers!
Discussion
Evaluation
The main contribution of this work is that it successfully proved ladder is not only PSPACE hard but PSPACE-complete.
It is a good idea to construct a polynomial-time reduction from QBF to ladders. The authors cleverly and flexibly engage four gadgets to build various lucid ladder structures that would align with any QBF. This method is also very generalizable, which we can apply to examine the complexity of many other similar games.
However, the first part of the proof (which is to prove Ladders is in PSPACE) is somehow “helped” by the rule of Go (to be more specific, ko). If there does not exist a ko rule to forbid the infinite loop, troubles may occur.
Moreover, the descriptions and marks for some images of the paper were a bit complicated, which requires the audience to have a high-level background knowledge of Go.
Real World Implementation
What does our discussion around Ladders are PSPACE complete tell us? Why is this discussion important?
The computational complexity of go varies with rules (the existence of the ko rule and superko rule). Go suggests a game-tree complexity of between 10^10⁴⁸ and 10^10¹⁷¹, and contributed to the development of combinatorial game theory. (See Tromp and Farnebäck, Combinatorics of Go)
Known as the hardest game because of its complexity in board positions and search space, go is of particular interest to scholars in the artificial intelligence field. This is why the winning of AlphaGo against Lee Sedol in March 2016 was such grave news in academic research and AI development. A DeepMind research paper titled “Mastering the game of Go with Deep Neural Networks & Tree Search” by David Silver and Aja Huang introduces a new approach to computer Go by combining Monte-Carlo tree search with deep neural networks.
In return, the strategies taken by AI players after their reinforcement learning and self-training are studied by human go players as well. (See Innovations of AlphaGo)
Future Improvement
The fact that ladders are PSPACE complete surprised me as Go players. Because the ladder problem is such an elementary exercise in Go that I never expect that it will be PSPACE complete with this many gadgets and variations. So building on the logic this paper follows, it is possible to look at more subproblems on Go and use a similar method to find their complexity.
Member contribution
- Yutong Zhang: Intro of Go, Intro of the Topic, Real World Implementation
- Yanning Tan: Hook, Intro of Proof, Gadget, QBF, Evaluation
- Winnie Zong: Proof, Further improvement, Conclusion