为什么我在这个 Nim 游戏中的智能机器人逻辑得到错误的结果

Question

尼姆的游戏。两名玩家交替从一堆弹珠中取出弹珠。在每个动作中，玩家选择要拿走多少弹珠。玩家必须至少拿一个但最多一半的弹珠。拿走最后一个弹珠的玩家输了。该程序在计算机(机器人(和人类之间播放。获胜的策略是选择一个数字，使(2^n)-1留在堆中。大小在 10 和 100 之间随机选择。

在智能模式下，机器人应该选择足够的弹珠，以便堆栈中剩余(2^n)-1弹珠(例如x 3,7,15,31,63..(。除非堆栈中已经有恰好(2^n)-1弹珠，在这种情况下，机器人会选择随机编号。的marbles < (size/2) .相反，我得到以下输出：

Total no. of marbles = 96
Your turn to pick: 
8
Remaining marbles: 88
Bot has selected:4
Remaining marbles:84
Your turn to pick: 
34
Remaining marbles: 50
Bot has selected:12
Remaining marbles:36  and so on..

法典：

int i;
int op=0;   //op becomes 1 when size=(2^n)-1
for(i=2;((2^i)-1)<=size;i++){   //size is total remaining marbles
  if((2^i-1)==size){
      if((size%2)==0){
           sel = rand.nextInt(size/2)+1; //sel is selected no. of marbles
      }
      else{
            sel = rand.nextInt((size-1)/2)+1;
      }
          size = size - sel;
          op =1;
      }
      if(((2^i)-1)<size){
           sel = (2^i)-1;  //in this case sel is required remaining marbles
             op =0;
         }
      }
       if(op==0){
             System.out.println("Bot has selected:"+(size-sel));
             size = sel;
             System.out.println("Remaining marbles:"+size);
       }
       else{
            System.out.println("Bot has selected:"+sel);
            System.out.println("Remaining marbles:"+size);
       }

Answer 1

你首先必须找到比大小小的更大的数字 n 是什么，以便 n = (2^i-1(。这个数字是 - 二进制 - 一个"1"序列，所以你可以用一种聪明的方式来找到它。当你找到它时，你发现你的原始数字是一个"1"的序列，那么你必须得到一个不超过剩余石头一半的随机数。因此，这是确定机器人必须移除多少宝石的函数：

public int stonesToRemove(int size) {
    if (size<=1) 
       return 0; // to avoid exceptions
    int toremove = size;
    int j = 0;
    while (size > 1) {
        j = 1 | j << 1; // this means j=j*2+1
        size >>= 1; // this means size=size/2
    }
    if (toremove == 1+(j << 1)) {
        toremove = 1+new Random().nextInt(j);
    } else {
        toremove -= j;
    }
}

你不需要这么大的迭代，只需要这样的小方法。