Как использовать обрезку алфавита для подключения четырех, как игра
Может ли кто-то быть так любезен, чтобы помочь мне понять, как использовать алгоритм отсечения альфа-бета? Я делаю игру, похожую на соединение четырех. Разница лишь в том, что диагонального выигрыша нет, и игрок может пометить квадрат в любой момент времени (если, конечно, он уже не занят). Я думаю, что я понимаю, как кодировать алгоритм, я просто думаю, что я использую его неправильно. Я делал цикл for, который выглядит примерно так:
for(i=0; i<size; i++)
for(j=0; j<size; j++)
val = alphabeta();
if(val > max)
max = val;
move = set(i,j);
setBoard(move); //sets the to the returned value from alphabeta()
проблема, с которой я сталкиваюсь, состоит в том, что первый запуск алфавита возвращает максимальное значение, поэтому ни одно из следующих значений не будет больше, и доска будет просто установлена на board[0][0]. Кто-нибудь знает, что я делаю не так?
public int alphabeta(Placement place, int depth, int alpha, int beta, boolean maxPlayer)
{
Placement p = null;
if(depth==0 || board.isWinner())
{
return evaluate(place, maxPlayer);
}
if(maxPlayer)
{
int i=0, j=0;
for(i=0; i<board.size; i++)
{
for(j=0; j<board.size; j++)
{
if(board.validMove(i,j)&&(board.canGetFour(i,j, opponent)&&board.canGetFour(i,j,player)))
{
board.board[i][j] = opponent;
p = new Placement(i, j);
alpha = Math.max(alpha, alphabeta(p, depth-1, alpha, beta, false));
board.board[i][j] = 0;
}
if(beta<=alpha)
break;
}
if(beta<=alpha)
break;
}
return alpha;
}
else
{
int i=0, j=0;
for(i=0; i<board.size; i++)
{
for(j=0; j<board.size; j++)
{
if(board.validMove(i,j)&&(board.canGetFour(i,j,opponent)&&board.canGetFour(i,j,player)))
{
board.board[i][j] = player;
p = new Placement(i, j);
beta = Math.min(beta, alphabeta(p, depth-1, alpha, beta, true));
System.out.println(board);
board.board[i][j] = 0;
}
if(beta<=alpha)
break;
}
if(beta<=alpha)
break;
}
return beta;
}
}
Это функция, которая делает ход
public void makeMove()
{
int max = -1;
Placement p = null;
int val = -1;
for(int i=0; i<size; i++)
for(int j=0; j<size; j++)
{
if(board.validMove(i, j))
{
if(board.canGetFour(i, j, opponent)||(board.canGetFour(i,j,player)&&board.canGetFour(i,j,opponent)))
{
board.board[i][j] = player;
val = alphabeta(new Placement(i,j), 5, -5000, 5000, true);
board.board[i][j] = 0;
if(val > max)
{
max = val;
p = new Placement(i, j);
}
}
}
}
board.board[p.row][p.col] = player;
board.moves++;
}
Так вот мой обновленный код, все еще не работает
public Placement alphabeta(Placement p)
{
int v = max(p,6,-500000, 500000);
return successors(v);
}
public int max(Placement p, int depth, int alpha, int beta)
{
if(depth == 0 || board.isWinner())
{
return evaluateMax(p,player);
}
int v = -500000;
for(int i=0; i<successors.size(); i++)
{
Placement place = new Placement(successors.get(i));
board.board[place.row][place.col] = player;
v = Math.max(v, min(place, depth-1, alpha,beta));
board.board[place.row][place.col] = 0;
if(v>= beta)
return v;
alpha = Math.max(alpha, v);
}
return v;
}
public int min(Placement p, int depth, int alpha, int beta)
{
if(depth == 0||board.isWinner())
{
return evaluateMax(p,opponent);
}
int v = 500000;
for(int i=0; i<successors.size(); i++)
{
Placement place = new Placement(successors.get(i));
board.board[place.row][place.col] = opponent;
v = Math.min(v, max(place,depth-1, alpha,beta));
board.board[place.row][place.col] = 0;
if(v<= alpha)
return v;
beta = Math.min(alpha, v);
}
return v;
}
public void makeMove()
{
Placement p = null;
for(int i=0; i<successors.size(); i++)
{
Placement temp = successors.get(i);
//board.board[temp.row][temp.col] = player;
p = alphabeta(temp);
//board.board[temp.row][temp.col] = 0;
}
System.out.println("My move is "+p.row + p.col);
board.board[p.row][p.col] = player;
successors.remove(p);
}
Я немного изменил алгоритм, чтобы четко видеть, что происходит с min и max, однако, он все равно не работает правильно
1 ответ
Хорошо, прошло некоторое время, но я думаю, что оно у меня есть.
В вашей функции оценки вы должны возвращать, насколько хорошим является состояние для реального игрока. Если размещение canGetFour для "otherPlayer" это плохое состояние (худшее состояние). Таким образом, вы вернете небольшое число. Тем не менее, если размещение canGetFour для "actualPlayer" вы возвращаете большое число (это хорошее состояние).
Затем в вашем makeMove вы просто проверяете, является ли это состояние наилучшим из возможных. Обратите внимание, что использование 2d-массива для этого является практически наименее эффективным способом хранения "дочерних узлов". Было бы гораздо разумнее иметь размещение. GetPossibleMoves(), которое возвращает массив всех пустых квадратов (как реальных, так и временных), и повторяет их. В противном случае ваш алгоритм будет экспоненциальным по времени в порядке размера доски.
private Placement bestNext;
private List<Placement> tempMoves = new ArrayList<>();
private int alpha;
private int beta;
public int alphabeta(Placement place, int depth, boolean maxPlayer)
{
Placement p = null;
if(depth == maxDepth){/* (unnasigned squares in actual board) */
return evaluate(place, maxPlayer)
}
int i=0, j=0;
for(i=0; i<board.size; i++)
{
for(j=0; j<board.size; j++)
{
if(board.validMove(i,j)){
p = new Placement(i, j);
tempMoves.add(placement);
int tmp = Math.max(alpha, alphabeta(p, depth += 1, actualPlayer.getOpponent()));
if(maxPlayer){
alpha = tmp
}
else{
beta = tmp
}
tempMoves.remove(placement);
}
if(beta<=alpha)
break;
}
if(beta<=alpha)
break;
}
return maxPlayer ? alpha : beta;
}