Have the AI continue to work in the background, planning its moves. Since your moves aren't done though, it obviously can't be in a final state. So examine what potential moves the player can do, and determine what the best course of action would be.
It's kind of like Chess, except that the AI plans its moves while you're still doing your turn, so that there is less waiting around when it's actually the AI's turn.