Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Asymptotically optimal pairing strategy for Tic-Tac-Toe 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 dành cho các bạn yêu thích môn toán học đề tài:Asymptotically optimal pairing strategy for Tic-Tac-Toe with numerous directions. | Asymptotically optimal pairing strategy for Tic-Tac-Toe with numerous directions Padmini Mukkamala Domotor Palvolgyi Rutgers New Jersey Eotvos University Budapest Submitted May 29 2010 Accepted Sep 19 2010 Published Oct 15 2010 Mathematics Subject Classification 91A46 Abstract We show that there is an m 2n o n such that in the Maker-Breaker game played on Zd where Maker needs to put at least m of his marks consecutively in one of n given winning directions Breaker can force a draw using a pairing strategy. This improves the result of Kruczek and Sundberg 15 who showed that such a pairing strategy exists if m 3n. A simple argument shows that m has to be at least 2n 1 if Breaker is only allowed to use a pairing strategy thus the main term of our bound is optimal. 1 Introduction A central topic of combinatorial game theory is the study of positional games the interested reader can find the state of the art methods in Beck s Tic-Tac-Toe book 4 . In general positional games are played between two players on a board the points of which they alternatingly occupy with their marks and whoever first fills a winning set completely with her his marks wins the game. Thus a positional game can be played on any hypergraph but in this paper we only consider semi-infinite games where all winning sets are finite. If after countably many steps none of them occupied a winning set we say that the game ended in a draw. It is easy to see that we can suppose that the next move of the players depends only on the actual position of the board and is deterministic.1 We say that a player has a winning strategy if no matter how the other player plays she he always wins. We also say that a player has a drawing strategy if no matter how the other player plays she he can always achieve a draw or win . A folklore strategy stealing argument shows that the second player who puts his first mark after the first player puts her first mark as ladies go first cannot have a winning strategy so the best .