1
我有一个任务，用人类玩家和AI玩家编写NIM游戏。这场比赛是玩“Misere”（最后一个必须拿一根棍子输掉）。人工智能应该是使用Minimax算法，但它的动作让它失去更快，我不知道为什么。现在我已经死了好几天了。 Minimax算法的要点是不会丢失，如果它处于失败位置，则会延迟尽可能多的移动，对吧？NIM游戏和使用Minimax算法的人工智能玩家 - AI让人失去移动
考虑以下几点：
NIMBoard板=新NIMBoard（34，2）;
- 34 =二进制编码棍棒的位置，2桩2根
- 2 =
所以我们这个方案开始桩的数量，较棒的*字符：
Row 0: **
Row 1: **
在这个特定的电路板情况下，Minimax算法总是会提出“从第1行中移除2根支杆”的举动。这显然是一个糟糕的举动，因为它在第0排中留下了2根棍子，其中人类选手可以从第0排中挑选1根棍子并赢得比赛。
AI玩家应该选择从一堆中选择一根。这使得本作的人类玩家：
Row 0: *
Row 1: **
所以无论是哪个移动现在人类球员做，当计算机发出后的下一步行动，人类玩家将总是输。显然这是一个更好的策略，但为什么算法没有提出这一举措？
public class Minimax
{
public Move nextMove;
public int evaluateComputerMove(NIMBoard board, int depth)
{
int maxValue = -2;
int calculated;
if(board.isFinal())
{
return -1;
}
for(Move n : this.generateSuccessors(board))
{
NIMBoard newBoard = new NIMBoard(board.getPos(), board.getNumPiles());
newBoard.parseMove(n);
calculated = this.evaluateHumanMove(newBoard, depth + 1);
if(calculated > maxValue)
{
maxValue = calculated;
if(depth == 0)
{
System.out.println("Setting next move");
this.nextMove = n;
}
}
}
if(maxValue == -2)
{
return 0;
}
return maxValue;
}
public int evaluateHumanMove(NIMBoard board, int depth)
{
int minValue = 2;
int calculated;
if(board.isFinal())
{
return 1;
}
for(Move n : this.generateSuccessors(board))
{
NIMBoard newBoard = new NIMBoard(board.getPos(), board.getNumPiles());
newBoard.parseMove(n);
calculated = this.evaluateComputerMove(newBoard, depth + 1);
// minValue = Integer.min(this.evaluateComputerMove(newBoard, depth + 1), minValue);
if(calculated < minValue)
{
minValue = calculated;
}
}
if(minValue == 2)
{
return 0;
}
return minValue;
}
public ArrayList<Move> generateSuccessors(NIMBoard start)
{
ArrayList<Move> successors = new ArrayList<Move>();
for(int i = start.getNumPiles() - 1; i >= 0; i--)
{
for(long j = start.getCountForPile(i); j > 0; j--)
{
Move newMove = new Move(i, j);
successors.add(newMove);
}
}
return successors;
}
}
public class NIMBoard
{
/**
* We use 4 bits to store the number of sticks which gives us these
* maximums:
* - 16 piles
* - 15 sticks per pile
*/
private static int PILE_BIT_SIZE = 4;
private long pos;
private int numPiles;
private long pileMask;
/**
* Instantiate a new NIM board
* @param pos Number of sticks in each pile
* @param numPiles Number of piles
*/
public NIMBoard(long pos, int numPiles)
{
super();
this.pos = pos;
this.numPiles = numPiles;
this.pileMask = (long) Math.pow(2, NIMBoard.PILE_BIT_SIZE) - 1;
}
/**
* Is this an endgame board?
* @return true if there's only one stick left
*/
public boolean isFinal()
{
return this.onePileHasOnlyOneStick();
}
/**
* Figure out if the board has a pile with only one stick in it
* @return true if yes
*/
public boolean onePileHasOnlyOneStick()
{
int count = 0;
for(int i = 0; i < this.numPiles; i++)
{
count += this.getCountForPile(i);
}
if(count > 1)
{
return false;
}
return true;
}
public int getNumPiles()
{
return this.numPiles;
}
public long getPos()
{
return this.pos;
}
public long getCountInPile(int pile)
{
return this.pos & (this.pileMask << (pile * NIMBoard.PILE_BIT_SIZE));
}
public long getCountForPile(int pile)
{
return this.getCountInPile(pile) >> (pile * NIMBoard.PILE_BIT_SIZE);
}
public void parseMove(Move move)
{
this.pos = this.pos - (move.getCount() << (move.getPile() * NIMBoard.PILE_BIT_SIZE));
}
@Override
public String toString()
{
String tmp = "";
for(int i = 0; i < this.numPiles; i++)
{
tmp += "Row " + i + "\t";
for(int j = 0; j < this.getCountForPile(i); j++)
{
tmp += "*";
}
tmp += System.lineSeparator();
}
return tmp.trim();
}
}
很抱歉的坏格式化，我似乎已经打破堆栈溢出解析器： - \ 下面是我用导出AI玩家的下一步行动： '极小极小=新极小（）;' 换行符 ' int result = minimax.evaluateComputerMove（board，0）;' newline 'return minimax.nextMove;' – RedShift
您确定在人类尽可能好的时候从空中角度挑选最大值的最大值移动，也就是让另一个玩家进入的最坏位置，而不是最小值，这可能是最糟糕的举动吗？ – Davislor
我这么认为，你是说'if（calculated> maxValue）'是不够的，我需要比较其他东西或比较更多？ – RedShift