Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic đề tài: Potential-Based Strategies for Tic-Tac-Toe on the Integer Lattice with Numerous Directions. | Potential-Based Strategies for Tic-Tac-Toe on the Integer Lattice with Numerous Directions Klay Kruczek Western Oregon University kruczekk@ Eric Sundberg Occidental College sundberg@ Submitted May 29 2009 Accepted Dec 18 2009 Published Jan 5 2010 Mathematics Subject Classification 91A46 Abstract We consider a tic-tac-toe game played on the d-dimensional integer lattice. The game that we investigate is a Maker-Breaker version of tic-tac-toe. In a MakerBreaker game the first player Maker only tries to occupy a winning line and the second player Breaker only tries to stop Maker from occupying a winning line. We consider the bounded number of directions game in which we designate a finite set of direction-vectors Sc Zd which determines the set of winning lines. We show by using the Erdos-Selfridge theorem and a modification of a theorem by Beck about games played on almost-disjoint hypergraphs that for the special case when the coordinates of each direction-vector are bounded . when S c v v ro k Breaker can win this game if the length of each winning line is on the order of d2 lg dk and d2 lg k respectively. In addition we show that Maker can build winning lines of length up to 1 o 1 d lg k if S is the set of all direction-vectors with coordinates bounded by k. We also apply these methods to the n-consecutive lattice points game on the Nd board with essentially S Zd and we show that the phase transition from a win for Maker to a win for Breaker occurs at n d o 1 lg N. 1 Introduction The traditional game of 3 X 3 tic-tac-toe is a type of positional game. In particular 3 X 3 tic-tac-toe is an example of what we call a strong positional game. In general a positional game is a two-person game with complete information played on a hypergraph V H where V is an arbitrary set called the board of the game and H is a family of subsets of V called the winning sets. The two players Player 1 and Player 2 alternately occupy previously unoccupied elements of V. In a
