Home * People * John Tromp
JOHN0.jpg

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. He was affiliated with the Centrum Wiskunde & Informatica (CWI) and currently resides in Long Island, New York [1].
John Tromp [2]

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

[7]

1989

1990 ...

2000 ...

2010 ...


Postings


External Links


References

  1. ^ John Tromp HomePage
  2. ^ John Tromp HomePage
  3. ^ Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3
  4. ^ John's Chess Playground - Number of chess diagrams and positions
  5. ^ Number of Go positions computed at last by John Tromp, The Computer-go Archives, January 22, 2016
  6. ^ Counting Legal Positions in Go by John Tromp, January 20, 2016
  7. ^ dblp: John Tromp
  8. ^ Prouhet–Thue–Morse Sequence, Prouhet–Thue–Morse constant from Wikipedia
  9. ^ Combinatorics on words from Wikipedia
  10. ^ The Shodan Go Bet
  11. ^ Cuckoo Cycle: a new memory-hard proof-of-work system by John Tromp, Bitcoin Forum, January 08, 2014
  12. ^ Cuckoo hashing from Wikipedia

What links here?


Up one level