Jump to content
  • Advertisement

StepTNT

Member
  • Content Count

    12
  • Joined

  • Last visited

Community Reputation

111 Neutral

About StepTNT

  • Rank
    Member
  1. I'll try it, thanks.   Do you have any hint on the negascout code that I wrote? I tried it and it seems to work but I'm not that sure.
  2. I want understand how it works, but some things does not make sense to me because taking things from different sources leads to some inconsistencies. Now, I split the method in that two because I thought that the "if node is the first child" thing was always true in the root search.   Now I think I got it right and I understood that the if means that I need to do a different kind of search for the first child of each node and not only for the root, so I came up with this code, hoping that I got it right now. protected MoveValue executeSearch(double alpha, double beta, int depth) { MoveValue bestMove = null; ArrayList<Move> moves = sortMoves(generateLegalMoves(playerType)); boolean isFirstChild = true; for (Move move : moves) { board.applyMove(move); if (bestMove == null) { bestMove = new MoveValue(); bestMove.returnMove = move; } double score; if (isFirstChild){ isFirstChild = false; score = -negaScout(-beta, -alpha, depth - 1, playerType.opponent()); } else { score = -negaScout(-alpha-1, -alpha, maxDepth - 1, player.opponent()); //null window if (score > alpha && score < beta){ score = -negaScout(-beta, -score, maxDepth-1, player.opponent()); } } board.undoLastMove(); if (score > alpha) { bestMove = new MoveValue(score, move); alpha = score; } } return bestMove; } protected double negaScout(double alpha, double beta, int maxDepth, MarbleType player) { if (!canContinue()) { return 0; } if (maxDepth == 0 || board.isGameOver()) { double value = currentHeuristic.evaluateBoard() * (player.equals(Black) ? -1 : 1); // Tried this line in a MinMax and solved the original problem of the topic so I've put it here too. return value; } boolean isFirstChild = true; ArrayList<Move> moves = sortMoves(generateLegalMoves(player)); for (Move move : moves) { board.applyMove(move); double score; if (isFirstChild){ isFirstChild = false; score = -negaScout(-beta, -alpha, depth - 1, playerType.opponent()); } else { score = -negaScout(-alpha-1, -alpha, maxDepth - 1, player.opponent()); //null window if (score > alpha && score < beta){ score = -negaScout(-beta, -score, maxDepth-1, player.opponent()); } } board.undoLastMove(); alpha = Math.max(alpha, score); if(alpha > beta){ break; } } return alpha; }
  3. I'm just ignoring that value, the search is performed by a separate thread and when 0 is returned the main method as already returned the best move. Can you please tell me how to fix the code? Because it's copied from wikipedia and I don't know how to fix that null-window thing.
  4. Right, I followed Wikipedia's pseudcode and I came up with this code. The executeSearch method is the root search (the else branch in the pseudocode) while negaScout is the whole method without that else branch. I hope I got everything right now! protected MoveValue executeSearch(double alpha, double beta, int depth) { MoveValue bestMove = null; ArrayList<Move> moves = sortMoves(generateLegalMoves(playerType)); for (Move move : moves) { board.applyMove(move); if (bestMove == null) { bestMove = new MoveValue(); bestMove.returnMove = move; } double score = -negaScout(-beta, -alpha, depth - 1, playerType.opponent()); board.undoLastMove(); if (score > alpha) { bestMove = new MoveValue(score, move); alpha = score; } } return bestMove; } protected double negaScout(double alpha, double beta, int maxDepth, MarbleType player) { if (!canContinue()) { return 0; } if (maxDepth == 0 || board.isGameOver()) { double value = currentHeuristic.evaluateBoard() * (player.equals(Black) ? -1 : 1); // Tried this line in a MinMax and solved the original problem of the topic so I've put it here too. return value; } ArrayList<Move> moves = sortMoves(generateLegalMoves(player)); for (Move move : moves) { board.applyMove(move); double score = -negaScout(-alpha-1, -alpha, maxDepth - 1, player.opponent()); if (score > alpha && score < beta){ score = -negaScout(-beta, -score, maxDepth-1, player.opponent()); } board.undoLastMove(); alpha = Math.max(alpha, score); if(alpha > beta){ break; } } return alpha; }
  5.   Well, how can I make them work together then? I'll rewrite the method using 2 different methods, one for the root and one for the children, so that I don't need to edit Wikipedia's method but I'm really struggling to understand how to add TT later.   I think I'll edit this post with the code without TT as soon as I finish writing it
  6. Before doing something wrong again, I've mixed the PVS pseudocode found on Wikipedia with your code on NegaScout + TT taken from this post. I've edited it a little bit to make it return a a move and it's value instead of returning just the value.   Can you please tell me if it's correct so that I can get back to the heuristic problem? MoveValue NegaScout(Board &b, int depth, int alpha, int beta) { if (depth<=0) return new MoveValue(static_eval(b, depth)); HashEntry *he = hash_search(b); if (he != 0) { if (he->depth >= depth) { // Don't use the score otherwise switch (he->flag) { case LOWER_BOUND: alpha = max(alpha, he->score); break; case UPPER_BOUND: beta = min(beta, he->score); break; case EXACT_SCORE: return he->score; } if (alpha>=beta) // return alpha; return he->entry; } } List<Moves> moves = sort(getLegalMoves()); MoveValue bestMove = null; for each move of moves{ if child is not first child{ score := -NegaScout(b, depth-1, -alpha-1, -alpha) (* search with a null window *) if alpha < score < beta (* if it failed high, score := -NegaScout(b, depth-1, -beta, -score) do a full re-search *) } else { score := -NegaScout(b, depth-1, -beta, -alpha) } if (score > alpha){ // Update best move and alpha alpha = score; bestMove = new MoveValue(score, move); } if alpha >= beta break ; } HashFlag flag = (bestMove.score <= alpha) ? LOWER_BOUND : (bestMove.score >= beta) ? UPPER_BOUND : EXACT_SCORE; store_hash(b, depth, score, flag, bestMove); return bestMove.score; }
  7. I'll take some time to read and understand your answer but I'll give you more details on this:   executeSearch starts the search from the root. This is needed because the standard negaScout returns a numeric value while I need a Move (wrapped inside the MoveValue class). The function takes both alpha and beta because it extends a class which requires this signature but, from the pseudocode found online, I don't need them   double best = Double.MIN_VALUE; is used to give a low value before starting the search. I know I should use Double.NEGATIVE_INFINITY but using it gave odd results and I reverted to MIN_VALUE   double score = -negaScout(best, best, depth - 1, 0, playerType.opponent()); I found this code somewhere online, I can't find the source again but it happened to work for the black player so I thought it was correct   "Speaking of which, where is `alpha' used in this function?" Considering that the main call is executeSearch(Double.MIN_VALUE, Double.MAX_VALUE, depth), alpha and best should be the same thing. I could use just alpha, but my source used this code and so I did   I'm checking canContinue everytime to avoid going deeper if it's not needed, so that the thread that's doing the search can terminate fine.   "Your evaluation function is expected to return a score from the point of view of the player to move." Actually I'm starting to have some doubts because the software that I'm using as reference shows the same scores despite the player that I'm using   "You could call undoLastMove here, instead of doing it in three different places further down" I'm not undoing it because it may happen that the result is outside the scout window so I need to make a full search for the same move   "Operators -- and ++ don't do what you think they do" And you're right, this one was really really noobish. I'll fix them ASAP     I would use them if only the evaluation function won't return a double :)
  8. Here's the code I'm using for the negaScout. I've added transposition tables, history sorting and null move pruning. protected MoveValue executeSearch(double alpha, double beta, int depth) { MoveValue bestMove = null; double best = Double.MIN_VALUE; ArrayList<Move> moves = sortMoves(generateLegalMoves(playerType), 0); Iterator<Move> movesIterator = moves.iterator(); while (movesIterator.hasNext() && canContinue()) { Move move = movesIterator.next(); board.applyMove(move); if (bestMove == null) { bestMove = new MoveValue(); bestMove.returnMove = move; } double score = -negaScout(best, best, depth - 1, 0, playerType.opponent()); board.undoLastMove(); if (score > best) { bestMove = new MoveValue(score, move); } } return bestMove; } protected double negaScout(double alpha, double beta, int maxDepth, int currentDepth, MarbleType player) { if (!canContinue()) { // This happens when time's up so we don't need to go on. return 0; } if (maxDepth == 0 || board.isGameOver()) { return currentHeuristic.evaluateBoard(); } long hash = ZobristKey.generateHash(); HashEntry entry = transpositionTable.get(hash); if (entry != null) { if (entry.depth >= currentDepth) { switch (entry.flag) { case LOWER_BOUND: { alpha = Math.max(alpha, entry.score); break; } case UPPER_BOUND: { beta = Math.min(beta, entry.score); break; } case EXACT_SCORE: { return entry.score; } } if (alpha >= beta) { return alpha; } } } // Null move pruning double nullValue = -negaScout(-beta, -beta - 1, 0, 0, player.opponent()); if (nullValue >= beta) { updateTranspositionTableEntry(nullValue, alpha, beta, currentDepth, hash); return nullValue; } ArrayList<Move> moves = sortMoves(generateLegalMoves(player), currentDepth); double scoutWindow = beta, currentValue = alpha; Iterator<Move> movesIterator = moves.iterator(); while (movesIterator.hasNext() && canContinue()) { Move move = movesIterator.next(); board.applyMove(move); double score = -negaScout(-scoutWindow, -currentValue, maxDepth--, currentDepth++, player.opponent()); if (score > currentValue) { currentValue = score; } if (currentValue >= beta) { board.undoLastMove(); // History sorting based on prunings int prunings = 0; if (historyTable.containsKey(move)) { prunings = historyTable.get(move); } historyTable.put(move, prunings++); break; } if (currentValue >= scoutWindow) { currentValue = -negaScout(-beta, -currentValue, maxDepth--, currentDepth++, player.opponent()); if (currentValue >= beta) { board.undoLastMove(); // History sorting based on prunings int prunings = 0; if (historyTable.containsKey(move)) { prunings = historyTable.get(move); } historyTable.put(move, prunings++); break; } } scoutWindow = currentValue++; board.undoLastMove(); } updateTranspositionTableEntry(currentValue, alpha, beta, currentDepth, hash); return currentValue; } isBlackPlayer means that we searching a move for the black player, but I'm starting to suspect that this is completely wrong :D
  9. Isn't what you're suggesting the same of doing double evaluate(){ ... return (isBlackPlayer) ? (black - white) : (white - black); } Because this is what I tried without success.
  10. I cannot post the code but I can post some pseudocode and explain how things should work. I've not included more details in the question because I thought I was missing some easy thing and I hoped you could enlighten me, never thought of a bug in my code.   So, the game is Abalone and here's how the heuristic is supposed to work:   compute the center of mass for black marbles, call it Cb compute the center of mass for white marbles, call it Cw compute the geometric mean between Cb, Cw and C (which is the center of the board) and call it R compute the sum of the distances between each black marble and R, call it Db compute the sum of the distances between each white marble and R, call it Dw the result of the evaluation function should be Db - Dw This is based on AbaPro and it's explained better here (my version is a little bit simple but the idea is the same).   Now, why is the result Db - Dw? The idea is to minimize the distance from the center for the player's marbles and maximize the opponent's one, so, assuming that the player is the black one, a good result is when Db < Dw and this leads to a negative score which is fine because I have double score = -negaScout(...) so the lowest negative score will be the better one for my negaScout code.   When the player is the white one I'd expect to have a good result when Dw < Db, but having Db - Dw as result of the evaluation leads to a positive score in this situation and, given the previouse line of code, this positive result will be the worst one for the negaScout.   I've tried switching to Dw - Db when I play as the white player but it still doesn't work somehow and I don't know why.   Of course I'm not asking you to solve the problem without having the full code, but I need to know if the idea is correct or if I was wrong since the beginning.
  11. I'm working on an AI for a 2-players board game and I ran into this issue: when my AI plays for the black player everything goes smooth, but when I decide to use it to play for the white one it chooses the worst possible move. I've tried changing the sign of the result when it plays as the white player but it still doesn't work. The heuristic that I'm using is taken from a working software which doesn't distinguish between black and white when it coms to evaluate the board, so I don't get why it doesn't work for me. Is there something that I'm not aware of? Do I need to do some changes in my negaScout based on what's my Ai's player?
  12. I'm working on an AI for a board game and I ended up using negaScout with TT. Now I'm starting to think on how I can improve it and, even if my understandings of how TT works are quite limited, I came up with this question: since my AI will play against other people's AIs, does it make sense to run a full game against a strong AI, store the TT and then load it before starting the new game? Will it cause more prunings and make everything faster for the next games?
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!