我有一個任務,用人類玩家和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