Improved strategy for Derek in the minimal variant of the Vector game

Abstract

In the minimal variant of the Vector game, the game is played at a circular table with n seats also called positions consecutively labelled from 0 to n−1. At start, a single token is placed at position 0. The two players, called Magnus and Derek, jointly control the token. If the current position is i, a round consists of Magnus choosing a positive distance l ≤n/2, then Derek deciding if the token moves clockwise or anticlockwise. Magnus’s aim in the game is to minimize the cardinality of the set of all positions occupied in the course of the game (while Derek’s is to maximize it).Let α(n) denotes the eventual size of the occupied set if both players play optimally. The focus of this paper is on a strategy for Derek to achieve at least α(n) visited positions in a small number of rounds (α(n)2 rounds) no matter how Magnus plays.

Keywords

• Combinatorial games
• Mobile agents
• Optimal strategies
• Algorithms
• Data structures