so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my code to run at a higher depth. However, my code is only given 1 second to run and generate a move and I'm worrying that my ai would not be able to check all the relevant nodes in the designated time. My thought is that I could implement iterative deepening, but I have no idea how to do that (so I really need some inspiration). And also how could I stop my code at a specific time? I want to push my code to the maximum depth if possible.
2
-
$\begingroup$ en.wikipedia.org/wiki/Iterative_deepening_depth-first_search, chessprogramming.org/Iterative_Deepening $\endgroup$– D.W. ♦Commented Mar 31, 2023 at 18:14
-
$\begingroup$ Thank you that is helpful, but how do I define time in a function/thread? Is there a way to stop a function when a specific time runs up? $\endgroup$– WolfkingCommented Mar 31, 2023 at 19:23
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
When you implement alpha-beta pruning, it is important to try the best moves first. To do this, you evaluate one move and sort the moves from best to worst. Then you evaluate two moves, trying moves in the order you found by one move, and sort again. Then three moves and so on.
In C or C++ you can use the clock() function which returns the time spent in the current thread, in multiples of CLOCKS_PER_SEC. So after evaluating a move, you check the time and estimate how likely it is to finish in the time you have.
If you absolutely need to finish in the given time, you run the calculation in a separate thread which updates the best result so far, and set a timer to display the best result after one second.
Note that clock() stops counting when the thread is not running, so if your computer is very busy it might take longer until clock() increases by more than a second. clock_gettime() might help.
$\begingroup$
$\endgroup$
2
As far as I know, it is not possible to achieve that exactly unless you are running a hard-real-time operating system (which neither Windows nor Linux are).
Anyway, you can obtain close to this behavior by one of two methods:
internal timing: choose one or more check points in your algorithms, that are frequently passed through and where you read the wall-clock time*. When the desired delay is reached, or a little before, let the algorithm terminate. The difficulty is to find a point where the algorithms passes frequently enough. The maximum running time between two passings should not exceed the desired time accuracy. This may pose a challenge if the algorithm behaves irregularly or at a pace that depends on the input data.
external timing: you can launch the algorithm in an auxiliary thread and start a timer synchronously (waiting call). Upon timer expiry, kill the auxiliary thread. There are two technicalities involved:
you must make sure that the algorithm can be interrupted at any time; in case the algorithm updates a list of results, the update must be made atomically, i.e. cannot be interrupted in the middle of a sequence of modifications that temporarily breaks data coherence.
you must make sure to regain control when the auxiliary thread is effectively killed, so that it won't change the results after the fact.
With all solutions, the system load may cause extra latencies; they cannot be avoided.
*Alternatively you can start a timer asynchronously (non-waiting call) and periodically check whether it has elapsed or not.
-
$\begingroup$ check clock_gettime() which can return the time since your computer started, on an M1 Mac under MacOS with 1/24th of a microsecond resolution. That should work on Linux as well. Don’t know about Windows. There is one clock that stops when the computer goes to sleep, and one that keeps running. $\endgroup$ Commented Mar 31, 2023 at 20:38
-
$\begingroup$ @gnasher729: under Windows (PC), see QueryPerformanceCounter. $\endgroup$– user16034Commented Mar 31, 2023 at 21:04
$\begingroup$
$\endgroup$
check all the relevant nodes in the designated time.
You will never be able to check all the nodes. The whole point of iterative deepening is that you search just a part of the tree, and return the best answer you have so far once time runs out. There are therefore two different problems to consider:
- Making sure the program runs within the given time.
- Having the program return the best solution found so far.
To address 1, you need an if-statement at the start of your loop that simply measures the time that has elapsed so far and if the program has less than 0.001s remaining to make a move, then it will return immediately. You can adjust the 0.001s threshold as needed.
To address 2, you use iterative deepening. In iterative deepening, you first search the game tree up to depth 1. The heuristic will be evaluated at depth 1 nodes. The best result for depth 1 is stored somewhere. Then you do the same thing for depth 2. Replace the depth 1 result with depth 2's result. And so on, you keep raising the depth by 1 and exploring the game tree only up to that depth and saving the best solution. If you are running out of time, you immediately return the best solution found so far.
