Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 01 Aug 2002
Offline Last Active Feb 02 2012 11:35 AM

#4878994 Bayes Networks in games?

Posted by Daerax on 31 October 2011 - 02:39 PM

If you honestly feel they are that valuable, you should be willing to make the resources available to teach people about them without needing encouragement. Most people won't see the need or interest until after a resource is available which clearly, concisely, and comprehensively illustrates the value of that technique.

Frankly, you shouldn't need our approval or rabid anticipation to do something that you think is worthwhile.

I am short on time or I would volunteer. Someday maybe. But he is right Decision Trees are something that are not payed enough attention to. Random Forest in my use case outperformed neural nets and SVM and are speedy to train.

For games, more than neural or bayes nets or genetic search, decision trees are the one thing out of machine learning I would argue to be most applicable to games in a splash and dash manner. They represent a probability distribution over the data, are not very far from FSM many are used to and with a weighted randomized voting method are close to behaviour trees (although built in an inverse manner - decision trees you start from a list of scenarios and desired ouptuts and it returns a tree, btrees - you start with actions to input states and build the tree - at least for what I can understand of behaviour trees, the game literature terminology is not one I am fluent in)

Here is a fairly clear but basic python example of a decision Tree from Machine Learning An Algorithmic Perspective (I highly recommend the book). http://www-ist.masse...Code/6/dtree.py

#4878783 Bayes Networks in games?

Posted by Daerax on 30 October 2011 - 08:45 PM

I am learning about Bayes Networks at Stanford's online AI class. I was wondering if there are books that talk about and implement code related to Bayes networks in context of games?


Bayes Networks would be wasted on games. They are slow, inference on them is NP - hard. Building the network structure from data is also NP-hard. So for a decent sized network you gonna be doing something like gibbs sampling to do inference on network a structure that is almost guaranteed to be wrong. For a game the AI will take a long time to get at the distribution and is not worth it. Most of machine learning is either too slow, data intensive or stationary for Game use.

If there would be one machine learning thing that I would actively look into, it would be Decision Trees. Decision trees are brittle so can add variance and do well with little data. You could then augment them as Random forest or boosted trees. I think that would be where I would start.

A close cousin to bayes nets that might be useful to some types of games (arcade shooter, anything requiring movement tracking and prediction) would be a particle filter. Finally, a bared down Reinforcement learning algo may be good for long term play in a strategy or RPG. All of these would be very hard to get right and take a lot of time when a simple markov chain based model or even Finite state machine would have done just as good or better for much less work.

#4826456 when are genetic algorithms useful?

Posted by Daerax on 22 June 2011 - 09:05 AM

- Black and White (some type of learning?)
- Creatures (not sure ...)

Black & White simply used reinforcement learning. All that does is tweak weight coefficients.
Creatures used a GA for the actual genetics (so not really a GA per se... just a gene sequence that was combined and mutated from parents). They also used a form of NN for the learning, iirc. Not really typical gameplay, however. Again, both of these were, as Alvaro said, the algorithms looking for problems and finding them.

dont you think its a bit disingenuous to call reinforcement learning as just tweaking weight coefficients? Most of machine learning can be described such.

#4729060 Why not learning AI?

Posted by Daerax on 05 November 2010 - 05:07 AM

I agree that ML is not currently a good fit for games but for completely different reasons than Kevin.

The only of his reasons I agree with is the part about lack of creative control. This inability is definitely a hindrance but for some games what you might gain in return is cool unscripted behaviour.

But 4 and 5? Something that no one has done before because it is so hard is exactly the thing that is looking to be disrupted, worked on and then joked about how people ever found such things difficult.

Then there is Issue numbers 3 and 2, basically the same root issue - what he calls rigid black boxes. Machine learning is not limited to these approaches and there are frameworks like PAC to aid in understanding or techniques like entropy or margin based models that have clear mathematical underpinnings. And the issues he speaks about, changing game parameters should only be a problem if the algorithm in uses is sensitive to over fitting and generalizes poorly or the game parameters vary very wildly during production. There are techniques such as online learning and reinforcement learning that are resilient to such unstable environments. In particular reinforcement learning is not a supervised technique and probably the most applicable of ML techniques to games. Also, I feel he misuses the term fitness function as he uses it more generally than I have encountered.

And issue 1 is a matter of using what works best. A controller for a car could use fuzzy logic, which is something thats not machine learning but arguably more robust than hand tuning a set of equations + if statements. But approaching machine learning like its anything like the name suggests is the wrong mental model. It is just statistics, differential equations and linear algebra. And fairly basic (as far as such things go) at that. Saying maths is not applicable to AI sounds a bit silly. And this brings me to the core issue I feel we agree with. Why machine learning is not enough for games.

Games are actually still trying to create AI but machine learning, especially the supervised kind is really just statistics. Not enough for the purposes of games. Games need agents that look smart but also make mistakes and are defeat-able and are fair. Machine learning excels where there is an enormous amount of data about some unknown condition but games are almost the opposite by definition. They are environments built from the ground up from scratch by people who become intimiate with many of its details. The need for statistics is little and a hand built HFSM is much more appropriate to those conditions with a need for creative but defeatable behaviour than ANNs, SVMs or what have you.

But if I would suggest something from ML to games people its Reinforcement learning. The fact that FSM are so prevalent is suggestive to its applicability. Many game environments are well modelled by Markov decision processes an area where reinforcement learning operates. Reinforcement learning is a lot less adhoc and with a much sounder mathematical underpinning, an ability to be reasoned about and incorporate planning and learning. It can be combined with game theory and tuned for mixed strategies - which are not predictable to a situation.

[Edited by - Daerax on November 5, 2010 11:07:24 AM]

#3600150 C# vs C++ as a choice for development

Posted by Daerax on 11 May 2006 - 11:32 PM

With regards to Managed vs Unmanaged code:

Certainly no single human with less than a decade of experience can even begin to hope to create applications in one language where speed difference in executed code are the cause of slow downs and not inefficient algorithim implementation and design.

Basically, it is unlikely, the chances highly remote that you'd ever run into the case where the "speed" differences would actually matter. The probability of encountering a scenario where languages create speed bottlenecks decreases with time. Processor and operating complexity further diminish this alleged spped gap.

[Edited by - Daerax on May 12, 2006 6:32:21 AM]

#2965722 Line segment plane intersection code issues...

Posted by Daerax on 20 March 2005 - 10:41 PM

I think the error lies in the line:
float dist = -((p.Normal() * p1) + p.Distance()) / denom;
It looks like you have the negative sign in the wrong place. I suggest trying:
float dist = (-(p.Normal() * p1) + p.Distance()) / denom;

Original post by Zipster
I don't understand this line:
float denom = p.Normal() * dir;

Or any of the other lines where you "multiply" two vectors and get a scalar. Dot product I presume?

At any rate, what I would do is find the absolute distance of p1 and p2 from the plane, call them p1dist and p2dist. Then you have the normalized direction vector from p1 to p2, call it dir. Then, the intersection point is dir * (p1dist / (p1dist + p2dist)) which works because of triangle congruency. This is what I think you're doing, however maybe it isn't as clear because of how you do it. Maybe the problem is because you have p1 - p2 as your direction instead of p2 - p1 but I haven't examined it that closely enough.

You offer me a perfect excuse to post my original reply, I went and wrote a lengthy reply without really looking at the code, when I finally did I smacked myself with a shoe and was like, arghh all that typing and he just had to move the sign!! Anyway Im sure it'll be useful to someone, there is not many satisfactory explanations on Intersection of stuffs.

Other post begins Here:

Your notation is a bit confusing to me as it clashes a bit with what I am used to. You have n(0,0,1)d = -24 and I thought you were defining the plane such that n was the normal and d was a scalar value..It took a while for me to recognize that d was a point which created a vector with the point through which the plane passed through..

Anyway I think your method is a bit acrobatic and the need for normals is unnecessary if one utilizes the definition of a line in 3 space. In planar geometry a line can be defined with a member point and its slope, similarly so is a plane defined in 3 space. The plane can be define by an inclination and point on the plane. If we ascribe a vector n orthogonal to our plane the task of defining our inclination it then follows that for any point P which lies in our plane going through some point Q, if we create a vector [QP] then the dot product with n will be zero since n is orthogonal to our plane. Thus a plane is defined as n•(P-Q) = 0.

If we have a line in 3-Space going through some point L then any any point X on the line creates a vector [LX] parallel to some vector v which directs the line.  Since [LX] || v it follows that there exists a scalar t describing our line progression such thatLX = tv. Since [LX] = tv then (X - L) = tv -> X = L + tv, our parametric equation for our line (since X, L and v are actually made up of 3 components i.e Xx, Xy Xz)

Since the we know the line intersects with our plane then we know that some point X on our line is also part of our plane.  You have your plane defined as n•d = c ( a variant of ax + by + cz = d), so we need to rewrite our original plane equation to reflect this form.

We have from earlier that n•(P-Q) = 0 thus n•P - n•Q = 0 -> n•P = n•Q, n•Q = d. => n•P = d, Since X from our line is also a part of the plane then X = P so:

n•X = d, X= L+tv -> (L + tv) • n => L•n + tv n = d  -> tv•n = d - L • n
t = d - L•n  Note also that since d =  n•Q that 

t =  n•Q - L•n  or n•(Q - L)
vn vn

That equation is for the general case when Q is known and no constant is given. Also note that the denominator of the equation for t will be equal to zero when the line is parrallel to the plane. Using your code as a template the PoI can be found thus:

Vector p1 (0, -64, -64);
Vector p2 (0, -64, 0);
Vector v = p2 - p1;

float denom = p.Normal() * v;

if (denom == 0)
continue; // n _|_ p

float t = d - (p1 * p.Normal())/ denom;
Vector PoI = p1 + (t * v);
End It! Damn it, I want my 15~20mins back!![sad]

Oh, I still dont know why you are normalizing and what this line means:

Vector p1 = this->points[y];
Vector p2 = this->points[x];