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.