SIAM Journal on Control and Optimization, Vol.34, No.2, 542-553, 1996
Superior Information Is Insufficient to Win in Games Between Finite Automata
A game between two computers is considered : the first computer generates a binary sequence while the second one tries to predict the next element of this sequence using the previous elements. Both computers operate with the same pool of strategies, which is the set of all boolean functions of N arguments. Notwithstanding the asymmetry of the game, it turns out that the value of the game is zero. An algorithm for choosing an optimal superstrategy for the first computer is proposed, and several generalizations of the game are considered.