koobas.hobune.stream
Call long running AI function without tying up game loop?
I'm writing a board game where players take turns at making moves. I have a recursive search function that looks for all the possible moves x turns deep & returns the best move for a player.
I need the AI to be able to call this function to pick it's move but without freezing up the main game loop.
// psuedo code (though I'm actually writing in c#)
function PickBestMove(forPlayer: byte): IMove { // looks through all the possible moves for "forPlayer" // finds the best achievable score for each move // and returns the move with the best score }
function GetBestAchievableScore(forPlayer: byte; searchDepth: byte): int { // if searchDepth is zero returns the score for "forPlayer" // for each possible move for "forPlayer" get the score for // each move by calling GetBestAchievableScore recursively // until we reach our search depth. // this function is where MOST of the time is spent }
My first thought was to throw some yields into my search function and call my PickBestMove like a coroutine but of-course you can only yield if it returns IEnumerator.
I'm a little stumped as to how/if I can turn my function into a coroutine, given there's actually 2 functions involved and one is recursive. Is this possible and if so can you show some example code please?
Otherwise will I need to pick the best move in a separate thread? Is unity cool with using mulitple threads?
I'd prefer to turn it into a coroutine rather than a separate thread if the code is still simple enough.
Though not exactly the approach you're after, here's an approach I might try:
Convert your recursive routine into an iterative one. You do this by maintaining your own stack (or queue) of work to be done, and rather than having the function call itself for sub-branches of the search, it instead just throws them onto the work stack.
If you make this work stack (probably implemented an ArrayList containing some sort of "GameState" objects) a property of the AI object, rather than a local variable, then you can make a function that does just a little bit of work at a time -- say, pulls one item off the work stack, examines it, and then either pushes the result up to the parent node, or pushes child nodes onto the stack.
This will be a quick function that you can call from Update() or some such, so it doesn't tie up the UI.
Of course if you're not used to thinking about the problem in this way, a thread will seem easier. I generally approach all my recursive problems this way anyway, because it gives me more control (e.g., using recursion pretty much limits you to a depth-first search, whereas with your own work queue you can go best-first). And also, I'm still a Unity newbie and don't know much about threads yet. So, I hope this is helpful.
I had considered the possiblity of rewriting the function from being recursive to a loop and holding info in a stack, though I've never written a function that way (when it could be done simplier recursively). But I figured this would be a lot of work and messy (though I could be wrong?) and hoped a recursive coroutine/thread approach would be easier if possible. But the way you explained it sounds interesting and I'll give it some thought. Cheers. :)
Well, I since learnt it is indeed possible to call coroutines recursively but in theory it would create a lot of allocations (creating lots of objects implementing IEnumerator). So I decided to give your idea a try. Turned out to be easier than I thought and works. One unexpected issue was that it turned out to be twice as slow as my original recursive function but still only doing the same amount of work from what I can tell. Have you noticed this when you implement functions this way vs recursively?
In other languages I've used, there was little or no difference in performance. But I haven't done this yet in C#. From what you say, it sounds like the overhead of creating/destroying those GameState objects is higher than the overhead of method calls.
If it's a problem, there are ways you could speed it up by recycling those objects. If ArrayList is pretty fast at pushing and popping objects (as I certainly hope it would be!), you can just keep a separate ArrayList "recycling pool," and ins$$anonymous$$d of letting objects you pop off the work queue be destroyed, push them onto that ins$$anonymous$$d. HTH!
Yeah it's wierd, I actually figured the non-recursive method would be faster. In my non-recursive coroutine I know how deep I need to go so I just create an array of gamestates of that length (depth) at the start once and therefore don't do extra allocations/pushing/popping at each "recursion" and yet it's still slower. Hopefully it's something I've done wrong & overlooked and not some inescapable truth, hehe. Time to do some profiling! Thanks for your help :)
