Design How do you manage intensive AI?

Joh

Member
So I built an AI for a card game, It essentially simulates all possible moves, then simulate opponent for as deep as desired.
Problem is run time of course. Such a kind of simulation is exponential and just very intensive. I would like for it to be seamsless because the environment animates and a freeze is a bad look.
At first I was using a recursion based approach:
  • duplicate state
  • perform move
  • simulate that new state. (recursion)
Problem is i cant be interupted, cut short or spread out, have to wait until all recursions are resolved to get the move.
So I thought of creating a "manager" that gather all the states and can linearly launch their execution. (scores are recursively propagated up at the end)
Clear advantage is now it doesn't have to fully run in 1 step.

My great disappointment is it still dips framerate/performance.
Now instead of freezing until all recursions are done, it slowly runs slower until all states are done.
The approach is still flexible though, so I was hoping there was a way to minimize impact?
  • Iter high: If i make many (1000) states simulation per step, it freezes (becomes like recursive approach)
  • Iter low: If I make it 1 state per step, it doesnt freeze but gradually slows down to a crawl.
  • spread: I made it so I could spread the steps: (run simulations every X steps) and that limited how slow it could get. but selecting the move takes noticable time.
  • steptime: I also have time breaks using current_time, automatically breaks out if simulation ran longer than 100ms in one step. <- is that too much?
  • fulltime: I also have a break and play once the total move selection time is too long, but I'd rather it was never needed.
Mixing and matching these parameters leads to different performances, but its hard to get a feel of what is ideal.

Anyone ever dealth with state tree AI? Anyone has an idea on how to best spread to load?
Thanks
 

HalRiyami

Member
There are a couple of ways you can deal with this. Async multithreading or by performing the calculation in the spare step time.

I don't have any experience with multithreading so all I can say (don't quote me on this) is that the way you would do it is by having the main loop run an the primary core (as is typical) and when the calculation is needed, fire off an async command with all pertinent data using an extension to a secondary core and wait on a response without pausing the main loop. Again, I don't know how this is done in GMS.

Your other option is to redesign the AI algorithm so that it work in the spare time you have each step. You'll want to know the delta time of the previous frame (or just use room speed), measure how long it takes to perform everything up to the AI and how long it takes to perform everything after the AI. Once you have these 3 pieces of info you can figure out how long the AI can run before it slows down the game. Simply time your algorithm after each state and if it exceeds that allotted time, save the progress and break then continue the next step.
 
  • Like
Reactions: Joh

Yal

šŸ§ *penguin noises*
GMC Elder
I coincidentally watched a bunch of videos on this type of thing recently:



The main takeaways are:
  • Assume the opponent will always make a good move, that way you can eliminate at least half the branches in your search tree (and maybe more depending on the good-vs-bad moves ratio)
  • Randomness is underrated, 50% chance to make a smart move is better than some more thoughtful approaches that makes a bad move almost all the time
  • Good Reliable is better than Perfect Too Late, if you have timing constraints you could just sort a "best move so far" list and when the time is up, you pick the best move you found. (The drawback is that players with a worse PC gets worse AI, so you probably need some metric of the least allowable number of considered states before you settle on a move)
 
  • Like
Reactions: Joh

Padouk

Member
Such a kind of simulation is exponential and just very intensive
From your description, I'm assuming you are implementing a derivative form of MinIMax Algorithm.
The idea here is to prune your tree and explore only relevant part of it. minimax is the keyword for your research and you can have a look at https://forum.yoyogames.com/index.php?threads/gmtactician-collection-minimax-devkit.79614/ if you haven't alreardy to see how the asynchrone can be implemented in GMS.

So I thought of creating a "manager" that gather all the states and can linearly launch their execution. (scores are recursively propagated up at the end)
Clear advantage is now it doesn't have to fully run in 1 step.
Yup that's the way to go for any CPU bound long running process.. Break it in few Steps, and run a few Steps per frames. That's what you have to do... Yey!

Now instead of freezing until all recursions are done, it slowly runs slower until all states are done.
With what you describe here, i'm assuming you are doing a Breath first search instead of a Depth first search, trying to complete a full Level of the tree at each "Step"
First Step works on lvl 1... it has 1 states to check ... Runs for X ms
2nd Step works on lvl 2... it has 2 states ... Runs for 2X ms.
3rd Step works on lvl 3 .. it has 4 states ... Runs for 4X ms..
...
so your 10th step probably takes 1024X ms.


If you are using minimax, each step should end up taking the same time due to pruning...
If you really want to look at all possible states, the only thing I would change in your approach is to unroll your Recursion and Convert it back to a sequential form.
So each "Step" runs on the same amount of branches
First Step works on 10 states (lvl 1 (1) + lvl2 (2) + lvl3 (4) + part of lvl 4)
2nd Step works on 10 states (part of lvl 4 + part of lvl 5)
...
so the 10th step still take the same amount of time than step 1

Mixing and matching these parameters leads to different performances, but its hard to get a feel of what is ideal.
  • Iter high: If i make many (1000) states simulation per step, it freezes (becomes like recursive approach)
  • Iter low: If I make it 1 state per step, it doesnt freeze but gradually slows down to a crawl.
Answer depends on your player's CPU.... So ask your player's CPU for the answer...
Instead of configuring the number of steps, you should configure the target delta_time (or fps)

Stat with "fair" amount of state like Iter = 100,
Then look at your fps_real or delta_time...
if it's still in bellow your target Iter += 10 to process slightly more states in your upcomign steps, speeding up the process for player with budget.


  • spread: I made it so I could spread the steps: (run simulations every X steps) and that limited how slow it could get. but selecting the move takes noticable time.
I don't see the value of that one, sorry

  • steptime: I also have time breaks using current_time, automatically breaks out if simulation ran longer than 100ms in one step. <- is that too much?
  • fulltime: I also have a break and play once the total move selection time is too long, but I'd rather it was never needed.
I wouldn't.. this would give a different gameplay experience for slower computer... It does not make sense to me.












Have an object keeping track of the work queue.





More specifically i'm pointing you to the Step function of his pseudo-daemon implementation. https://github.com/dicksonlaw583/GM...ects/__obj_gmtactician_mm_daemon__/Step_0.gml







I coincidentally watched a bunch of videos on this type of thing recently:



The main takeaways are:
  • Assume the opponent will always make a good move, that way you can eliminate at least half the branches in your search tree (and maybe more depending on the good-vs-bad moves ratio)
  • Randomness is underrated, 50% chance to make a smart move is better than some more thoughtful approaches that makes a bad move almost all the time
  • Good Reliable is better than Perfect Too Late, if you have timing constraints you could just sort a "best move so far" list and when the time is up, you pick the best move you found. (The drawback is that players with a worse PC gets worse AI, so you probably need some metric of the least allowable number of considered states before you settle on a move)
 
  • Like
Reactions: Joh

FrostyCat

Redemption Seeker
I've done this before on MCTS and Minimax, and the code I wrote for these have been used in 3 different GMC Jam entries.

Instead of using plain recursion, I converted the algorithm to iterative by simulating the call stack. That way it can be batched into ticks that are minimally blocking, and the process can be stopped simply by not processing more ticks. Minimax had to be converted like this, MCTS is already iterative.

To minimize lags caused by too many ticks at once, I used TCP Reno's congestion control algorithm to dynamically adjust the rate. The tick rate increases linearly as long as fps_real is more than some multiple of room_speed, but halves if it isn't. That way there is no use for fixed rates that vary from hardware to hardware.
 
  • Like
Reactions: Joh

Joh

Member
Woah, lots of feedback, thanks a lot!

There are a couple of ways you can deal with this. Async multithreading or by performing the calculation in the spare step time.

I don't have any experience with multithreading so all I can say (don't quote me on this) is that the way you would do it is by having the main loop run an the primary core (as is typical) and when the calculation is needed, fire off an async command with all pertinent data using an extension to a secondary core and wait on a response without pausing the main loop. Again, I don't know how this is done in GMS.

Your other option is to redesign the AI algorithm so that it work in the spare time you have each step. You'll want to know the delta time of the previous frame (or just use room speed), measure how long it takes to perform everything up to the AI and how long it takes to perform everything after the AI. Once you have these 3 pieces of info you can figure out how long the AI can run before it slows down the game. Simply time your algorithm after each state and if it exceeds that allotted time, save the progress and break then continue the next step.
Im not sure there's multithreading with GMS and that might be overkill for a somewhat simple project, but yeah doing calculaions in spare time is what I was aiming for, balancing it out seems like the hard part. As you and everyone proposed timing the process and adjusting accordingly seems like the best way.

I coincidentally watched a bunch of videos on this type of thing recently:

The main takeaways are:
  • Assume the opponent will always make a good move, that way you can eliminate at least half the branches in your search tree (and maybe more depending on the good-vs-bad moves ratio)
  • Randomness is underrated, 50% chance to make a smart move is better than some more thoughtful approaches that makes a bad move almost all the time
  • Good Reliable is better than Perfect Too Late, if you have timing constraints you could just sort a "best move so far" list and when the time is up, you pick the best move you found. (The drawback is that players with a worse PC gets worse AI, so you probably need some metric of the least allowable number of considered states before you settle on a move)
Funnilly enough, i was assuming best plays (wasn't deleting bad branches yet, but that was part of the plan.) But now I'm thinking of rating wih weighted sums since if I can't reach W/L leaf node, the estimation of good moves is not necessarily good.
And playing against humans who will try optimal moves but will eaily miss it at times accounting for some (estimated)bad branches might be good.
Due to mistakes, my thoughtful approach made lots of bad moves. now I think its fixed, but I'll also add randomness for sure!
And yes I do have the pickbest at time constraint, but I hadn't considered it means worse AI for bad PCs, interesting point.

@Padouk & @FrostyCat
Yes, what I did is essentially minimax (or MCTS?) off the top of my head, hadn't even occured to me to look if it had been done before.
Looking at the FrostyCat exemples it's beautiful! Bookmarked and will definitely use If I ever need an Ai again. If i cant fix my attempt, ill bite the bullet and start over with this as a base.
With what you describe here, i'm assuming you are doing a Breath first search instead of a Depth first search, trying to complete a full Level of the tree at each "Step"
First Step works on lvl 1... it has 1 states to check ... Runs for X ms
2nd Step works on lvl 2... it has 2 states ... Runs for 2X ms.
3rd Step works on lvl 3 .. it has 4 states ... Runs for 4X ms..
...
so your 10th step probably takes 1024X ms.


If you are using minimax, each step should end up taking the same time due to pruning...
If you really want to look at all possible states, the only thing I would change in your approach is to unroll your Recursion and Convert it back to a sequential form.
So each "Step" runs on the same amount of branches
First Step works on 10 states (lvl 1 (1) + lvl2 (2) + lvl3 (4) + part of lvl 4)
2nd Step works on 10 states (part of lvl 4 + part of lvl 5)
...
so the 10th step still take the same amount of time than step 1
Im doing the second way but with no pruning(yet).
each steps always run the same number of states say 10. Why it becomes slower is (I Assume) due to doing Intense frames in a row. If I do the same 10 states but space them out (this is the spread parameter): 10 states once every 20 frames, then there isnt a fps drop (at least noticable one) problem with that is if I do 10 states per 20 frames, it will take forever to get anywhere.
I wouldn't.. this would give a different gameplay experience for slower computer... It does not make sense to me.
The difference in gameplay hadn't occured to me. However it is important in a case where it just doesn't run well (ideally performance would be fixed) If I have a 30sec limit per turn (for player) the AI should under no circumstances ever break that 30sec limit, fairness/integrity be damned. (plus odds are no better move would be found with more time)

To minimize lags caused by too many ticks at once, I used TCP Reno's congestion control algorithm to dynamically adjust the rate. The tick rate increases linearly as long as fps_real is more than some multiple of room_speed, but halves if it isn't. That way there is no use for fixed rates that vary from hardware to hardware.
Seeing some of the other feedback, I was looking into taking the fps into account and adjust the tick count. making it dynamic is a great idea, I was thinking decreasing it when fps drops, but increasing it while its fine is smart!

Thanks a lot everyone!
 
Top