Báo cáo toán học: "Potential-Based Strategies for Tic-Tac-Toe on the Integer Lattice with Numerous Directions"

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

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.