Names of AI searches.

trevbang · Post by **trevbang** » Thu Oct 12, 2006 1:32 pm

Is there a specific name for an AI that searches all solutions and calculates the probability of victory for each path. Then chooses the path with the highest probability of victory.

Also is there a name for an AI that chooses the path with victory in the least number of turns.

As of now I will just be calling them Probabilities and Quick-Win. The other method I will be comparing is Min-Max.

pgordon · Post by **pgordon** » Fri Oct 13, 2006 11:13 am

Hello trevbang,

A complete game tree is an AI tree that contains all possible moves from each position. A partial game tree is an AI tree that has been pruned to eliminate poor decision paths.

It would depend on what type of game your AI is playing but often it could be very difficult or almost impossible to calculate the probability of victory because winning is such a binary outcome and is dependant on the other players move. Using Kalah as an example the AI should calculate its moves based on capturing the most stones while at the same time having the opponent's best possible move capture the least stones. The AI would then evaluate each of its current options and rate the moves based on a given algorithm. It may also be very hard to test what you call a Quick-Win AI in Kalah because of how the game is setup.

I am trying to explain within the scope of your project. If you can post more details about which different AI methods you are planning on testing I could provide you with more specific answers. Good Luck.

Vlad Verishnakov · Post by **Vlad Verishnakov** » Fri Oct 13, 2006 1:12 pm

Hello trev bang. You should trying doing a comprehensive data search using info trac at your school on the data tree.

trevbang · Post by **trevbang** » Fri Oct 13, 2006 1:24 pm

Those are the three types of searches I will be comparing (Probabilities, Quick-win, and Min-Max). I am hypothesizing that the min-max will be the most effective but I want to see how it reacts in different situations because min-max may only be effective against an opponent who has perfect play and can judge the values of all positions. That is pretty much optimizing your position while minimizing your opponents.

My Quick-win search will follow the path that captures over half the stones the quickest because after over half the stones are captured the game is won and any move after that doesn't matter. This may work well against human opponents as it will take the whole game by storm but will probably lose against the probabilities one.

The probability search will label all end game nodes as wins and losses and assign the ration to each branch. The program will choose the branch with the greatest win percentage. This too make work well against an untrained human because they are less likely to choose the winning move.

The point of my research is not to make a perfect Kalah AI but rather to better understand how different AIs work and what makes them efficient against different types of opponents.

ChrisG · Post by **ChrisG** » Sat Oct 14, 2006 12:40 pm

Hi Trevbang, I like your idea of comparing algorithms. You might be interested to read this:
http://graphics.stanford.edu/~irving/pa ... _kalah.pdf

They solved Kalah for all combinations up to (not including) 6 pits and 6 seeds. Today, computers are somewhat faster than when they did their work, but it sounds like the solution for 6 pits and 6 seeds is still out of reach, even for them. So, you will probably need to use a simplified version of Kalah (like 6 pits, 3 seeds), or a more simple game. You might also need to use limited versions of the algorithms so that they don't all win against human competitors 100% of the time.

trevbang · Post by **trevbang** » Sun Oct 15, 2006 6:42 pm

ChrisG wrote:Hi Trevbang, I like your idea of comparing algorithms. You might be interested to read this:
http://graphics.stanford.edu/~irving/pa ... _kalah.pdf

They solved Kalah for all combinations up to (not including) 6 pits and 6 seeds. Today, computers are somewhat faster than when they did their work, but it sounds like the solution for 6 pits and 6 seeds is still out of reach, even for them. So, you will probably need to use a simplified version of Kalah (like 6 pits, 3 seeds), or a more simple game. You might also need to use limited versions of the algorithms so that they don't all win against human competitors 100% of the time.

Thanks! I actually have already read that and spoken to Geoffrey Irving about it. It was partially why I finally decided to use Kalah as my base.