I have a card game that I am analyzing with Maple. Actually, it's a series of card games, one for every parameter k, where k is a natural number (representing the number of ranks of cards used in the game). For small k, it is feasible to completely solve the game by "reverse induction". I am trying to create an AI that will play optimally from this.
Given a winning position (and it being the computer's turn) the computer can answer quite easily with any move that takes the position to a losing one for the player. However, what to do with a losing position? It turns out, picking a random move is a terrible strategy. Is there some way to make life very difficult for our poor human player? One idea I had was to make it choose a move that maximizes the length of the minimum path needed for the player to win the game. That would seem to avoid getting into all the psychology of what human weaknesses are in the game etc.
I am aware that this problem is completely general (does not depend on the game). Does anyone have any references for someone interested in learning about AI in this setting?
Thanks!
I think your idea of maximizing the least number of moves your opponent needs to win is basically sound. However, I'd refine it a bit and suggest that you try to maximize the search depth your opponent needs to find a winning response to your next move, assuming that they use the same search strategy as you do.
The basic idea is that, if your opponent knows the optimal strategy, they'll win and there's nothing you can do about it. Thus, you should assume that they don't know it.
What should you assume they know, then? Well, in the absence of evidence otherwise, it's generally better to overestimate your opponent than to underestimate them, so a conservative assumption would be that your opponent just barely failed to see the winning response to at least one of your possible moves. This suggests that you should figure out which move that was and play it.
The complication here, of course, is that your opponent might recognize certain moves as winning ones based on heuristics or prior information, without necessarily having to search all the way to the final victory. This is particularly likely when playing against a human: we make a lot of use of heuristic rules and prior experience. Thus, simply maximizing the number of turns to your opponent's victory may not be a very good strategy, as some of those turns might be very easily predictable even for a rather "dumb" opponent.
On the other hand, assuming that you've already taken some effort to come up with a fairly efficient search algorithm tuned for the specific game you're playing, you might as well assume that your opponent is probably doing something similar. Thus, assuming that you're essentially playing against a just slightly weaker copy of yourself seems to give you a fairly good chance of winning, assuming that you have one at all.