Monday, February 1, 2010

Alpha-Beta Weaknesses

The AI for two person games can be created using the alpha-beta (AB) algorithm. AB generates ALL possible moves in the future until the game has ended but usually that is impossible so you have to use an evaluation function which looks at the current game position and tries to calculate which player is winning and by how much. Obviously creating a good evaluation function can be very complicated. The "heart" of the AB algorithm is the evaluation function.

(Sorry for a little bit of review but I just wanted to make sure that everyone is on the same page.)

While AB has been very successful when applied to chess, AB is not without its weaknesses. AB does not have a "game plan", such as trying to maximize the value of Wrath of God. AB just looks ahead and picks a good move. The AB algorithm may appear to have a game plan which would give AB some "human characteristics". The best kind of AI is both challenging and realistically acts like a human opponent. (Depending on the specific game the AI may do something that a human player would never do which ruins the illusion of playing against another person. And yes I've had this happen to me while I was playing Forge.)

While AB does not do any planning, there are other algorithms that use goal-directed reasoning or planning. Unfortunately these types of algorithms seem 100 times more complicated than AB since they need more information. Reasoning and planning algorithms need to have knowledge about the game and the ability to generate or choose from a variety of plans.

Through trial and error, AB can be combined with planning algorithms which would allow the best of both worlds. Maybe AB could handle combat while the planning algorithm could choose an overall plan such as playing a creature every turn or effectively using Royal Assassin.

p.s.
If Forge 2 ever got AB working, it would be fun to let people tweak the evaluation function to see how it helps or hurts the AI's performance.

Anonymous said...

(AB) algorithm, sounds interesting, but when evaluating the game state does the AI have knowledge of the cards in the player's hand or deck?

Forge said...

The answer is that it depends on the exact implementation. At first I plan to not allow the AI to cheat and look at the cards in his opponents hand. Later, I might let the AI cheat and do that.

Right now I doubt that allowing the AI to do that would improve the AI's performance since it might make the AI perform worse since it creates too many possible future states.

Forge said...

And maybe letting the AB algorithm view the cards in his opponent's hand would improve the AI? I know that this "cheating" sound really bad and people are initially against it but if it helps the AI, I'm all for it.

And maybe the AI could see a few cards in your hand, which is similar when playing the 2nd or 3rd games of a match where you have seen a few cards that are in your opponent's deck.

The downside is that the AB algorithm is hard to program.

chicago information technology master degree said...

Fastest way to become a master hacker” There is no fast way. Most “master hackers” are self taught and have natural ability to hack. You need to understand the workings of the computer and networks in depth before even beginning to think of programming. You also need have excellent logistical/analytical skills and be naturally good at maths