Marco van de Wijdeven's AI Article writing contest entry has been published.

Examines how heuristic game tree search can be used in videogames like real-time strategy games. Written from the viewpoint of both AI programmers and gamers, the article provides an over view of concepts as well as a description and analysis of the algorithm.

http://ai-depot.com/GameAI/GameTree.html

Make sure to check out this month's contest! You can win eternal fame, and a prize... well, at least one of the two ;)

I enjoyed reading this article, but it will be nice if you've written more about the heuristic function in Strategic Games (ex: like Starcraft)...

That's right very interesting (from many here) because it's not only a AI current situation's check, it goes beyond.

It's also right that you wait for a next article as some details are missing, so is that planned ?

thanks for this essay.

Hi, nice article you have there ;)
It's exactly what I was looking for, in my game there's a number of computer controled kingdoms that are constantly at war with each other (it's a multiplayer RPG but the kingdoms' AI plays like an RTS), but it's very important that one of them never wins (their frontiers change and all, but they must all be somewhat balanced no matter what)... I never thought I'd really find such a nice aproach to this problem =)

I also agree with Cdc, the best heuristic function I can come up with for a game like this is summing up the number of owned units, kills, and stuff like that (multiplying them by some factor). Is this really the best way to go?

Sorry for never actually checking these comments but better late then never right?

Anyway in response to your question about a suitable strategic heuristic, I'll attempt to give one for an RTS like game.

There are three important things for an AI to know in an RTS game.
How many units does my opponent have? How much units will my opponent have? And where are they right now?

Army strenght is indeed the sum of all units but the strength of an individual unit varies over time. A unit all by itself is much weaker then a unit in a group of units even if it's the same unit!
So a group is stronger then the sum of it's units and an army is stronger then the sum of its groups.

You can reflect this in an heuristic algorithm by adding an extra value on top of the base unit strength. This value will be the total sum of the inverted distances this unit has to any friendly units within a fixed radius.

So: Army strength = E(base unit strength + E(1/distance to friendly))

Note that this is still simplified as most RTS games usually have a paper, rock, sissor system which modifies a units potential strength even more.

Up next is the location of enemy units itself. Basically what you need to do is identify locations that are critical towards the desired win/lose condition. And then calculate how close by enemy units are (with once again the value shift for groups taken into account).
So: Location dominance = E(1/unit distance to critical location + E(1/distance to friendly)

Last we have the potential (not existing yet) army which can be extrapolated from info regarding resources. If the AI knows its opponent controls two resource patches and spotted the amount of harvesters it can determine how much resources the opponent has stored in the bank so to say. Resources that aren't harvested yet are controlled and not owned.
Resources Owned = Income per second*Elapsed Time (in seconds) - observed enemy army cost.

Note that this assumes exact knowledge of resource costs for enemy units.

So the total sum is: Army Strenght + Location Dominance + Resources Owned

Army strength: More units is better, especially when close to each other.
Location Dominance: Having units near important locations is better.
Resources Owned: Having more resources available for spending is better.

Note that Army strength and Location Dominace are related with a negative correlation. If an AI groups all it's units into a single group it has high army strength but low location dominance if there are several critical locations. If only one critical location remains this algorithm will still display the proper behavior (massing all units for the final strike).

I hope this belayed anwser helps out somewhat. Even though it still needs some extra variables to account for more specific gameplay constructs. =)

Hi ,

This was a real good tutorial for game programmers. But Can this be used for real time applications or problem solving where our aim is not to "keep afloat" but to find solution as early as possible? May be in such cases we can keep beta value to maximum.

Thanks,
Abhiman