• Advertisement

Archived

This topic is now archived and is closed to further replies.

Incredible AI - Could it be possible???

This topic is 5059 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I got this game in the works (Who Doesn''t ?) and i''ve been dooing some huge brainstorming. Most of my ideas are large, so large that i wonder if today''s hardware could handle them. But what i''ve been thinking on artificial intelligence sounds pretty.. well... cool! Imagine, an action adventure game, where youre walking into a bar. The bartender greets you and asks if you desire anything. you could reply, but instead, you pull out your guns and point it right at his head. What will he do!?! He could pray for his life, give the player what he wants, he could grab the shotgun stored under the counter and try to fight back. He could talk you out of doing some stupid. He could also start beeing *smart* and mouthing you off because he "knows" he''s got big strong freinds sitting around in the crowd.. What if the AI could respond to it''s best advantage, whether he knows he''s got freinds willing to back it up or if it could or not handle the situation. You know... something like Neural Net or something. Wouldn''t that be groovy? Post your comments so everyone can hear them, don''t keep them to yourself :-)

Share this post


Link to post
Share on other sites
Advertisement
You seek a minimaxed game tree. The computer evaluates it''s options up to a certain depth of the tree. It works like this:

Computer is faced with situation A. From this situation, he can do one of 3 things: X, Y, or Z The computer evaluates X to see if it''s to his advantage. He figures on a weighted scale that option X is worth 5. He then looks down at option Y, and figures it''s worth -9. He then looks at option Z and sees that it''s worth 0. The computer will pick option X, since it''s to his greatest advantage. This is a single-depth search.

Double depth means he looks at his advantage and the next opponent''s move off that to the opponent''s disadvantage. It''s really quite complex, but know that IBM''s computer "Deep Blue" used this to win the chess game. It had enough processing power to think out 1 million plus solutions per second. Meaning if it had 10 moves each level, it could search out a six level tree in a second. It also used comparitive advantage. It keeps track of it''s best move so far. If it finds a place where the computer can gain ground on it, it will automatically discount that route. That''s because it''s obivous that if the computer picked that route, the other side would pick it''s best route which would end up WORSE for the computer. This is assuming that all sides can think optimally The computer can literally tell that you''re going to pick your best move, so if it picks this one, it will actually lose out in the long run. It''s a very awesome search principle But it''s hardware dependant..

If you want more help on this, lemme know. i just took a DB programming class involving this. I made a really awesome game in Unix based on it.. kinda a clone off Global Thermonuclear War from WarGames they wiped the accounts afore i could save the code :/ my girlfriend and i had like 25 hours and 2k lines of code invested in it :/ oh well though.. hehe.

J

Share this post


Link to post
Share on other sites
Oh yeah, lemme mention.. minimaxed game trees is a LOT to code yeah, a LOT
So.. if you want to, go for it. Games like Chess, etc use it. And it''s been shown to be a good way to do AI. I can give you resources for info on it

J

Share this post


Link to post
Share on other sites
Another option is to use scripts. They''re probably not as mathematically powerful though. Example:
If NPC''s morale = 15 or higher then goto script 10a
If NPC''s morale = 12,13,14 then goto script 10b
If NPC''s morale = 11 or lower then goto script 10c

script 10a is npc violent script
script 10b is npc talk script
script 10c is npc cry script
etc


Scripts really are just i higher level of what Niphty was talking about though, you''ll still need the minimaxed logic tree if you want something truely dynamic and versitile.
just a thought...

Share this post


Link to post
Share on other sites
Well, Minimax itself is not such a big deal to code. Maybe 60 lines if you do not put any fancy optimization. What is hard is the evaluation function.

Also, what is hard, is that Minimax cannot work with a too big depth. I just finished an othello AI : in blitz-mode (max 5 minutes for the whole game) my Minimax can work with depth 3, alpha-beta pruning with depth 5, optimized alpha-beta with depth 8-9, and a Scout with depth 8-12.

Btw. in my opinion, you want more something like programming by constraints for your AI. In other words, defining rules and letting the AI engine assemble them for you.

Be reading you,
David

--
===
Am I the keeper of my brother ?

Share this post


Link to post
Share on other sites
Paul, scripts are fun to play with, but i think they''re harder for most people to comprehend in the begining. The simple reason is because they don''t have a truely apparant structure. If this, do this. And a lot of those are there It seems daunting the number if-then''s! The minimaxed tree just assigns it some sort of functional logic.. lol and they all tie together. if you actually looked, there''s no real difference, since a minimax tree will look about the same as all those if-thens put into a tree

Altmann, true.. minimax is a snap to code, but hard as hell to run the eval routine. It''s near impossible to imagine all the variables you could possibly use How did you run the scouting routine? I was considering having the computer scout ahead while the player was making their move.. just to model how a human looks ahead while waiting. I never had time to get around to coding it though :/ Had to get to work on a hash table lab almost immediately after i got done with this one, so i didn''t have much spare time.. lol All kinds of features we wanted to add, that''s why we''re pissed we didn''t get it off the server afore they wiped it. Oh well though

I like the idea ofallowing the AI to build its own choices. I''m unsure how to program this very effectively and effciently, however. So if you wanna toss us some tips on it, other than "i like this way better" lol Does it use up more or less CPU time than the minimaxed tree does? And does it model how people will consider options before actually doing something? I don''t like how most things simply have the AI check a value and compare it to certain routes. I personally would have the AI''s intelligence score or whatever modified to determine the search level it would perform. And i''d try to keep the program from using total CPU time by making it take pauses This way it''s actually like a human, waits and considers it''s options.. hehe There''s some devilish programming to be had here It might decide "if player looks away, then grab gun regardless" even if it sees that as a bad option. When the player looks away, then that option''s value suddenly increases The problem is foresight enough to plan for all these variables and to assign them space in memory.. hehe

J

Share this post


Link to post
Share on other sites
Ideally, you would have more than one variable in that tree. Maybe one for "fear" and one for "confidence" and one for "familiarity"... however many you can make. That way, it''s not just a point value thing. The computer would now be cross-referencing several emotions and if properly written, this technique creates a pretty life-like output.

Share this post


Link to post
Share on other sites
Well, I must say. Minimax is very interesting and I will defenitley consider looking up more on it. Although processor power is always a key element, I hope it doesn''t suck up all it''s juices.

My ultimate goal is to get a world filled with NPs that can react to players actions in very realistic ways. But if Minimax can run AI for 50 different NPs is a mystery to me.

Keep me informed on this, It''s extremeley interesting and sounds exactley like what I might be looking for :-)

Share this post


Link to post
Share on other sites
Cheese? as in, it''s nothing compared to rendering polygons? LOL! far from. I brought our comp system to it''s knees with the first tree i implimented in the game. I had it just go buckwild on an exhaustive search using MPI to run on multiple computers.. hehe. Brought two of our labs and the two main PII 450 1 gig memory machines to their knees.. muahahha! but damn.. it was cool as hell You can kill a processor with any simply algorithm.. hell.. try this:

main()
{
while(1)
fork;

return;
}

HEHEHEHE!

J

Share this post


Link to post
Share on other sites
3D graphics is simple for computers, which are designed expressly to manipulate numbers. Humans have trouble with the abstract nature of algebra etc.

Whereas artificial intelligence suits humans perfectly: we understand abstract concepts, we have several highly-developed languages to help shape higher thoughts, etc. Computers have trouble dealing with the abstract.

This is why we have 3D cards and no AI cards AI is just way too vague. And it doesn''t help that the ''traditional'' AI people and the ''game'' AI people aren''t really singing from the same scoresheet. Traditional AI people are more interested in making a truly intelligent simulation of an insect, whereas game AI people would usually rather have a partially intelligent human.

The minimax algorithm is simply a costs/benefit analysis. You check the possible outcomes, and the sub-outcomes, compare the scores, and choose the best one. But this is all numbers. You need to program into the system some concept of ''worth''. In chess, you just say a pawn is worth 1, a knight worth 3, etc, and the game can play reasonably well just on that information alone. But there are no simple values or equations for emotion. And there are usually several orders of magnitude more possible ''moves'' than in a chess game, killing your tree search at the 2nd or 3rd level of depth. The human mind quickly learns which parts of the tree are ''redundant'' and doesn''t search those possibilities any further. This has to be somehow encoded into a game''s AI, and while learning systems are all very fun, you can''t really put the learning into most games: you need the finished product.

AI is a big stumbling block: we are starting to get more processor time to do it in, but we are only really succeeding in being able to use more complex scripts and patterns.

Share this post


Link to post
Share on other sites
I''ve got to admitt i''ve been putting off repling to this thread but here goes. Rip me apart at will :-)

I see minimax and scripts as two different AI routines. The minimax being the more dynamic of the two when speaking on the [goto, if, then] coding level. Where as the script tends to been seen as static because they are hardcoded and have limited implementability (excluding the potential for variable inductions).

So, i now see two ways these AI elements can work together:
1. Scripts contain goto statements to minimax systems.
2. Minimax systems contain goto statements to scripts.

To me, script are the way to go if you have large amounts of memory at hand and maybe less processor juice. Vice versa for minimaxed systems. So it comes down to the hardware the game will run on not to mention the type of game.

------
I feel the need to babble out an idea...
Tech levels in RTS games are common and what they offer is usually the same thing (better armour bla bla). What if you increase the minimaxed ai depth for a unit when you increased it''s tech level [instead]. This would be new.
------

Minimax system are only good in limited area''s of the game/true? Where it''s easy for us to create values that the system can manipulate.

Rather than appling it to every creaton that walks the plain of a rpg and hence consuming valuable processor juice, would it not be possible to use it for the big bosses only. So rather than having the same old situation where the big boss has the usual more health and deal more damage just give them better ai.

- AI isn''t brain surgury... yet! -




Share this post


Link to post
Share on other sites
Paul, i think scripts with minimaxed parts would be best That way you could already narrow the field of searching. It''s like the whole "humans alreayd know certain things won''t work" kinda thinking With the script, you can limit how the minimax searches. But it''ll be different for every case. If the strong warrior approches, the AI will respond in kind. Perhaps the AI character is a wizard? it wouldn''t want to get near to the warrior. So it would use scripts to delimit the minimaxed tree, and then decide what is best to do from there. The script could act like knowledge.. hard coded, and the minimax would be like intelligence, thinking on the fly Together they could really work well. perhaps even have multiple levels of script/minimaxing? The AI sees a warrior, so it reacts accordingly, it checks certain variables on both the PC and NPC and then runs into a minimax of how best to carry out its decision. Would teleporting get me away faster? hehe Does the PC have ranged weapons that''ll kill me? lol The AI could look at what the player has, sum it up, and then decide how best to act.. but this might require multiple levels. You script to find out you should run, and then you minimax for the best way to run, and then you script again to see if this way is logical versus certain factors and if not.. you go and change the value of running and recheck it all again. This way it might decide "i can''t teleport, he''s got a ranged weapon, so running is futile, what now?" hehe it''s a very interesting set of logic checks, but i think would use some processor time, still. Then bosses could have better scripts and better depth-searching! whee!

J

Share this post


Link to post
Share on other sites
You might also want to take a look at the Creatures 2 and Creatures 3 decision making system. This game simulates a world with up to 12 independent AI''s (creatures) who each decide what to do based on their internal chemistry/emotional states. The chemistry/emotional system is genetically determined, hence different for every creature and evolving over generations. I think a system like this would be really fantastic for calculating NPC actions based on social input (i.e. actions by the player''s character). And you get 12 AI''s worth of brainpower from a Pentium II, not a supercomputer.

Share this post


Link to post
Share on other sites
I may be way off base here but-
isn''t the basic way described here similar to other attributes of the character, such as health, strength, exc.
however these attribs should be changed when certain other things change, such as-
if he is the bartender and one of his friends comes into the room the other should change the value of say confidence of the bartender, however, if you want to get way into it, this shouldn''t happen until the bartender sees his friend.
however, in the end it shouldn''t be much harder than say a rts game where each item checks if it is affecting another item/object, i''m guessing a per square calculation.
when u look at it this way it seems very possible!

just me and my ramblings
-Thr33d

Share this post


Link to post
Share on other sites
Also, forgot to note.
you would also have to include who affected who in the game and might have to have broder terms (of who affects who in which areas) but for a simple(complex) ai this may work fine.

btw sound like an awesome idea to me!

ttyl
-Thr33d

Share this post


Link to post
Share on other sites
AI is used for different situations:
1. Reacting to a players actions
2. Planning ahead (strategy style)
3. ???

As i see AI implementation, it all comes down to gamma testing. If it makes the processor sweat to much because it''s to complex then you have to reduce it''s complexity. Vice versa if the processors not sweating.

What about having the program (game) check to see how much juice the processor has left and self-optimizing the minimax search depth? Then the game would be better on better machines. Come to think of it, it would make the game a little harder to review aswell.

What do you think about that idea Niphty?

You would have to use the processor power % as a variable for controlling the level of searching. I know this probably doesn''t help much when you actually sit down and code this stuff in but its an idea.


WE are their,
"Sons of the Free"

Share this post


Link to post
Share on other sites
Humm.. how about a script that checks for processor percent and modifies based on that? I don''t like the idea that more powerful machines get a bigger advantage over those with less money to spend on a computer. If a script did it, it could weed out fields in the minimax tree that would likely not work. This way the processor wouldn''t go for long-shot type of solutions They might work, but no sense in trying to find out if it''s useless 95% of the time. But on a bigger machine, you could go for those long shots that might work.

It could work out either way. Just have a harder game the bigger machine you have.. hehe That might be kinda wild. Perhaps even have the player set the level of enemy AI. The problem with those today is that they''re all just how random the AI is. Since AI can be perfect, the random element is what people use to divert their intelligence. That to me isn''t right. Play almost any racing game today on the hardest level and i bet you''ll swear the AI is cheating. No, the AI is a physics god in the game and knows everything about everything. Half of the games don''t seem to have realistic controlls either because they''re not analog. Like you can race against someone who''s got percision controls when you''ve got digital As an avid car and race fan.. i find many faults with AI in racing games :/ But.. oh well. Paul, i like that idea.. hehe.. perhaps you should try to come up with more like it so i can be lazy!

J

Share this post


Link to post
Share on other sites
You know, if you make the AI irrational, you would''ve done a copy of the human brain.

LOL

- DarkMage139
"Real game developers don't change the rules. Real game developers don't break the rules. Real game developers make the rules!"
"Originality (in games) is the spice of life!"

Share this post


Link to post
Share on other sites
quote:
Original post by Niphty

Humm.. how about a script that checks for processor percent and modifies based on that? I don''t like the idea that more powerful machines get a bigger advantage over those with less money to spend on a computer.


I can understand Niphty that from your position when your making a game for online. But it would be neat for a single player game as you noted below.

quote:


If a script did it, it could weed out fields in the minimax tree that would likely not work. This way the processor wouldn''t go for long-shot type of solutions They might work, but no sense in trying to find out if it''s useless 95% of the time. But on a bigger machine, you could go for those long shots that might work.


yeah, ive heard of this type of ai memory where the computer actually uses search paths and when it''s done it once, it remembers the best path rather than doing it every time.

(possibly) --->You''d have to allow the program to name a routine and save it by itself. Or something like that. or turn a (already done) search path into a seed and name that seed appropriately so when it comes up again it uses those seeds which have already been solved. Kind of like it makes it''s own scripts in a way.

I probably deserved to be hassled out to the max for what i just said like "how the f#ck am i meant to do that :-)" go ahead, flame me. I understand.
quote:

It could work out either way. Just have a harder game the bigger machine you have.. hehe That might be kinda wild. Perhaps even have the player set the level of enemy AI. The problem with those today is that they''re all just how random the AI is. Since AI can be perfect, the random element is what people use to divert their intelligence. That to me isn''t right. Play almost any racing game today on the hardest level and i bet you''ll swear the AI is cheating. No, the AI is a physics god in the game and knows everything about everything.


hehehuf, yeah i worked that out about the physics god stuff. Why, because i know that i''d be easier to code. and easier on the CPU. Besides, good ai for a racing game is probably a waste of good cpu juice unless you want it to analyse the player for some reason or another.

quote:

Half of the games don''t seem to have realistic controlls either because they''re not analog. Like you can race against someone who''s got percision controls when you''ve got digital As an avid car and race fan.. i find many faults with AI in racing games :/ But.. oh well. Paul, i like that idea.. hehe.. perhaps you should try to come up with more like it so i can be lazy!


I''m just an evil apprentice here niphty ;-) [twiddling thumbs]. Hmmm thinking... hmmm... tell me what you''d really like to see in ai and i''ll bounce some idea''s around with you if you like? I''m enjoying this topic 8^}





WE are their,
"Sons of the Free"

Share this post


Link to post
Share on other sites
LOL.. ok, first off, i''m a dork. How the hell do you quote like that?

Secondly.. hehe.. evil apprentice my arse

And third.. humm.. irrational AI. This makes me think of when i''m losing like mad in a racing game and i turn my car around, trying to ram the lead car while going backwards on a race course.. ehehhee!

Now.. on with the real stuff. The thing that''s hard to do is make an AI which learns because of the sheer size it would take on. You could imagine an install program which reads:
Low-level AI: basically stupid.
Mid-level AI: little processor time required.
High-level AI: Lots of processor time required with moderate memory demands.
Learning-level AI: Lots of processor time required with options for using memory or hard drive for storage. Requires a lot fo storage space which will not exceed 2 terabytes.
Perfect-level AI: Knows it all, doesn''t need to calculate, a true machine.

Just imagine how many people would be like "uhhmm.. what?" so instead you rename those using their first first "low" "mid" "high" etc.. And you call it difficulty.. hehe. The learning AI would start stupid but would become your worst nightmare in the end.. lol. They''d learn to anticipate your moves, knock you out of the race and still be perfect in running Unfortunately, i think that 2 terabyte number might be a bit small depending on how complex the game is. Imagine an AI that remember how it hit the puck at you in an air hockey game. People do this. You look for weaknesses. If someone can''t handle a backhand in tennis, you do it more often to them, as much as you can. In air hockey, my friend could never EVER block a shot that bounced off two walls. So i''d hit it right, off that wall, and off the left wall, and right in.. lol The AI could easily remember what it did to score and try to repeat those conditions. It could keep up with % of times it scored in this manner, and utilize the best ones. It could also track your performance like this and let you know if you''ve improved. And it could tell you your weaknesses.. hehe Very interesting concept, requires little space.. and is very nice for frustrating a player.. hehe. Then the AI level is simply how frequently it gets into position and exposes your weaknesses. The fewer weaknesses you have, the harder you''ll be to beat. Very true to life

J

Share this post


Link to post
Share on other sites
I just realised a problem with having self optimizing minimax. The player would learn that the more red herrings that they can produce for the ai to chomp down the worse (shallower search depth) the computers decisions would be.

I half agree with you on the AI memory issue. Such systems would be applicable to something like a training program but it would have to be gravely modified for gaming. I thing the system would still be very useful if implemented to enhance the fun factor of the game.

How do you do this? Some sort of balancing routine would probably be a good start i think/yes? Maybe rather than adding challange it could calculate how to add to the fun. It would have to calculate what the player is doing to have fun. This way the game becomes customized to each individual gamer. Boy can i dream :-).
-----
(to niphty)
I''m quite suprised you still havn''t flamed me Niphty, you must be a very tolerant dork/nerd :-)??? or do you just think of me as an amusing clown :-)??
-----

Is there any way of reducing the memory consumption of a remembering minimax system? Shall I? Shall I? yeah why not...
You would have to be very tight on what you apply (ingame) the system to. Like one big boss using it then "save" once he''s dead and the next big boss will "load" and on and on until the game is over. Each big boss will become smarter and more customized to you (the player). The longer you take to kill him the more he/she/it learns about you. This would be quite a surprise for the more arrogant gamers (like me)who like to toy with big bosses and take their time with them hehe they''d get a nasty little suprise come the endo of the next level. You see, i am an evil apprentice Niphty :-) or maybe more an evil conspirator. [licking lips, nodding & squinting] mmmm yeahesss Mmmm

Alright, what about a self correction ai. The system would have to first realise that it did something good AND that it could have been done better.

You know i''ve seriously been considering working out irrational ia. It would have to be some kind of virtual wheel of fortune. Rather than going with the option with the highest value it just chucks all the options on a wheel and spins it. Takes the random one that comes out and uses it as a category for it''s next minimax search. Kind of like teaching the computer to gamble in a way.

Teach the computer to apply values to patterns and it could develop strategies. A strategy to me is an influencing act when compared to a tactic which produces a result. A strategy can be calculated a a percentage increase. This way a computer can value a pattern. A pattern that increases the odds for a sucessful tactical manuveur would then be applied in-game. But what happens when the best two patterns have equal values? <--- that''s a topic tease :-)





WE are their,
"Sons of the Free"

Share this post


Link to post
Share on other sites
I think you are placing a little too much faith in this whole ''minimax'' concept. It''s more designed for effective-yet-simple AI than interesting-and-detailed AI. On a very basic level, it''s just ''evaluate all options, choose which one benefits me the most and the opponent the least''. Adjusting the search depth on the fly won''t help you much when you have a billion and one possible options in the first place. You still have to do the hard work up front: namely, assigning scores to given situations. In chess, a knight can nearly always be considered to be worth 3 points. How many points is a gun worth to the bartender? What if the opponent is perhaps resistant to bullets? What if shooting people is illegal? What if there''s a low chance of getting caught? These issues are hard to quantify with simple ''values''. Minimax is really designed to crunch thousands of simple point values in a repetitive manner, and is thus more suited to things like chess. It works best where the ''breadth'' of the search is not very large. For instance, there may only be 30 or so possible moves available in a game of chess. So, there are 30 level one possibilities to evaluate, about 900 at level 2, 27,000 at level 3, and so on. You want to be able to go a few more levels than 3 to have a good result. But the average person might have thousands of things they could do in a given situation. That means you''re dealing with billions of things at level 3 rather than tens of thousands.

In real life, people address major abstract concepts first, and search deeper within that concept if necessary. For example, to re-use the chess analogy, instead of checking every possible chess move, a human player may think ''ah, my queen is under threat'' and often only look at related issues. You can do -some- of this with minimax (known as ''alpha-beta pruning'') but then you start to lose the benefits. This is why a scripting approach is generally going to be much easier to do and yield much better results. You could spend all your life designing minimax data for just the simplest of situations that a person could be in. It''s probably better for you to think of a few high-level abstract situations so that you can use more general heuristics to guide creature behaviour.

Share this post


Link to post
Share on other sites
Paul, i wouldn''t flame you.. you''ve not done anything to deserve it, yet keep trying.

I think the point of the minimax tree is to merely search out what paths would be helpful for the computer. The script would limit those options to search for "do i have a gun? can i use it well? could i hit this guy in this armor?" etc. Once the field is limited then you can begin to make some choices using the minimax. It''s all about limiting those choices before you search. Maybe pick three or four main possiblities with the highest probability.. "duck and cover" "surrender" "blast the mofo''s head off". The minimax would take over evaluating each one of those and determine which on is the best according to what the AI character''s stats are, and then it would return to the script with "blow his head off" and the script would look at this and say "is he aiming at me already?" and if so, then that option''s out.. hehe
It could work well together, and minimax would just allow for some prediciting of the future whereas a script can only deal with what''s going on here and now. Together they could do some serious damage.

Paul, i''ll touch on the other stuff you said later on time to sleep for now.

J

Share this post


Link to post
Share on other sites

This topic is 5059 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.

  • Advertisement