The accelerated κ-in-a-row game

被引:13
作者
Pluhár, A [1 ]
机构
[1] Univ Szeged, Dept Comp Sci, H-6720 Szeged, Hungary
基金
匈牙利科学研究基金会;
关键词
positional games; Maker-Breaker version; derandomization; kappa-in-a-row;
D O I
10.1016/S0304-3975(01)00115-3
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We investigate two versions of the well-known k-in-a-row game. While in the most intriguing k = 5 case the outcome of the game has been recently settled, very little is known about what happens when the rules are changed. A natural modification is that the players take more than one square of the board per move in order to speed up the game. Our main goal is to improve the quadratic bound on the error term, given by Csirmaz in Csirmaz (Discrete Math. 29 (1980) 19-23), to a logarithmic one for the accelerated k-in-a-row. The other issue is the extreme sensitivity of k-in-a-row under biased rules. Beck proposed in Beck (unpublished lecture notes) that a player may trade some of his freedom of choice for the right of taking more squares than his opponent. We prove logarithmic bounds on the error term in that case, too. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:865 / 875
页数:11
相关论文
共 11 条
[1]  
Allis L. V., P 1993 AAAI FALL S G, P1
[2]   VANDERWAERDEN AND RAMSEY TYPE GAMES [J].
BECK, J .
COMBINATORICA, 1981, 1 (02) :103-116
[3]  
BERLEKAMP ER, 1982, WINNING WAYS, V2, P667
[4]  
CSIRMAZ L, 1980, DISCRETE MATH, V29, P19
[5]  
Erdos P., 1973, Journal of Combinatorial Theory, Series A, V14, P298, DOI 10.1016/0097-3165(73)90005-8
[6]  
Guy R. K., 1979, AM MATH MONTHLY, V86
[7]  
Guy R.K., 1980, Amer. Math. Monthly, V87, P575
[8]  
Hales A. W., 1963, Trans Amer. Math. Soc, V106, P222, DOI 10.2307/1993764
[9]  
Pluhar A., 1997, Acta Cybernetica, V13, P77
[10]  
PLUHAR A, UNPUB RECYCLED KAPLA