25,161
edits
Changes
Created page with "'''Home * People * John Tromp''' FILE:JohnTromp.jpg|border|right|thumb|link=https://tromp.github.io/| John Tromp <ref>[https://tromp.github.io/ John Trom..."
'''[[Main Page|Home]] * [[People]] * John Tromp'''
[[FILE:JohnTromp.jpg|border|right|thumb|link=https://tromp.github.io/| John Tromp <ref>[https://tromp.github.io/ John Tromp HomePage]</ref> ]]
'''Johannes (John) Theodorus Tromp''',<br/>
a Dutch mathematician and computer scientist with a Ph.D. in 1993 on [[Algorithms|algorithms]] and [https://en.wikipedia.org/wiki/Computational_complexity_theory complexity] from [https://en.wikipedia.org/wiki/University_of_Amsterdam University of Amsterdam] under advisor [[Mathematician#PVitany|Paul Vitányi]].
His research interests include [[Artificial Intelligence|artificial intelligence]] and [[Games|board games]] such as [[Connect Four]], [[Chess]] and [[Go]], complexity, [https://en.wikipedia.org/wiki/Algorithmic_information_theory algorithmic information theory], [https://en.wikipedia.org/wiki/Distributed_computing distributed computing], and [https://en.wikipedia.org/wiki/Computational_biology computational biology].
His recreational interests include playing [[Go]] and [[Chess|chess]]. Along with [[Álvaro Begué]], John Tromp is co-author of the Go playing program ''Dimwit'' <ref>[http://www.computer-go.info/db/oprog.php?a=Dimwit Computer-go.info - Details of Program: Dimwit]</ref>.
=Number of Positions=
John Tromp has researched on counting the number of legal positions in [[Go]] and reachable [[Chess Position|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]] <ref>[[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref>, that it requires better documentation to be considered verifiable <ref>[https://tromp.github.io/chess/chess.html John's Chess Playground - Number of chess diagrams and positions]</ref>. On January 20, 2016, the number of legal positions on a standard size Go board was determined to be <ref>[https://groups.google.com/d/msg/computer-go-archive/jlVCk9IRGEY/us3LHpTPCgAJ Number of Go positions computed at last] by [[John Tromp]], [http://computer-go.org/pipermail/computer-go/ The Computer-go Archives], January 22, 2016</ref>:
<pre>
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
</pre>
or more compact
<pre>
2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935
</pre>
The approximation
<pre>
L19 ~ 2.081681994 * 10^170
</pre>
has been known since 2006. So what took 10 years to nail it down to the last digit? <ref>[http://tromp.github.io/go/legal.html Counting Legal Positions in Go] by [[John Tromp]], January 20, 2016</ref>
=Selected Publications=
<ref>[https://dblp.uni-trier.de/pers/hd/t/Tromp:John dblp: John Tromp]</ref>
==1989==
* [[John Tromp]] ('''1989'''). ''How to Construct an Atomic Variable (Extended Abstract)''. [http://www.informatik.uni-trier.de/~ley/db/conf/wdag/wdag89.html#Tromp89 WDAG 1989]
==1990 ...==
* [http://www.informatik.uni-trier.de/~ley/pers/hd/a/Afek:Yehuda.html Yehuda Afek], [http://www.informatik.uni-trier.de/~ley/pers/hd/g/Gafni:Eli.html Eli Gafni], [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''1992'''). ''Wait-free Test-and-Set (Extended Abstract)''. [http://www.informatik.uni-trier.de/~ley/db/conf/wdag/wdag92.html#AfekGTV92 WDAG 1992]
* [[John Tromp]] ('''1993'''). ''[https://tromp.github.io/thesis.html Aspects of Algorithms and Complexity]''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Amsterdam University of Amsterdam], advisor [[Mathematician#PVitany|Paul M. B. Vitányi]]
* [[John Tromp]], [[Mathematician#JShallit|Jeffrey Shallit]] ('''1995'''). ''Subword Complexity of a Generalized Thue-Morse Word''. [https://en.wikipedia.org/wiki/Information_Processing_Letters Information Processing Letters], Vol. 54, No. 6 <ref>[[Max Euwe#ProuhetThueMorseSequence|Prouhet–Thue–Morse Sequence]], [https://en.wikipedia.org/wiki/Prouhet%E2%80%93Thue%E2%80%93Morse_constant Prouhet–Thue–Morse constant from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/Combinatorics_on_words Combinatorics on words from Wikipedia]</ref>
* [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Li:Ming.html Ming Li], [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''1996'''). ''How to Share Concurrent Wait-Free Variables''. [[ACM#Journal|Journal of the ACM]], Vol. 43, No. 4
==2000 ...==
* [[Marcel Crâşmaru]], [[John Tromp]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_16 Ladders Are PSPACE-Complete]''. [[CG 2000]]
* [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''2001'''). ''Randomized Two-Process Wait-Free Test-and-Set''. [http://www.informatik.uni-trier.de/~ley/db/journals/corr/corr0106.html#cs-DC-0106056 CoRR]
* [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''2002'''). ''A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification''. [http://www.informatik.uni-trier.de/~ley/db/conf/sirocco/sirocco2002.html#TrompV02 SIROCCO]
* [[John Tromp]] ('''2006'''). ''Binary Lambda Calculus and Combinatory Logic''. [http://www.informatik.uni-trier.de/~ley/db/conf/dagstuhl/P6051.html#Tromp06 Kolmogorov Complexity and Applications]
* [[John Tromp]], [[Gunnar Farnebäck]] ('''2006'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-75538-8_8 Combinatorics of Go]''. [[CG 2006]]
* [[John Tromp]], [[Gunnar Farnebäck]] ('''2009'''). ''Combinatorics of Go''. (revised version of the [[CG 2006]] paper), [http://www.google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA&url=http%3A%2F%2Fhomepages.cwi.nl%2F~tromp%2Fgo%2Fgostate.ps&ei=4c-_TZHrIozbsgbbqeH1Bg&usg=AFQjCNHHe9_yffwPyFYLzlzy9GHGS5EuKw ps]
==2010 ...==
* [[Ingo Althöfer]] ('''2011'''). ''John Tromp in the Style of David Levy: 4-0 win in the Go bet''. [[ICGA Journal#34_2|ICGA Journal, Vol. 34, No. 2]] <ref>[http://dcook.org/gobet/ The Shodan Go Bet]</ref>
* [[John Tromp]] ('''2014'''). ''[https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf Cuckoo Cycle: a memory-hard proof-of-work system]''. [http://www.informatik.uni-trier.de/~ley/db/journals/iacr/iacr2014.html#Tromp14 IACR Cryptology ePrint Archive] <ref>[https://bitcointalk.org/index.php?topic=405483.0 Cuckoo Cycle: a new memory-hard proof-of-work system] by [[John Tromp]], [https://bitcointalk.org/index.php Bitcoin Forum], January 08, 2014</ref> <ref>[https://en.wikipedia.org/wiki/Cuckoo_hashing Cuckoo hashing from Wikipedia]</ref>
* [[John Tromp]] ('''2016'''). ''The number of legal Go positions''. [[CG 2016]]
* [[John Tromp]], [[Matthieu Walraet]] ('''2016'''). ''[[Matthieu Walraet#googolplex|A googolplex of Go games]]''. [[CG 2016]]
=Postings=
* [https://groups.google.com/d/msg/rec.games.chess/pyM6LfZPbvY/DO2V0y4BezIJ entropy of chess positions] by [[John Tromp]], [[Computer Chess Forums|rgc]], April 15, 1991
* [https://groups.google.com/d/msg/computer-go-archive/jlVCk9IRGEY/us3LHpTPCgAJ Number of Go positions computed at last] by [[John Tromp]], [http://computer-go.org/pipermail/computer-go/ The Computer-go Archives], January 22, 2016
* [https://groups.google.com/d/msg/computer-go-archive/sTHY0pBpm0o/3s_YkoUlBQAJ longest 3x3 game] by [[John Tromp]], [https://groups.google.com/forum/#!forum/computer-go-archive Computer Go Archive], February 18, 2016
=External Links=
* [https://en.wikipedia.org/wiki/John_Tromp John Tromp from Wikipedia]
* [https://github.com/tromp tromp (John Tromp) · GitHub]
* [https://tromp.github.io/ John Tromp HomePage]
: [https://tromp.github.io/chess/chess.html John's Chess Playground]
: [https://tromp.github.io/c4/c4.html John's Connect Four Playground] » [[Connect Four]]
: [https://tromp.github.io/go.html John's Go Page] » [[Go]]
: [https://tromp.github.io/go/legal.html Counting Legal Positions in Go], January 20, 2016
: [https://tromp.github.io/pearls.html Programming Pearls]
* [http://amsterdam.academia.edu/JohnTromp John Tromp | University Of Amsterdam - Academia.edu]
* [http://www.computer-go.info/db/operson.php?a=Tromp%2C+John Computer-go.info - Details of Programmer: Tromp, John]
* [https://genealogy.math.ndsu.nodak.edu/id.php?id=66084 The Mathematics Genealogy Project - Johannes Tromp]
* [http://senseis.xmp.net/?JohnTromp John Tromp at Sensei's Library]
* [https://www.linkedin.com/in/john-tromp-b1601b8/ John Tromp | LinkedIn]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Go Programmer|Tromp]]
[[Category:Researcher|Tromp]]
[[FILE:JohnTromp.jpg|border|right|thumb|link=https://tromp.github.io/| John Tromp <ref>[https://tromp.github.io/ John Tromp HomePage]</ref> ]]
'''Johannes (John) Theodorus Tromp''',<br/>
a Dutch mathematician and computer scientist with a Ph.D. in 1993 on [[Algorithms|algorithms]] and [https://en.wikipedia.org/wiki/Computational_complexity_theory complexity] from [https://en.wikipedia.org/wiki/University_of_Amsterdam University of Amsterdam] under advisor [[Mathematician#PVitany|Paul Vitányi]].
His research interests include [[Artificial Intelligence|artificial intelligence]] and [[Games|board games]] such as [[Connect Four]], [[Chess]] and [[Go]], complexity, [https://en.wikipedia.org/wiki/Algorithmic_information_theory algorithmic information theory], [https://en.wikipedia.org/wiki/Distributed_computing distributed computing], and [https://en.wikipedia.org/wiki/Computational_biology computational biology].
His recreational interests include playing [[Go]] and [[Chess|chess]]. Along with [[Álvaro Begué]], John Tromp is co-author of the Go playing program ''Dimwit'' <ref>[http://www.computer-go.info/db/oprog.php?a=Dimwit Computer-go.info - Details of Program: Dimwit]</ref>.
=Number of Positions=
John Tromp has researched on counting the number of legal positions in [[Go]] and reachable [[Chess Position|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]] <ref>[[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref>, that it requires better documentation to be considered verifiable <ref>[https://tromp.github.io/chess/chess.html John's Chess Playground - Number of chess diagrams and positions]</ref>. On January 20, 2016, the number of legal positions on a standard size Go board was determined to be <ref>[https://groups.google.com/d/msg/computer-go-archive/jlVCk9IRGEY/us3LHpTPCgAJ Number of Go positions computed at last] by [[John Tromp]], [http://computer-go.org/pipermail/computer-go/ The Computer-go Archives], January 22, 2016</ref>:
<pre>
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
</pre>
or more compact
<pre>
2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935
</pre>
The approximation
<pre>
L19 ~ 2.081681994 * 10^170
</pre>
has been known since 2006. So what took 10 years to nail it down to the last digit? <ref>[http://tromp.github.io/go/legal.html Counting Legal Positions in Go] by [[John Tromp]], January 20, 2016</ref>
=Selected Publications=
<ref>[https://dblp.uni-trier.de/pers/hd/t/Tromp:John dblp: John Tromp]</ref>
==1989==
* [[John Tromp]] ('''1989'''). ''How to Construct an Atomic Variable (Extended Abstract)''. [http://www.informatik.uni-trier.de/~ley/db/conf/wdag/wdag89.html#Tromp89 WDAG 1989]
==1990 ...==
* [http://www.informatik.uni-trier.de/~ley/pers/hd/a/Afek:Yehuda.html Yehuda Afek], [http://www.informatik.uni-trier.de/~ley/pers/hd/g/Gafni:Eli.html Eli Gafni], [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''1992'''). ''Wait-free Test-and-Set (Extended Abstract)''. [http://www.informatik.uni-trier.de/~ley/db/conf/wdag/wdag92.html#AfekGTV92 WDAG 1992]
* [[John Tromp]] ('''1993'''). ''[https://tromp.github.io/thesis.html Aspects of Algorithms and Complexity]''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Amsterdam University of Amsterdam], advisor [[Mathematician#PVitany|Paul M. B. Vitányi]]
* [[John Tromp]], [[Mathematician#JShallit|Jeffrey Shallit]] ('''1995'''). ''Subword Complexity of a Generalized Thue-Morse Word''. [https://en.wikipedia.org/wiki/Information_Processing_Letters Information Processing Letters], Vol. 54, No. 6 <ref>[[Max Euwe#ProuhetThueMorseSequence|Prouhet–Thue–Morse Sequence]], [https://en.wikipedia.org/wiki/Prouhet%E2%80%93Thue%E2%80%93Morse_constant Prouhet–Thue–Morse constant from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/Combinatorics_on_words Combinatorics on words from Wikipedia]</ref>
* [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Li:Ming.html Ming Li], [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''1996'''). ''How to Share Concurrent Wait-Free Variables''. [[ACM#Journal|Journal of the ACM]], Vol. 43, No. 4
==2000 ...==
* [[Marcel Crâşmaru]], [[John Tromp]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_16 Ladders Are PSPACE-Complete]''. [[CG 2000]]
* [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''2001'''). ''Randomized Two-Process Wait-Free Test-and-Set''. [http://www.informatik.uni-trier.de/~ley/db/journals/corr/corr0106.html#cs-DC-0106056 CoRR]
* [[John Tromp]], [[Mathematician#PVitany|Paul M. B. Vitányi]] ('''2002'''). ''A Protocol for Randomized Anonymous Two-process Wait-free Test-and-Set with Finite-state Verification''. [http://www.informatik.uni-trier.de/~ley/db/conf/sirocco/sirocco2002.html#TrompV02 SIROCCO]
* [[John Tromp]] ('''2006'''). ''Binary Lambda Calculus and Combinatory Logic''. [http://www.informatik.uni-trier.de/~ley/db/conf/dagstuhl/P6051.html#Tromp06 Kolmogorov Complexity and Applications]
* [[John Tromp]], [[Gunnar Farnebäck]] ('''2006'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-75538-8_8 Combinatorics of Go]''. [[CG 2006]]
* [[John Tromp]], [[Gunnar Farnebäck]] ('''2009'''). ''Combinatorics of Go''. (revised version of the [[CG 2006]] paper), [http://www.google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAA&url=http%3A%2F%2Fhomepages.cwi.nl%2F~tromp%2Fgo%2Fgostate.ps&ei=4c-_TZHrIozbsgbbqeH1Bg&usg=AFQjCNHHe9_yffwPyFYLzlzy9GHGS5EuKw ps]
==2010 ...==
* [[Ingo Althöfer]] ('''2011'''). ''John Tromp in the Style of David Levy: 4-0 win in the Go bet''. [[ICGA Journal#34_2|ICGA Journal, Vol. 34, No. 2]] <ref>[http://dcook.org/gobet/ The Shodan Go Bet]</ref>
* [[John Tromp]] ('''2014'''). ''[https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf Cuckoo Cycle: a memory-hard proof-of-work system]''. [http://www.informatik.uni-trier.de/~ley/db/journals/iacr/iacr2014.html#Tromp14 IACR Cryptology ePrint Archive] <ref>[https://bitcointalk.org/index.php?topic=405483.0 Cuckoo Cycle: a new memory-hard proof-of-work system] by [[John Tromp]], [https://bitcointalk.org/index.php Bitcoin Forum], January 08, 2014</ref> <ref>[https://en.wikipedia.org/wiki/Cuckoo_hashing Cuckoo hashing from Wikipedia]</ref>
* [[John Tromp]] ('''2016'''). ''The number of legal Go positions''. [[CG 2016]]
* [[John Tromp]], [[Matthieu Walraet]] ('''2016'''). ''[[Matthieu Walraet#googolplex|A googolplex of Go games]]''. [[CG 2016]]
=Postings=
* [https://groups.google.com/d/msg/rec.games.chess/pyM6LfZPbvY/DO2V0y4BezIJ entropy of chess positions] by [[John Tromp]], [[Computer Chess Forums|rgc]], April 15, 1991
* [https://groups.google.com/d/msg/computer-go-archive/jlVCk9IRGEY/us3LHpTPCgAJ Number of Go positions computed at last] by [[John Tromp]], [http://computer-go.org/pipermail/computer-go/ The Computer-go Archives], January 22, 2016
* [https://groups.google.com/d/msg/computer-go-archive/sTHY0pBpm0o/3s_YkoUlBQAJ longest 3x3 game] by [[John Tromp]], [https://groups.google.com/forum/#!forum/computer-go-archive Computer Go Archive], February 18, 2016
=External Links=
* [https://en.wikipedia.org/wiki/John_Tromp John Tromp from Wikipedia]
* [https://github.com/tromp tromp (John Tromp) · GitHub]
* [https://tromp.github.io/ John Tromp HomePage]
: [https://tromp.github.io/chess/chess.html John's Chess Playground]
: [https://tromp.github.io/c4/c4.html John's Connect Four Playground] » [[Connect Four]]
: [https://tromp.github.io/go.html John's Go Page] » [[Go]]
: [https://tromp.github.io/go/legal.html Counting Legal Positions in Go], January 20, 2016
: [https://tromp.github.io/pearls.html Programming Pearls]
* [http://amsterdam.academia.edu/JohnTromp John Tromp | University Of Amsterdam - Academia.edu]
* [http://www.computer-go.info/db/operson.php?a=Tromp%2C+John Computer-go.info - Details of Programmer: Tromp, John]
* [https://genealogy.math.ndsu.nodak.edu/id.php?id=66084 The Mathematics Genealogy Project - Johannes Tromp]
* [http://senseis.xmp.net/?JohnTromp John Tromp at Sensei's Library]
* [https://www.linkedin.com/in/john-tromp-b1601b8/ John Tromp | LinkedIn]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Go Programmer|Tromp]]
[[Category:Researcher|Tromp]]
