John Tromp
Johannes (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. Along with Álvaro Begué, John Tromp is co-author of the Go playing program Dimwit [2].
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 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]:
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
or more compact
2081681993819799846 9947863334486277028 6522453884530548425 6394568209274196127 3801537852564845169 8519643907259916015 6281285460898883144 2712971531931755773 6620397247064840935
The approximation
L19 ~ 2.081681994 * 10^170
has been known since 2006. So what took 10 years to nail it down to the last digit? [6]
Selected Publications
1989
- John Tromp (1989). How to Construct an Atomic Variable (Extended Abstract). WDAG 1989
1990 ...
- Yehuda Afek, Eli Gafni, John Tromp, Paul M. B. Vitányi (1992). Wait-free Test-and-Set (Extended Abstract). WDAG 1992
- John Tromp (1993). Aspects of Algorithms and Complexity. Ph.D. thesis, University of Amsterdam, advisor Paul M. B. Vitányi
- John Tromp, Jeffrey Shallit (1995). Subword Complexity of a Generalized Thue-Morse Word. Information Processing Letters, Vol. 54, No. 6 [8] [9]
- Ming Li, John Tromp, Paul M. B. Vitányi (1996). How to Share Concurrent Wait-Free Variables. Journal of the ACM, Vol. 43, No. 4
2000 ...
- Marcel Crâşmaru, John Tromp (2000). Ladders Are PSPACE-Complete. CG 2000
- John Tromp, Paul M. B. Vitányi (2001). Randomized Two-Process Wait-Free Test-and-Set. CoRR
- John Tromp, Paul M. B. Vitányi (2002). A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification. SIROCCO
- John Tromp (2006). Binary Lambda Calculus and Combinatory Logic. Kolmogorov Complexity and Applications
- John Tromp, Gunnar Farnebäck (2006). Combinatorics of Go. CG 2006
2010 ...
- Ingo Althöfer (2011). John Tromp in the Style of David Levy: 4-0 win in the Go bet. ICGA Journal, Vol. 34, No. 2 [10]
- John Tromp (2014). Cuckoo Cycle: a memory-hard proof-of-work system. IACR Cryptology ePrint Archive [11] [12]
- John Tromp, Gunnar Farnebäck (2016). Combinatorics of Go. Revised Version of the CG 2006 Paper
- John Tromp (2016). The number of legal Go positions. CG 2016
- John Tromp, Matthieu Walraet (2016). A googolplex of Go games. CG 2016
Postings
- entropy of chess positions by John Tromp, rgc, April 15, 1991
- Number of Go positions computed at last by John Tromp, The Computer-go Archives, January 22, 2016
- longest 3x3 game by John Tromp, Computer Go Archive, February 18, 2016
- On the number of chess positions by John Tromp, CCC, July 09, 2021
- Re: On the number of chess positions by John Tromp, CCC, April 02, 2022
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
- John Tromp | University Of Amsterdam - Academia.edu
- Computer-go.info - Details of Programmer: Tromp, John
- The Mathematics Genealogy Project - Johannes Tromp
- John Tromp at Sensei's Library
- John Tromp | LinkedIn
References
- ↑ John Tromp HomePage
- ↑ Computer-go.info - Details of Program: Dimwit
- ↑ Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3
- ↑ John's Chess Playground - Number of chess diagrams and positions
- ↑ Number of Go positions computed at last by John Tromp, The Computer-go Archives, January 22, 2016
- ↑ Counting Legal Positions in Go by John Tromp, January 20, 2016
- ↑ dblp: John Tromp
- ↑ Prouhet–Thue–Morse Sequence, Prouhet–Thue–Morse constant from Wikipedia
- ↑ Combinatorics on words from Wikipedia
- ↑ The Shodan Go Bet
- ↑ Cuckoo Cycle: a new memory-hard proof-of-work system by John Tromp, Bitcoin Forum, January 08, 2014
- ↑ Cuckoo hashing from Wikipedia
