臺灣博碩士論文加值系統

Connect(m,n,k,p,q) 是一種兩人玩的棋類遊戲。在m乘n的棋盤上，除了第一個玩家在第一步放上q顆棋子外，兩個玩家分別輪流放上p顆棋子。先在棋盤上達成k顆連續的棋子連成一線的玩家就是贏家。舉例來說，五子棋就是Connect(19,19,5,1,1)，六子棋則是Connect(19,19,6,2,1)。我們的論文在探討這類型遊戲的複雜度以及公平性。我們證明了當k>=4p+7且q<=p時，這個遊戲是公平的。我們也證明了當k-p>=max{3,p}時，這類遊戲的難度是PSPACE-complete。

Recently, Wu and Huang[15] introduced a new game called Connect6, where two players, Black and White, alternately place two stones of their own color, black and white respectively, on an empty Go-like board, except for that Black (the first player) places one stone only for the first move. The one who gets six consecutive (horizontally, vertically or diagonally) stones of his color first wins the game. Unlike Go-Moku, Connect6 appears to be fairer and has been adopted as an official competition event in Computer Olympiad 2006.
Connect(m, n, k, p, q) is a generalized family of k-in-a-row games, where two players place p stones on an m×n board alternatively, except Black places q stones in the first move. The one who first gets his stones k-consecutive in a line (horizontally, vertically or diagonally) wins. Connect6 is simply the game of Connect(m, n, 6, 2, 1). In this paper, we study two interesting issues of Connect(m, n, k, p, q): fairness and complexity. First, we prove that no one has a winning strategy in Connect(m, n, k, p, q) starting from an empty board when k >= 4p + 7 and p >= q. Second, we prove that, for any fixed constants k, p such that k-p >= max{3,p} and a given Connect(m, n, k, p, q) position, it is PSPACE-complete to determine whether the first player has a winning strategy. Consequently, this implies that the Connect6 played on an m × n board (i.e., Connect(m, n, 6, 2, 1)) is PSPACE-complete.

1 Introduction and preliminaries 11
2 Fairness 17
3 PSPACE-completeness 23
3.1 Global idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Construction of winning zone and auxiliary zones . . . . . . . 25
3.3 Construction of simulation zone . . . . . . . . . . . . . . . . . 26
3.3.1 Gadgets for vertices . . . . . . . . . . . . . . . . . . . . 27
3.3.2 Gadgets for arcs . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Put it together . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Conclusion and remarks 43
A Drawing 3-planar graphs orthogonally in linear time 45

[1] A.S. Fraenkel, M.R. Garey and D.S. Johnson, The Complecity of Checkers
on an N × N Board - Preliminary Report, In the 19th IEEE Sympo-
sium on Foundations of Computer Science, 55-64, 1978.
[2] S. Iwata and T. Kasai, The Othello game on an n×n board is PSPACEcomplete,
Theoretical Computer Science, 123: 329-340, 1994.
[3] G. Kant, Drawing planar graphs using the canonical ordering, Algorith-
mica, 16(1): 4-32, 1996.
[4] R. Kaye, Minesweeper is NP-complete, Mathematical Intelligencer,
22(2): 9-15, 2000.
[5] D. Lichtenstein and M. Sipser, Go is polynomial-space hard, Journal of
the ACM, 27: 393-401, 1980.
[6] W.-J. Ma, Generalized Tic-tac-toe, http://www.klab.caltech.edu/
~ma/tictactoe.html, 2005.
[7] R.J. Nowakowski, Games of no chance: combinatorial games at MSRI,
Cambridge University Press, 1994.
[8] R.J. Nowakowski, More games of no chance, Cambridge University
Press, 2002.
[9] C.H. Papadimitriou, Computational complexity, Addison Wesley Publishing
Company, 1994.
[10] A. Pluh´ar, The accelerated k-in-a-row game, Theoretical Computer Sci-
ence, 270: 865-875, 2002.
[11] S. Reisch, Gobang ist PSPACE-vollst¨andig (Gobang is PSPACEcomplete),
Acta Informatica, 13: 59-66, 1980.
[12] J.M. Robson, N by N Checkers is EXPTIME complete, SIAM Journal
on Computing, 13(2): 252-267, May 1984.
[13] M. Sipser, Introduction to the Theory of Computation, PWS Publishing
Company, 1997.
[14] H.J. van den Herik, J.W.H.M. Uiterwijk and J. van Rijswijck, Games
Solved: Now and in the Future, Artificial Intelligence, 134: 277-311,
2002.
[15] I.-C.Wu and D.-Y. Huang, A new family of k-in-a-row games, In the 11th
Advances in Computer Games Conference (ACG’11), Taipei, Taiwan,
September 2005.
[16] J. Yolkowski, Tic-tac-toe, http://www.stormloader.com/ajy/
tictactoe.html, 2003.
[17] T.G.L. Zetters, 8(or More) in a Row, American Mathematical Monthly,
87: 575-576, 1980.