I use to play Descent (by Interplay, I think) all the time. My basic strategy was to rush into an area, thus stirring up all of the bots and then retreating to a corner somewhere and wait for them to come and get me. Then, one by one, I’d pick them off. This strategy worked very well for the first several levels. Then, all of a sudden, the bots stopped coming after me. I’d wait for a few moments and they wouldn’t show up, so I’d start back to where the bots were to see what was wrong and they would be waiting in an ambush for me, generally right around the corner from where I was hiding. Descent claimed to have an AI that learned and adapted to the player. Whether or not they did, what tools do you think would be used in implementing this kind of behavior (neural nets, fuzzy logic, simple state machine, basic if-else statements)? I guess it would have to collect inputs about how the human player plays the game and determine a way to use this information to its advantage. Maybe it would coordinate with other computer-controlled players to take advantage of the human player’s weaknesses. Any ideas? Thanks.

The basic idea of machine learning is to classify behaviour based on observations of the player actions. You need a scheme for describing that behaviour in a finite set of variables and then a partitioning of the domain of those variables to represent the different behaviours.

From there the task is to observe the players actions and determine which behaviour is being enacted and thus choose an appropriate response. There are various ways of doing this.

Offline methods involve training an ML algorithm (such as an artificial neural network) using a large set of training cases. The problems with this approach are 1) that it is often difficult to generate a reasonable training data set; and, 2) that if the player performs actions that the network has not been trained on it cannot correctly classify that behaviour.

An online method usually involves reinforcement learning. The NPC agents pick actions from a finite set and try these in the domain. The outcome of the action is scored and this scoring influences which actions are chosen next. A classifier system is a good example of this class of algorithm. Reinforcement learning usually also employs some form of search algorithm to generate new possible actions/plans based on the current set, so that the agent has some form of innovation and doesn't always repeat the 'best of a bad bunch' of actions.

If you're interested in Machine Learning, there are many excellent references out there. Try google or perhaps even Amazon.

Cheers,

Timkin

[edited by - Timkin on June 16, 2002 11:52:43 PM]

Have you looked at the source code?
Of course they have a license about not using it for revenue.

I was unaware they released the source code.

Timkin,

That is kind of what I thought they did, but it seems almost too simplistic to be useful. I figured there had to be a better way.

quote:

---

Original post by spiffgq
I was unaware they released the source code.

Timkin,

That is kind of what I thought they did, but it seems almost too simplistic to be useful. I figured there had to be a better way.

---

There''s never anything wrong with "simple". If a simple solution provides the behavior you want out of your computer players, why overdo it?

"I''ve never seen that. I''ve never seen anybody drive their garbage down to the side of the street and bang the hell out of it with a stick. I''ve never seen that."

Once you find it(d1srcpc.exe-1,510,364 bytes) and unpack it, the ai code is in /MAIN.

AI.C is 133 KB large, so I wouldn''t call it simplistic.

After reading through it I can tell you that they do exactly as Timkin has described.

quote:

---

Original post by spiffgq
That is kind of what I thought they did, but it seems almost too simplistic to be useful. I figured there had to be a better way.

---

The concept may seem simple... and there are certainly some very simple schemes that do very basic machine learning of a few behaviours form a small, predefined set, however...

... the real fun/difficulty/intersting AI comes about when you allow the player a multitude of actions, some or all of which may have countably infinite outcomes. Descent is an interesting environment because the player is limited to a few control variables with which they can perform an infinite variety of actions. Many of these though will be very similar... and this is the classification you are looking for.

Why don''t you take a look at the Descent AI code and see if you can figure out exactly the learning scheme they used. From there you can play with the AI to see how it performs differently in the game... that''s a great way to get a good understanding of it!

Good luck,

Timkin