+- Ludii Forum (https://ludii.games/forums)
+-- Forum: Questions (https://ludii.games/forums/forumdisplay.php?fid=13)
+--- Forum: About Ludii (https://ludii.games/forums/forumdisplay.php?fid=14)
+--- Thread: move selection in Alpha-Beta search (/showthread.php?tid=1454)
move selection in Alpha-Beta search - Tester001 - 02-03-2023
When using the Alpha-Beta-AI in the Ludii player, it always gives a response about how deep it could go in the search tree.
This is valuable information to assess the quality of moves (i guess) but what does it really mean for the task of move-selection ?
For example if for some game it takes 60 sec to calculate to reach depth 10 (resulting in move A),
and would maybe need another 40 sec to get to 'complete search of depth 11' (resulting in move B).
Would the selected move be the same after 80 seconds (move A) when the next depth could not be checked completely ?
Or stated otherwise: Will the selected move always be the same for a certain depth, or can the extra seconds make a difference?
I tested some Alpha-Beta games and the correlation of depth & moves seemed to be very strong in the Ludii player algorithm.
RE: move selection in Alpha-Beta search - DennisSoemers - 02-04-2023
Extra seconds do not make a difference if they do not end up leading to a new search depth. Whenever the agent runs out of processing time, it selects the move that it thinks is best based on the deepest depth for which it was able to *completely* search the tree.
It's not entirely accurate to say that the move selected will always be the same for the same search depth though. Sometimes there can be multiple different moves that are all equally evaluated as "best moves", and the agent may randomly pick among them (not exactly just randomly, but there can be a random component in this tie-breaking). Aside from that little detail, yes, it will always pick the same move (or pick from the same set of multiple best moves) for the same search depth.
RE: move selection in Alpha-Beta search - Tester001 - 02-04-2023
Interesting! Thanks for the explanation.
I saw in my tests that the extra seconds brought nothing even if they were minutes and was wondering why a move with 'better evaluation' (in some sense) than the best of the last complete depth is not chosen in the end.
Because when the next depth is not finished and although there might be an even better move, the best move from 'extra time' could still be better than everything else found for the last finished depth, I thought. ok.
Yes, the random possibility for equal eval I understand. (as in UserGuide Appendix B7)
So when I have two different .lud encodings (with different runtime leading to different depths) of one game they should still give the same best move when I increase the time for the slower one to match the 'completed depth' of both, is this right?
(in cases when equally evaluated moves can be ruled out* with very high probability)
If the rate of different best move at same depth would be high this would be a hint to an error in one of the two lud files, I guess.
Regards, Franz
*It would be nice to have the output of such an evaluation parameter for AlphaBeta like in UCT, if possible.
RE: move selection in Alpha-Beta search - DennisSoemers - 02-04-2023
> So when I have two different .lud encodings (with different runtime leading to different depths) of one game they should still give the same best move when I increase the time for the slower one to match the 'completed depth' of both, is this right?
Ehm, yes I think that sounds right. Can't think of any reason right now anyway that this wouldn't be the case. Except if the differences in encoding are so substantial that "depth" no longer has the same meaning across the two implementations. For example, you might have one description of Chess where a single move is a full movement of a piece from a current site to a destination (as in our in-built version of Chess), and another description of the same game where one move is first to just "select" a piece, and selecting the destination to move it towards is modelled as a separate move altogether. In the latter model of the game, you'd have to search twice as deep to get the same results as in the former model.
RE: move selection in Alpha-Beta search - RogerCooper - 03-12-2023
It would be good if we could specify the search depth when using Alpha-Beta. The human player could get a more consistent level of play, even though the time to move would be variable.
RE: move selection in Alpha-Beta search - Tester001 - 03-13-2023
Yes, I thought of that, too. But it's copmlicated.
You have to know the behaviour of a game very well to use this wisely, otherwise the ludii.player '.. will be lost, in time'.
Therefore it could be a good option to combine the desired depth with a maxTime-value, as usual.
If you set this very high, then you get what you want.