Synthesis and biological evaluation of some new β-lactam-triazole hybrids.pdfVIP

Combinatorics of Go John Tromp1 and Gunnar Farneb¨ack2 1 CWI, Amsterdam john.tromp@ 2 Laboratory of Mathematics in Imaging, Harvard Medical School, Boston, Massachusetts gunnar@lysator.liu.se Abstract. We present several results concerning the number of posi- tions and games of Go. We derive recurrences for L(m, n), the number of legal positions on an m × n board, and develop a dynamic program- 3 2 m ming algorithm which computes L(m, n) in time O(m n λ ) and space O(mλm ), for some constant λ 5.4. An implementation of this algorithm enables us to list L(n, n) for n ≤ 17. For larger boards, we prove the exis- tence of a base of liberties lim mn L(m, n) of ∼ 2.9757341920433572493. Based on a conjecture about vanishing error terms, we derive an asymp- totic formula for L(m, n), which is shown to be highly accurate. We also study the Game Tree complexity of Go, proving an upper bound on the number of possible games of (mn)L(m,n) and a lower bound 2n2 /2 −O(n) 2n−1 of 2 on n × nboards and 2 on 1 × n boards, in addition to exact counts for mn ≤ 4 and estimates up to mn = 9. Most proofs and some additional results had to be left out to observe the page limit. They may be found in the full version available at [8]. 1 Introduction Go, originating over 3,000 years ago in China, is perhaps the oldest board game in the world. It is enjoyed by millions of players worldwide. It