Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 07 Mar 2002
Offline Last Active Today, 12:21 AM

#5146705 AI is harder than I thought

Posted by on 13 April 2014 - 08:57 AM

We understand you are excited about fuzzy logic, TD. It is one of those approaches that have a sexy name and a good story to go with it. The same is true of neural networks and genetic algorithms.

But until you get some actual experience solving problems with fuzzy logic, please stop telling everyone that it is the solution to their problems. You simply don't know if that's the case.

When [smart] humans play tic-tac-toe, they generally can look a few moves ahead. Minimax search might be a better analog of how humans behave in this context.

#5146693 AI is harder than I thought

Posted by on 13 April 2014 - 06:55 AM

The whole story goes that there is a computer that can beat any human at a game of chess. It learns your natural patterns and then adapts to beat you. So the more it plays you, the better it comes at beating you. Eventually it will beat you every time. This takes advantage of the fact that humans, no matter how random they try to be, are really not so random.

What are you talking about?

I actually think the scenario was a game of rock, paper, scissors, but the idea applies everywhere.

Oh, I see: Rock-paper-scissors, tic-tac-toe, chess, brain surgery... It's all the same in your mind, unencumbered by detailed knowledge of anything in this subject.

That is why I think fuzzy logic is the best way to do AI for such games as tic-tac-toe, because it becomes naturally fair, since the computer isn't using a mathematical algorithm for solving the game, but an imprecise observation and guessing at the solution to any current problem. So it is bound to make human-like errors, that keep the game fun. 

And fuzzy logic is actually not as hard. I am doing research in this area, and I should be finished with it (an implementation as well) by next Saturday.

What time on Saturday do you think you'll be finished with it?

#5146592 Using C++

Posted by on 12 April 2014 - 05:22 PM

Why is this in the "Artificial Intelligence" forum? There is a "For Beginners" forum.

#5146588 AI is harder than I thought

Posted by on 12 April 2014 - 04:34 PM

1) Don't know the name of it - 'game board' is lines of dots. You take away dots on your turn. You win if you opponent picks up the last dot.

It's called Nim, and it has been solved for over a hundred years.

#5146587 [Flocking] How to improve performance?

Posted by on 12 April 2014 - 04:30 PM

First, do yourself a favor and start thinking of how long it takes to do something, not how many times you can do something per second. It's easier to think about the former than the latter.

It looks like your performance is approximately linear in the number of boids, which is about the best you can hope for. If you were using a more naive algorithm, you could easily see the time it takes to complete a frame growing with the square of the number of boids.

So the issue is then how you can get more than 6000 boid updates per second. I don't know anything about unity3D, but I am sure there are ways to profile your code. If nothing else, one can insert timing calls into the code to generate a log that tells you how long each step is taking.

If everything else fails, post your code so we can see if you are doing something obviously inefficient.

#5146438 Binary search implementation

Posted by on 11 April 2014 - 07:34 PM

There is an implementation of binary search in the library: upper_bound

#5146369 I have some new habits.

Posted by on 11 April 2014 - 12:56 PM

You can make a wrapper around `float' or `double' that is templetized on three integers, indicating what powers of kilogram, meter and second give you the units. It's kind of a cool exercise.


Or you can use Boost.Units.

#5146284 Static as substitute of private members.

Posted by on 11 April 2014 - 09:00 AM

Static is not a replacement for private in C. Declaring and defining them only in the .C file is.

Don't they need to be declared static inside the .C file so that they only visible from within that compilation unit.

No, each compilation unit is compiled individually, a variable has to be declared as extern to become accessible across compilation units.

If you declare and define the variable in global scope in the .C file, it's implicitly static anyway.

What do you mean "implicitly static"? If you have two compilation units that define variables with the same name in the global scope and none of them are static, you will get a "multiple definition" error when linking. There is no such thing as "implicitly static".

#5146231 Need some pointers on a diplomatic AI

Posted by on 11 April 2014 - 06:43 AM

My preference would be to create a set of rules that give small factions some edge (guerrilla war, sympathy of the local population, difficulty of finding their hideouts, perhaps large factions get slowed down by bureaucracy and coordination problems...) and then let each faction really try hard to win. Otherwise you could end up with diplomatic actions that make little sense, where the dominant faction helps a weak faction without much justification, or where it becomes too transparent that they are collaborating to keep a healthy ecosystem of factions. Of course the guiding principle should be to make the illusion work for the player, by whatever means necessary.

#5146146 Need some pointers on a diplomatic AI

Posted by on 10 April 2014 - 08:14 PM

Over the last few years, computer go playing has improved dramatically by using Monte Carlo Tree Search. Many of the techniques developed for computer go are applicable to a large class of games. The fact that you don't know what deals other players have made with each other might complicate things, but perhaps you can start by ignoring that, and think about it more once you have something working.

You need several ingredients:
* A class that represents the game situation. You'll need methods to know if the game is over (and how well each player did), what the available actions are for each player at any given time, and to perform an action.
* A so-called playout policy, which is a fast function that picks a random action from each available action to each player. This random selection need not be uniformly random: It's better if it selects moves that are obviously good more often than obviously bad moves. This doesn't need to be very smart at all.

The basic idea is that for each of the available actions at the current position, we play many random games (using the playout policy for every player) and we compute the average reward we get from them. Then simply pick the move with the highest average reward. In order to be able to simulate a significant number of random games, it is essential that the code be fast.

It is very possible that the AI resulting from doing what I just described will be good enough. If it's not, there are a few improvements you can try:
* Explore promising moves more often, treating the situation as a multi-armed bandit, and using an algorithm like UCB1. Actually, this is easy enough that you should do it even if the program is strong enough without it.
* Accumulate statistics for positions that have been visited multiple times by this procedure and apply the point above at those positions as well (this results in Monte Carlo Tree Search).
* Enrich the statistics using something called RAVE, or other techniques that exploit similarity between positions.

Hopefully that gives you enough ideas and search terms to get you started.

#5146066 I have some new habits.

Posted by on 10 April 2014 - 02:05 PM

After doing a little bit of reading on the subject, it looks like this is an old debate: http://en.wikipedia.org/wiki/Fuzzy_logic#Comparison_to_probability . My own thinking seems to line up closely with that of Bruno de Finetti's.

#5146061 I have some new habits.

Posted by on 10 April 2014 - 01:47 PM

Whenever I see a mathematical expression I understand that all constants have a name, and all variables have a name.

This is one thing I like about computer programming. We can use words. Take the number 1.82 in your example. What does 1.82 represent?

What does 0.1 represent? What relationship do these numbers have to the height in meters? And how does this expression describe the tallness of any object?

I know that -9.81 is the gravitational constant.

GRAVITY = -9.81

Now take the number -9.81 alone and you have no information as to what it represents unless you had been taught in school.

Sure, I didn't give the constant names, but I thought their meanings would be easy to deduce from the context. I shouldn't make such assumptions and I apologize.

The constant 1.82 is the height of a man for which, if you asked a random person, they would classify them as tall with a probability of 50%. The constant 0.1 expresses how quickly we build consensus that someone is tall as his height increases from 1.82. So for this particular setting, a man of height 1.92 m would a probability of being considered tall of about 73%. I made up both numbers without looking at any data, and even the form of the formula is questionable. My point is that you need some model of the probability of being considered tall as a function of height. The details are less important.

In the example in the video I posted, he has several basketball players who need to be sorted by their tallness. Not using the cut-off point method (Boolean logic) he was able to represent the tallness or shortness of a player as a percentage to the "idea" of tall, which could change in each new game (scale is one thing that is very unlikely to remain the same from game to game, unless you use the same game engine and make the same types of games.)

Sorry, I didn't realize you had posted a video. I'll go back through the thread and try to find it.

#5146037 I have some new habits.

Posted by on 10 April 2014 - 12:18 PM

Here's one way of handling tallness with probability. A man has a height, which might be a hidden quantity if you can't measure it directly. "Tallness" is an observable, which we could define as "the probability that someone would call this person tall". If we want to reason about the situation, we need to introduce a model that maps height to tallness, and which could look something like this:
tallness = 1 / (1 + exp(-(height_in_meters - 1.82) / 0.1)) // [EDIT: I had forgotten a minus sign in this formula]
As an illustration of the usefulness of this approach, if you have a set of men that are suspects in a murder case, and you learn that the killer is tall, you can take your prior distribution of probability of guilt and use the suspects' tallness to compute a posterior probability, using Bayes' formula.

#5145969 I have some new habits.

Posted by on 10 April 2014 - 09:24 AM

So now we are shifting to a religious war about fuzzy logic? :)


I only have one comment about it: If you want to know how to handle truth values between 0 and 1, learn probability.

#5145821 I have some new habits.

Posted by on 09 April 2014 - 07:09 PM

(To the guys (as a group) that try to oppose the obvious. Not the OP who is caught it in the crossfire.)
If you still don't get it after my posts and the post of hodgman, I am at loss of words.

Get what, exactly? That a naive adherence to OO principles without any experience to guide you will result in programs with poor performance? There is some truth to that, and it's worth pointing it out to beginners. But from there to advocating a repudiation of abstraction in favor of looking at the data and how it's laid out in memory...

Hang in there some 10+ years and then get back to me.

I see, we are just too inexperienced to understand what you are saying.


PS2 - Pro tip. Look me up and see what I have achieved. Then think.

Sorry, you are named after a generic beginners' OpenGL project, so it's not so obvious what you have achieved.