How to design an AI For Sorry?

Question

Context: I'm working on a Windows console version of the board game Sorry. In Sorry, each player has four pawns. Based on drawn cards, a player moves their pawns around the board. These moves can impact other players' pawns, like bumping another player's pawn back to Start.

Problem: Along with human players, I want to have computer players. Thus, I'm trying to write a simple, but smart, AI. When taking its turn, each computer player gets the current board state and a collection of possible new board states to choose from, based on the drawn card and the different legal moves that can be made. A board state is a collection of Pawn objects, which know their position on the board.

Ideas:

Idea #1: My first AI idea was to convert each board into a numeric value, and choose the largest value as the best possible move. To produce a value, I gave each of the player's pawns a value and summed the values together. A pawn's value increases as it approaches home. The trouble with this approach is that it neglects an opponent's relative strength in the game. For instance, if the player has two pawns, it will always choose to move the one that advances closer to home. However, the farther one could bump an opponent's pawn back to Start, which may be a better choice.

Idea #2: My second idea was to sum deltas of board state. Specifically, for each new board state, determine its score via pawn position (a la idea #1) but do that for all players. Then compare those values to the current board's state to get deltas and sum the deltas. This would allow me to calculate the improvements to the player's position and any loses to an opponent's position. Trouble here is we're not accounting for whether we're leading, or if an opponent is leading. Sorry'ing an opponent who I'm easily beating is probably not worth it.

Question: Is this a reasonable approach for a Sorry AI that can be improved, or is there a better way to do this?

Answer 1

You have good start. Each AI needs to be able to figure out "value" of current board. But it is often not enough. This is because calculating good "value" heuristic might be complicated and often current state of the board won't give you full idea about possible future developments.

This is where algorithms that try to predict future exist. In your case, simple ExpectiMinMax algorithm (which is extension of classical MinMax with probability) should be enough. Simply said this algorithm tries to calculate as many possible future state as possible and figure out what is best current move based on that information.

In your case, the random nodes can easily be calculated from what cards remain to be picked and then all player's options for each card. Given that search space is relatively small, you could probably search huge amount of games for each turn.