I'm in the research stage of programming a hockey game, and my ambition is pretty high. I'm aiming at a purely physics-based gameplay engine (using biases for things like possession and shot accuracy), but that's almost an entirely different animal. Ultimately, I think it would be interesting to compile a fuzzy logic system for AI agents within the game. That way, rather than a cut-and-dry FSM-based reaction, I'm hoping for a more "human" reaction from the AI. I understand that these reactions are all based on calculations to begin with, but I'm hoping for something a little more unpredictable than "If Player A has possession of the puck, then Player B should try to check him." I think "Player A is a 'good' shooter, and Goalie B is a 'bad' goalie, so Defenseman C should challenge Player A." The question is: would it be worthwhile -- processing speed, actual effect on agent intelligence and reaction, etc -- to implement this kind of system, or would I really be better off using a simplistic FSM model? Am I barking up the wrong tree, or have I not gone quite far enough? Thanks for any answers or further ideas you may have. -will anything i say should be taken with a grain of salt. a really really big grain. maybe an entire salt lick. you know, like in old yeller...never mind. don''t trust my words. [edited by - mojo pin on August 22, 2003 4:17:25 PM]

"Player A is a ''good'' shooter, and Goalie B is a ''bad'' goalie, so Defenseman C should challenge Player A."

that sounds like you just want a more complex FSM that the "If Player A has possession of the puck, then Player B should try to check him." FSM. I don''t see why you can''t just implement a more complex FSM to do what you have described...

FuSMs can be used in ways such as determining whether or not to be in an offensive mode or a defensive - or somewhere in between. Factors can be combined in various ways. Where are we on the ice? Which team has the puck? Where are my players? Where are the other team''s players? What is the score? How much time is left on the clock? Each of these could be represented by a value that contributes to the overall score... that score would then be thrown against a FuSM algorithm to determine which of a number of states that a player should be in. For example:

(+ is offensive, - is defensive)
I am a forward. +1
My team has the puck. +3
I am in neutral ice. +1
The puckhandler is behind me. 0
3 of our players are in our own zone. -2
4 of the other team''s players are in THEIR own zone. +1
We are up by 2. -1
It is late in the 3rd period. -1

The total in the above example is +2. Let''s say that translates into "slightly offensive" - the 2nd of 5 categories. We could then pass that parameter into a further state machine that helps us decide what SPECIFIC act we should take given the SPECIFIC situation. In this case, we would want to wait in the neutral zone for the puckhandler to catch up and maybe even kill some time.

Now... change the game situation:

I am a forward. +1
My team has the puck. +3
I am in neutral ice. +1
The puckhandler is behind me. 0
4 of our players are in our neutral ice. +3
1 of the other team''s players are in THEIR own zone. +1
We are down by 1. +2
It is late in the 3rd period. +2

We now have a +13! That would obviously be "very offensive" meaning that we have a whole new set of states to choose from.
A good choice here would be to charge the line looking for a leading pass from the puckhandler... or maybe waiting for him to cross over the blue line so we can get into scoring position.

Obviously, there are places to combine some of the above into their own algorithms. The score/time remaining category for example. If it is late in the 3rd, you may have either an offensive or defensive state depending on the score. That can be done in a couple of ways, though. The bottom line is that a lot of this stuff would need to be "rolled up" into the final decision making process... and rather than using the static, rigid nature of FSMs, you can make for smooth transitions and many possible outcomes by combinging response curves and FuSMs.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Dave has presented a specific solution idea for the class of problems that this hockey game AI falls into. Essentially, you want to define a mapping from states to actions. Consider the different variables that Dave mentioned; let''s assume there are n of them. If you were to assume they were independent, you could plot an n -dimensional vector given the specific values of them. You can see that you could conceivably have quite a lot of possible combinations and thus vectors to plot. Imagine that you put a dot in your n -dimensional space at the end of each vector (so now the variable values are coordinate values). The problem you are faced with is deciding what action to take given a specific location in your n -dimensional space.

Dave has highlighted one approach, which is to map the specific n -dimensional point to a single dimension based on then signed coordinate distance from the origin to the dot (the sum of the coordinate values). This greatly simplifies the decision problem. Additionally, by utilising a fuzzly classifier, dots from the same region of the state space map to the same decision outcome. This is a useful way of dealing with the complexity of such a problem.

One particular difficulty in this sort of AI problem comes in determining the decision boundaries. These are the surfaces embedded in your n -dimensional space that separate sets of dots such that, when mapped into your lower dimensional decision space, the different sets map to different decisions.

You can choose these boundaries yourself (based on expert opinion), you can learn them from data, or you can evolve them based on the quality of the decisions that they produce given the states. This is a whole research area in itself, but thankfully there is plenty of literature out there on how to solve this sort of problem.

Besides FuSMs, you can try other sorts of classification/clustering algorithms to develop and utilise the decision boundaries. Alternatively, you can try a probabilistic approach. I wont go into details about this sort of approach as it is rather detailed, needless to say that again, there is plenty of literature out there on it (and I''m happy to explain further if needs be).

The other way to look at this problem is from the planning perspective (although you wouldn''t implement a planning system to solve this problem, other than perhaps a reactive planner, a la Pengo). What you are trying to create is a universal (conditional) plan, also called a policy. This policy provides the optimal action for each state the agent can be in. Given the size of the state space and the number of interacting agents in the game (making it an extremely dynamic environment), you don''t want to try and solve for the optimal policy before run time.

This means that you are left with the task of approximating the optimal policy during execution. Not an easy task.

Finally, here''s my actual suggestion...

Break your state space down into sub-spaces and constrain decisions within these sub-spaces. So, for example, treat the location, velocity and facing of all of the players on the ice, as well as the puck, as one sub-space (affects the influence of other agents on the decision); treat the game time, score, player fatigue, etc as another sub-space (affects ''pressure/stress'' of the state); etc. You can break it down which ever way you like.

Then, within each of these sub-spaces come up with a (set of) decision(s). You then need some way of choosing from conflicting decisions between these sub-spaces. For example, the location of the players on the ice might suggest that the current agent moves forward, however the time pressure of the situation and the scroe line might suggest dropping back. This is like having two assistant coaches making recommendations on the sidelines. The governing AI needs to choose between the two options. This model is known as a mixture of experts . Again, you can assign rules for preferencing one expert over another, or you can learn relationships based on performance. While the latter approach is tougher, it gives very good results. For example, such approaches have been used very successfully in automated intruder detection and repulsion systems for computer networks.

I know I''ve written a lot above and there''s a lot to take in. However, you should know (and hopefully realise by now) that this problem is a massive one and draws on lots of different research areas from AI. Don''t be put off by this. You can produce a system that plays hockey and you might even be able to produce a system that plays hockey well!

Good luck!

Timkin

"Fuzzy Logic" is, sometimes, just another name for "score-based rule sets."

Thus, the different actions may lead to different outcomes, and those outcomes are scored based on current knowledge of the game, which typically is measured using scalars, not booleans. (seconds since taking possession, meters from the goal, degree of occlusion along passing line, etc).

I wish fup had dropped into this. I happen to know he is working on a soccer (football) simulation for his next book.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Easily fixed Dave!

Wow, thanks a lot for the very detailed responses, they''re much appreciated! I''m normally not one to cut corners when in comes to learning different techniques in programming, but there are so many options on the table that I had to get some additional opinion. I''m definitely taking all those suggestions into account, and hopefully I''ll have some results soon. Again, thanks for the input, because it''s a great community response like this that keeps a forum interesting and informative instead of a slam-fest on supposed "newbies" for wording their questions in ways that make them seem uninformed. Also, for long, run-on sentences like that one.

To quote Arnold Schwarzenegger''s inevitable re-election campaign slogan, "I''ll be back".

It seems that Mat (fup) has finally made his move to India and so is rather busy at the moment. Tis a shame really, because I would have liked to have read his perspective on this problem.

Timkin

quote: Besides FuSMs, you can try other sorts of classification/clustering algorithms to develop and utilise the decision boundaries. Alternatively, you can try a probabilistic approach. I wont go into details about this sort of approach as it is rather detailed, needless to say that again, there is plenty of literature out there on it (and I''m happy to explain further if needs be).

What do you mean by probabilistic approach ? Markov chains that somehow simulates a FSM ?