What's your best AI?

⌘-R in Chief
Posts: 1,237
Joined: 2002.05
Post: #1
I'm in an AI mood lately and am curious to see an array of the best AI implementations you've all written. Grin

Anyone care to share? The best thing I've done is a connect four game which will squash you like a bug. Smile Sadly, that's all I've done. Cry
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #2
I wish I had more time to play around with AI stuff. I did once implement a genetic algorithm for basic path finding. While not particularly impressive, genetic algorithms are really cool and I was blown away the first time I saw it working.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #3
We did an AI competition for my algorithms class called RoboGame. The basis was that you were writing an AI for a little robot that moved around a city grid laying down a trail of bread crumbs. The only input you got was the distance to the building in front of you, and the status of the grid cells immediately around you. If you closed the trail, and all of the buildings inside the loop were uncaptured, then you would capture all the buildings. If the loop contained any buildings captured by the other robots, you got zilch. Whoever captured the most buildings at the end won.

Our robot was the only one that did mapping or pathfinding (with turning costs considered) and did fairly well. The second time around we modified it so that it would also mark off sections of the map that it knew were captured. We also implemented a pretty effective "bastard move" that it performed right off the bat. If that was successful, we would have half the buildings right away and only actively look for new buildings on the uncaptured side. We pretty much cleaned house then.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Moderator
Posts: 691
Joined: 2002.04
Post: #4
Hmm, well I hacked together this prototype (gun_dance, ~0.5Mb) a few months ago to fill a dull week, but I wouldn't want to label it my best (it doesn't even try to weigh threats, making it somewhat... single-minded Rolleyes)

What I would label my best is a learning AI which learns to play Puyo Puyo starting with a blank slate; I was hoping it would form part of my final project for uni, but as it looks like I won't be returning to uni, I'll try to tidy it up to post here (the uni I attend seems - at least my course, but I've seen nothing in the purer computing courses to change my mind - to have almost no coverage of AI Cry)

Mark Bishop
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #5
Does emergent behavior count? I've never done any hard AI ( no neural nets, no self guided learning, etc ), but I've had a great time writing behavioral networks with emergent behavior to do pathfinding and motor control for walking.

http://home.earthlink.net/~zakariya/files/Clumsy_2.mov
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #6
A few months ago I wrote a pedestrian simulator (based on A*) that tries to have people avoiding to bump into each other and avoiding bottlenecks (given a wall map).

I tried different ideas in the end I settled for this: each agent knows the "intended path" of the other agents, so can adjust his path to avoid getting close to other people (increasing the A* cost for going close to where you think other people will be in future steps). Once an agent updates, the other agents will have to update too since his intended path changed etc. Each agent updates his intended path every 5 steps (not all together).

Works ok (fairly realistic) though cheats a bit Wink

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
Member
Posts: 245
Joined: 2005.11
Post: #7
I had a go at a neural network library a while back. I built some little networks with it and tought them to play high/low and some other simple tests like that. It did work ok but the way I changed the design two or three times while programming it meant it was a bit of a mess. Also it was all C++, and I tend to do everything in Obj-C these days so I'll be starting my future AI projects from scratch when I eventually get that far.
Quote this message in a reply
⌘-R in Chief
Posts: 1,237
Joined: 2002.05
Post: #8
Skorche Wrote:We also implemented a pretty effective "bastard move" that it performed right off the bat. If that was successful, we would have half the buildings right away and only actively look for new buildings on the uncaptured side. We pretty much cleaned house then.

LOL, that's great.


TomorrowPlusX Wrote:Does emergent behavior count?

I think so. I did a crowd simulation thing for emergentish behavior. It was neat, but not very fancy. I think that emergent behavior is a really big goal of the type of AI that intrigues me most. I'm a huge Deus Ex fan and I've always thought the AI was pretty good, but if you took it 10 steps further, I'd imagine seeing some type of emergent behavior through learning.

Najdorf --- Can you post your sim? I wrote mine in two days for a school project so I didn't get as far as long-distance pathing, and my collision detection sucked. Rasp
Quote this message in a reply
Moderator
Posts: 770
Joined: 2003.04
Post: #9
I made a little virtual robot which evolves the size/shape of it's body segments and legs, and learns to walk and push a little ball, but it is simply using a genetic algorithm, I don't personally consider it AI.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #10
Genetic algorithms are fun, but a total pain. They generally end up exploiting the subtlest mistakes/oversights in your simulations...

I tried to evolve a walker some years ago. Every single viable evolved candidate actually ended up evolving hopping motions, since they went the furthest, most quickly. I couldn't come up with a good judgement criteria that excluded hops Rasp
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #11
TomorrowPlusX Wrote:Genetic algorithms are fun, but a total pain. They generally end up exploiting the subtlest mistakes/oversights in your simulations...

I tried to evolve a walker some years ago. Every single viable evolved candidate actually ended up evolving hopping motions, since they went the furthest, most quickly. I couldn't come up with a good judgement criteria that excluded hops Rasp

I heard someone made a GA to generate the optimal keyboard layout and it came very close to dvorak.

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Member
Posts: 100
Joined: 2006.05
Post: #12
unknown Wrote:I heard someone made a GA to generate the optimal keyboard layout and it came very close to dvorak.

That's pretty awesome. I've been looking for a little experimental proof of why I took the time to learn DVORAK....
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #13
Speaking of GA results and weaknesses: I've heard that it is pretty common for modern racing games to use GAs for the AI car routes (not on the fly, but as the game is being developed). I remember playing Need for Speed Most Wanted and seeing the cars sometimes take some really dopey turns in one spot on the track. I was able to exploit it every time because it was the least efficient route by far in that spot. But of course they'd often know other spots that would make time up on me, or the game would simply cheat to catch up (which it did whenever I got far ahead).

So the learning function in that instance was probably just to win the race, and sometimes they did against me, but it didn't always make for a pretty route around the track. What tipped me off that it must have been done with GAs is that most of the cars took that identical dopey route, and that is something you'll often see when you watch GA agents evolve. They don't care how they get there, they just have to satisfy the learning function.
Quote this message in a reply
Member
Posts: 749
Joined: 2003.01
Post: #14
Quote:Najdorf --- Can you post your sim?

http://www.ragdollsoft.com/pathfindah.zip intel only

It's got few (read none at all) features. Still you can edit the map [but not remove the 3 lines (I tried to optimize for those 3 with specific code)]

©h€ck øut µy stuƒƒ åt ragdollsoft.com
New game in development Rubber Ninjas - Mac Games Downloads
Quote this message in a reply
⌘-R in Chief
Posts: 1,237
Joined: 2002.05
Post: #15
TomorrowPlusX Wrote:I tried to evolve a walker some years ago. Every single viable evolved candidate actually ended up evolving hopping motions, since they went the furthest, most quickly. I couldn't come up with a good judgement criteria that excluded hops Rasp

lol, that's great. I understand the basic principle of genetic algorithms, but we didn't go into implementation and application, so I'm still a little bit unsure as how they can be applied to non-obvious problems.
Quote this message in a reply
Post Reply