我已经完成了与人类玩家和AI玩家一起编写NIM游戏的任务 . 该游戏是“Misere”(最后一个必须选择一根棒) . 人工智能应该是使用Minimax算法,但它正在进行移动,使其失去更快,我无法弄清楚为什么 . 我已经连续几天走到了尽头 . Minimax算法的目的是不输,如果它处于失败状态,延迟失去尽可能多的动作,对吧?
考虑以下:
NIMBoard board =新的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();
}
}
2 回答
你认为对AI来说更好的举动实际上并不是一个更好的举措 . 在那种情况下,人类玩家将从第1行中拿出两根棍子,并且计算机仍然卡在最后一根棍子上 . 这并不能保证您的程序正常运行,但我认为您应该尝试一些不同的测试用例 . 例如,如果您认为人工玩家会失败的情况,请查看AI的作用 .
你不应该为人类玩家提供不同的功能 . 你应该假设两个玩家都使用最好的策略,因为你实现它,它应该是两个玩家相同的代码 .
该算法的思想不是将状态id分配给当前状态,该状态id等于最小状态id,该状态id不会与您可能最终的状态的任何状态id重叠 . 如果你可以使用ids 0,1和3进行移动并达到状态,那么当前状态应该具有状态ID 2.任何丢失状态都应该具有id 0 .
如果你当前的状态是状态ID为0,你就不会失去你做出的任何动作 . 否则你可以找到一个移动,将棋盘移动到id为0的状态,这意味着其他玩家将会失败 .