Incredible AI - Could it be possible???

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

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

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...

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 ?

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

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.

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 :-)

Processor power? Isn''t this all cheese compared to a single polygon?

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

Hey man. Don''t forget, I know NOTHING!

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.

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! -

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

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.

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

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

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"

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

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!"