Mirror games were invented by Garg and Schnieder (ITCS 2019). Alice and Bob take turns (with Alice playing first) in declaring numbers from the set {1,2, ...2n}. If a player picks a number that was previously played, that player loses and the other player wins. If all numbers are declared without repetition, the result is a draw. Bob has a simple mirror strategy that assures he won't lose and requires no memory. On the other hand, Garg and Schenier showed that every deterministic Alice needs memory of size linear in $n$ in order to secure a draw. Regarding probabilistic strategies, previous work showed that a model where Alice has access to a secret random perfect matching over {1,2, ...2n} allows her to achieve a draw in the game w.p. a least 1-1/n and using only polylog bits of memory. We show that the requirement for secret bits is crucial: for an `open book' Alice with no secrets (Bob knows her memory but not future coin flips) and memory of at most n/4c bits for any c>2, there is a Bob that wins w.p. close to 1-2^{-c/2}.
翻译:Garg 和 Schnieder 发明了镜像游戏( ITS 2019) 。 Alice 和 Bob 轮流( 由爱丽丝先玩游戏) 宣布 {1, 2,...... 2n} 。 如果玩家选择了先前玩过的数字, 该玩家会输, 而其他玩家会赢。 如果所有数字都声明不重复, 结果是一幅画。 Bob 拥有简单的镜像策略, 保证他不会输, 不需要记忆。 另一方面, Garg 和 Schenier 显示, 每个确定性爱丽丝都需要以美元为单位的线性记忆, 以图画。 关于概率策略, 先前的工作显示, 一个模式, 爱丽丝可以在游戏 w. p. 至少 1 - 1 / / n 中获取一个秘密的随机匹配, 并且只使用多盘记忆部分。 我们显示, 对秘密比目的要求非常关键 : 对于一个没有秘密的“ 开放书” 爱丽丝( ) ( Bob 知道她的记忆, 但不是未来的翻硬币) ) 以及最多 n/4c bits 的记忆中的n2 。