The Number of Legal Go Positions

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10068
• 期：1
• 页码：183-190
• 丛书名：Computers and Games
• ISBN：978-3-319-50935-8
• 卷排序：10068

文摘

The number of legal \(19\times 19\) Go positions has been determined as Open image in new window A roughly 1.2 % fraction of the \(3^{19\times 19}\) total number of positions, this is more naturally expressed in ternary. Replacing the usual ternary digits 0,1,2 by \(+\)(empty), Open image in new window (black), and Open image in new window (white) respectively, yields the following (illegal) position that counts all legal positions: Open image in new windowReferences1.Tromp, J., Farnebäck, G.: Combinatorics of go. In: Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 84–99. Springer, Heidelberg (2007). doi:10.1007/978-3-540-75538-8_8 CrossRefGoogle Scholar2.Wikipedia: Go (game). http://en.wikipedia.org/wiki/Go_(game) 3.Wikipedia: Chinese remainder theorem. https://en.wikipedia.org/wiki/Chinese_remainder_theorem 4.Tromp, J.: The game of Go (website). http://tromp.github.io/go.html 5.Tromp, J.: github repository. https://github.com/tromp/golegal 6.Tromp, J.: Number of legal \(18\times 18\) Go positions computed. One more to go, Hacker News, March 9, 2015. https://news.ycombinator.com/item?id=9167781 7.Tromp, J.: Number of legal Go positions computed, Hacker News, January 22, 2016. https://news.ycombinator.com/item?id=10950875 8.GoBase.org (website). http://gobase.org/ 9.Johnson, L.: After 2,500 years, a Chinese gaming mystery is solved, Motherboard, January 25, 2016. http://motherboard.vice.com/read/after-2500-years-a-chinese-gaming-mystery-is-solved 10.James, M.: Number of legal Go positions finally worked out, IProgrammer, February 3, 2016. www.i-programmer.info/news/112-theory/9384-number-of-legal-go-positions-finally-worked-out.html Copyright information© Springer International Publishing AG 2016Authors and AffiliationsJohn Tromp1Email author1.Stony BrookUSA About this paper Publisher Name Springer, Cham Print ISBN 978-3-319-50934-1 Online ISBN 978-3-319-50935-8 eBook Packages Computer Science About this book Reprints and Permissions Paper actions .buybox { margin: 16px 0 0; position: relative; } .buybox { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; } .buybox { zoom: 1; } .buybox:after, .buybox:before { content: ''; display: table; } .buybox:after { clear: both; } /*---------------------------------*/ .buybox .buybox__header { border: 1px solid #b3b3b3; border-bottom: 0; padding: 8px; position: relative; background-color: #f2f2f2; } .buybox__header .buybox__login { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; letter-spacing: .017em; display: inline-block; line-height: 1.2; padding: 0; } .buybox__header .buybox__login:before { position: absolute; top: 50%; -webkit-transform: perspective(1px) translateY(-50%); transform: perspective(1px) translateY(-50%); content: '\A'; width: 34px; height: 34px; left: 10px; } /*---------------------------------*/ .buybox .buybox__body { padding: 0; padding-bottom: 16px; position: relative; text-align: center; background-color: #fcfcfc; border: 1px solid #b3b3b3; } .buybox__body .buybox__section { padding: 16px 12px 0 12px; text-align: left; } .buybox__section .buybox__buttons { text-align: center; width: 100%; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__buttons { border-top: 0; padding-top: 0; } /******/ .buybox__section:nth-child(2) .buybox__buttons { border-top: 1px solid #b3b3b3; padding-top: 20px; } .buybox__buttons .buybox__buy-button { display: inline-block; text-align: center; margin-bottom: 5px; padding: 6px 12px; } .buybox__buttons .buybox__price { white-space: nowrap; text-align: center; font-size: larger; padding-top: 6px; } .buybox__section .buybox__meta { letter-spacing: 0; padding-top: 12px; } .buybox__section .buybox__meta:only-of-type { padding-top: 0; position: relative; bottom: 6px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__meta { margin-top: 0; margin-bottom: 0; } /******/ .buybox__meta .buybox__product-title { display: inline; font-weight: bold; } .buybox__meta .buybox__list { line-height: 1.3; } .buybox__meta .buybox__list li { position: relative; padding-left: 1em; list-style: none; margin-bottom: 5px; } .buybox__meta .buybox__list li:before { font-size: 1em; content: '\2022'; float: left; position: relative; top: .1em; font-family: serif; font-weight: 600; text-align: center; line-height: inherit; color: #666; width: auto; margin-left: -1em; } .buybox__meta .buybox__list li:last-child { margin-bottom: 0; } /*---------------------------------*/ .buybox .buybox__footer { border: 1px solid #b3b3b3; border-top: 0; padding: 8px; position: relative; border-style: dashed; line-height: 1.3; } /*-----------------------------------------------------------------*/ @media screen and (min-width: 460px) and (max-width: 1074px) { .buybox__body .buybox__section { display: inline-block; vertical-align: top; padding: 12px 12px; padding-bottom: 0; text-align: left; width: 48%; } .buybox__body .buybox__section { padding-top: 16px; padding-left: 0; } .buybox__section:nth-of-type(2) .buybox__meta { border-left: 1px solid #d3d3d3; padding-left: 28px; } .buybox__section:nth-of-type(2) .buybox__buttons { border-top: 0; padding-top: 0; padding-left: 16px ; } .buybox__buttons .buybox__buy-button { } /********** article buybox specific **********/ .buybox.article__buybox .buybox__section:nth-of-type(2) { margin-top: 16px; padding-top: 0; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta { margin-top: 40px; padding-top: 0; padding-bottom: 45px; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta:only-of-type { margin-top: 8px; padding-top: 12px; padding-bottom: 12px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section:first-child { width: 69%; } .buybox.mycopy__buybox .buybox__section:last-child { width: 29%; } /******/ } /*-----------------------------------------------------------------*/ @media screen and (max-width: 459px) { /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__body { padding-bottom: 5px; } .buybox.mycopy__buybox .buybox__section:last-child { text-align: center; width: 100%; } .buybox.mycopy__buybox .buybox__buttons { display: inline-block; width: 150px ; } /******/ } /*-----------------------------------------------------------------*/ Log in to check access Buy eBook EUR 41,64 Buy paper (PDF) EUR 24,95 Instant download Readable on all devices Own it forever Local sales tax included if applicable Learn about institutional subscriptions (function () { var forEach = function (array, callback, scope) { for (var i = 0; i Export citation .RIS Papers Reference Manager RefWorks Zotero .ENW EndNote .BIB BibTeX JabRef Mendeley Share paper Email Facebook Twitter LinkedIn Cookies We use cookies to improve your experience with our site. More information Accept Over 10 million scientific documents at your fingertips