John Tromp has researched on counting the number of legal positions in Go and reachable chess positions, and gives an upper bound of 7728772977965919677164873487685453137329736522 (about 10^45.888 or ~ 2^152.437) on the number of chess positions, but states, like the bound of ~10^46.25 published by Shirish Chinchalkar^{[3]}, that it requires better documentation to be considered verifiable ^{[4]}. On January 20, 2016, the number of legal positions on a standard size Go board was determined to be ^{[5]}:

Home * People * John TrompJohannes (John) Theodorus Tromp,a Dutch mathematician and computer scientist with a Ph.D. in 1993 on algorithms and complexity from University of Amsterdam under advisor Paul Vitányi. His research interests include artificial intelligence and board games such as Connect Four, Chess and Go, complexity, algorithmic information theory, distributed computing, and computational biology. His recreational interests include playing Go and chess. He was affiliated with the Centrum Wiskunde & Informatica (CWI) and currently resides in Long Island, New York

^{[1]}.^{[2]}## Table of Contents

## Number of Positions

John Tromp has researched on counting the number of legal positions in Go and reachable chess positions, and gives an upper bound of7728772977965919677164873487685453137329736522(about 10^45.888 or ~ 2^152.437) on the number of chess positions, but states, like the bound of ~10^46.25 published by Shirish Chinchalkar^{[3]}, that it requires better documentation to be considered verifiable^{[4]}. On January 20, 2016, the number of legal positions on a standard size Go board was determined to be^{[5]}:or more compact

The approximation

has been known since 2006. So what took 10 years to nail it down to the last digit?

^{[6]}## Selected Publications

^{[7]}## 1989

1989).How to Construct an Atomic Variable (Extended Abstract). WDAG 1989## 1990 ...

1992).Wait-free Test-and-Set (Extended Abstract). WDAG 19921993).Aspects of Algorithms and Complexity. Ph.D. thesis, University of Amsterdam, advisor Paul M. B. Vitányi1995).Subword Complexity of a Generalized Thue-Morse Word. Information Processing Letters, Vol. 54, No. 6^{[8]}^{[9]}1996).How to Share Concurrent Wait-Free Variables. Journal of the ACM, Vol. 43, No. 4## 2000 ...

2000).Ladders Are PSPACE-Complete. CG 20002001).Randomized Two-Process Wait-Free Test-and-Set. CoRR2002).A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification. SIROCCO2006).Binary Lambda Calculus and Combinatory Logic. Kolmogorov Complexity and Applications2006).Combinatorics of Go. CG 20062009).Combinatorics of Go. (revised version of the CG 2006 paper), ps## 2010 ...

2011).John Tromp in the Style of David Levy: 4-0 win in the Go bet. ICGA Journal, Vol. 34, No. 2^{[10]}2014).Cuckoo Cycle: a memory-hard proof-of-work system. IACR Cryptology ePrint Archive^{[11]}^{[12]}2016).The number of legal Go positions. CG 20162016).A googolplex of Go games. CG 2016## Postings

## External Links

John's Chess Playground

John's Connect Four Playground » Connect Four

John's Go Page » Go

Counting Legal Positions in Go, January 20, 2016

Programming Pearls

## References

1996).An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3## What links here?

Up one level