Why an AI for Outwitters is hard to do

[yasw]

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.

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

[Cookie]

Yes, probably hard, but not actually that hard. E.g. much much easier than Starcraft.

First step: Remove the fog of war (no need to do this in the end, but necessary when you start writing the AI).

Second step: Some kind of goal based search. Goals will be things like taking out units, see a large portion of the board, hitting the base, and create new units. Actually, the branching is not that high in practice, because for many things there will be one or a few best moves.

The one tricky thing is the balance of building up an army and attacking the base. But this is hard for human players too.

I am not saying it is easy. But also, I don't think it is quite as hard as you make it sound. Summoner Wars is one recent similar game for iOS with AI. It does not have fog of war, but it does have high branching and the players have hands that are hidden to the opponent. The AI is not very good, but it is passable.

[Kamikaze28]

(07-14-2012 01:43 AM)Cookie Wrote:  Yes, probably hard, but not actually that hard. E.g. much much easier than Starcraft.

The perception of difficulty is highly subjective. My primary goal with this thread is to show that AI creation is not something you can do in a few weeks and expect jaw-dropping results and to show what goes into writing one. If you're eager, you can develop a challenging AI for Outwitters, it would at minumum make a good BSc thesis in AI research, I'd wager.

(07-14-2012 01:43 AM)Cookie Wrote:  First step: Remove the fog of war (no need to do this in the end, but necessary when you start writing the AI).

Okay, I see now that there are two different ways to go about the Fog of War for the AI:

1. Remove FoW for the agent and make up for its omniscience somehow.
2. Deal with it the way a human would (through estimation, inference and exploration).

I'm an advocate of approach 2, but I accept the existence of 1.

(07-14-2012 01:43 AM)Cookie Wrote:  Second step: Some kind of goal based search. Goals will be things like taking out units, see a large portion of the board, hitting the base, and create new units. Actually, the branching is not that high in practice, because for many things there will be one or a few best moves.

You cannot pre-define 'best moves' in an AI, it will have to explore states and then decide if they are worth to explore further or not. The priorities of these goals is also something that came up earlier in the thread which is basically the evaluation function for the states.

(07-14-2012 01:43 AM)Cookie Wrote:  The one tricky thing is the balance of building up an army and attacking the base. But this is hard for human players too.

Evaluation function - designing that piece of the puzzle is really hard and differentiates mediocre game AI from excellent ones. You don't want an AI that goes for your Wit Spaces first, no matter the situation. It will have to work from the current state and determine which goals are attainable and how useful they are compared to each other.

(07-14-2012 01:43 AM)Cookie Wrote:  I am not saying it is easy. But also, I don't think it is quite as hard as you make it sound. Summoner Wars is one recent similar game for iOS with AI. It does not have fog of war, but it does have high branching and the players have hands that are hidden to the opponent. The AI is not very good, but it is passable.

I just watched a YouTube review of the board game to get an idea of the game. It looks very much like Hero Academy to be honest. I'm not familiar enough with this game to compare it to Outwitters in regards to the difficulty of creating an AI for it though.
As a developer, you are going to have to ask yourself beforehand: are months of development time worth the result of a 'passable AI' as you call it.

[ArtNJ]

Uniwar (another IOS asynch game) has AI. Its terra-bad, but it has AI. It has a "campaign" where the computer is given massive advantages to compensate for its stupidity. It doesnt have skirmish mode, not sure why, since the terra-bad AI is already ready.

Were OML to spend the time and money, this is the kind of AI we would most likely have. As Kamikaze has said, AI is hard.

This type of AI/campaign does very little for me.

[Kirenx]

(07-14-2012 01:43 AM)Cookie Wrote:  I am not saying it is easy. But also, I don't think it is quite as hard as you make it sound. Summoner Wars is one recent similar game for iOS with AI. It does not have fog of war, but it does have high branching and the players have hands that are hidden to the opponent. The AI is not very good, but it is passable.

A few things about Summoner Wars. SW is a much simplier, more straight-forward game. This is because it has to be as it comes from a physical board-game. Thus unlike either HA or Outwitters, SW is structured into phases, a movement phase, an attack phase, etc. This limits what options are available for AI at any one time by a huge amount. HA and Outwitters have a far larger range of options everytime an AI would have to choose. The difficulty for a game like Outwitters then becomes that you have such an overwhelming amount of decisions at once as all the phases are merged, essentially everything SW does over an entire round is an option during a single action. I can't find my scientific calculator at the moment, but someone with some knowledge of statistics could probably whip up the average range of actions in an SW phase versus the range always present in an Outwitters turn. I'd bet the difference would be huge.

[Amateur6]

Non-programmer’s two cents: this thread should be stickied!