Why an AI for Outwitters is hard to do

[Kamikaze28]

(07-13-2012 11:04 PM)getuliojr Wrote:  There are many ways to build an AI and I don´t think it is that much complicated. You just have to set the goals and on each new version of the software making it better as you learn along.

If creating AI wasn't hard, mankind would have already been enslaved by intelligent machines.

(07-13-2012 11:04 PM)getuliojr Wrote:  1. You can create a game based on played games. You choose only one type of map and get all results that has lead a player to victory and save his movement to a database. And put the computer to get copy this moves. It probably will go farther away and probably will find in the dabase a move he can take based on the actual state. BAD: you would need to download a lot of chunk of information to the mobile in order to have it data to play offline, otherwise even single player would require a internet connection.

As you already pointed out, this database would be enormous - not to mention the search effort to find an identical or similar state and corresponding reaction for every single move would be unbearable.
Also: what would you do if there was no known situation in your database? You'd have to have a 'traditional' AI at hand for that anyway.

(07-13-2012 11:04 PM)getuliojr Wrote:  2. You could write te goals that ends the game and all moves and attacks and create to achieve the goal and make the computer simulate, like a tree. How much should a computer simulate before playing ? Well in easy mode it can be like 10 moves ahead or 20 seconds of processing, in hard could be up to 30 moves ahead or 1 minute of processing. When each one reachs the computer stop, and execute the best one at the time que processed that would give him 70% of chance of victory to 100% of chance of victory based on certain simulated cenaries and plays it.

Next turn it restart and do all over again. NOT that much hard, but work is necessary.

That's basically what I described in my first post. Also, who'd want to wait 20 seconds or a full minute for the device to finish simulating before it moved. Not to mention the battery power that would be burned in the process.
Just a little number game. I estimated Outwitters branching factor somewhere in 'the hundreds' - let's be modest and say it's 50. Simulating 10 'moves' (or actions as I'd rather call them) ahead would require the exploration of 50^10 (≈9.76e+16) states - that's roughly 15.5 years at the speed of 200 million states/second (Deep Blue). Just for funsies, here's the estimation for your 'hard mode':
50^30 ≈ 9.31e+50 states which would take roughly 1.48e+29 years at 200e+12 states/sec (a million times faster than Deep Blue). Exponential growth at its best.
And remember, 10 actions is roughly 2 turns and 30 actions about 6 turns in Outwitters.

I invite you to create a chess AI and see how well it performs. And then remember that in Outwitters, you spawn your units and have Fog of War.

---

(07-13-2012 11:19 PM)yasw Wrote:  How about an "AI" that just do random moves? Might not be challenging, but could be fun I have a friend who did his master thesis in computer science analyzing a chess-AI that only did random (valid) moves. Was actually not that easy to beat.

As an academic exercise, it sure is interesting - but given the rules and gameplay of Outwitters, there are a lot more stupid moves compared to smart moves - which means that a random AI like this is likely to be laughed at.