更多關於Magnus-Derek Game的研究

Abstract

我們針對Magnus-Derek Game這個兩人遊戲做探討. 這個遊戲是在一個n個位置的圓桌上進行. 兩個玩家分別叫做Magnus和Derek. 一開始一個標的物被放在0這個位置. 在每個回合中, Magnus選澤一個m值, 這個值不超過n/2, 為移動標的物的距離; 而Derek選擇標的物的移動方向是順時針或逆時針. Magnus的目標是要讓標的物經過越多位置越好, 而Derek則是要讓標的物經過越少位置越好. 在兩個玩家都用最佳策略的情況下, 我們證明了Magnus可以在O(n)個回合內就達成它的目標, 改進了之前要在O(nlogn)這麼多回合才能達成目標的結果. 我們另外考慮這個遊戲的變型, 在變型的遊戲進行時, 其中一個玩家必須把自己在全部回合中的移動方向或距離先告訴另一個玩家, 而另一個玩家則使用最佳化的策略應對. 在Magnus先告訴Derek他在全部回合的移動距離的情況下, 我們證明Derek有一個O(n^3)時間的演算法來讓標的物經過的位置最少. 在Derek先告訴Magnus他在全部回合的移動方向的情況下, 我們證明Magnus有O(n)時間的演算法來讓標的物經過的位置最多. 我們也考慮兩個玩家都用亂數決定自己走法的情況, 我們證明要經過所有位置所需回合數的期望值是O(nlogn).

We consider the so called Magnus-Derek game, which is a two-person game played on a round table with n positions. The two players are called Magnus and Derek. Initially there is a token placed at position 0. In each round Magnus chooses a positive integer m ≤ n/2 as the distance of the targeted position from his current position for the token to move, and Derek decides a direction, clockwise or counterclockwise, to move the token. The goal of Magnus is to maximize the total number of positions visited, while Derek's is to minimize this number. If both players play optimally, we prove that Magnus, the maximizer, can achieve his goal in O(n) rounds, which improves a previous result with O(nlog n) rounds. Then we consider a modified version of Magnus-Derek game, where one of the players reveals his moves in advance and the other player plays optimally. In this case we prove that Derek has an O(n^3) algorithm to achieve his goal if Magnus reveals his moves in advance. On the other hand, Magnus has an O(n) algorithm. We also consider the circumstance that both players play randomly, and we show that the expected time to visit all positions is O(nlog n).