# 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 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 .

TÀI LIỆU LIÊN QUAN
32    57    0
45    42    0
6    65    0
4    53    0
6    55    0
6    52    0
6    45    0
5    59    0
7    58    0
6    64    0
TÀI LIỆU XEM NHIỀU
13    32483    1651
3    19354    204
25    18656    3687
20    16759    1476
16    15829    2493
14    14332    2540
37    13043    2802
1    11349    401
3    10964    211
23    10562    384
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
54    37    1    05-07-2022
48    22    2    05-07-2022
5    1    1    05-07-2022
20    16    1    05-07-2022
19    19    1    05-07-2022
150    18    1    05-07-2022
9    22    2    05-07-2022
7    13    1    05-07-2022
9    17    1    05-07-2022
104    9    1    05-07-2022
9    14    1    05-07-2022
7    12    1    05-07-2022
6    13    1    05-07-2022
9    47    2    05-07-2022
5    4    1    05-07-2022
9    26    2    05-07-2022
10    18    1    05-07-2022
40    25    2    05-07-2022
5    11    1    05-07-2022
6    14    1    05-07-2022
TÀI LIỆU HOT
3    19354    204
13    32483    1651
3    1497    75
580    3626    344
584    1957    80
62    4387    1
171    3985    621
2    1743    72
51    2474    150
53    3339    175
Đã 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.