Decision Making in Strategy Game

Game Mechanics Artificial Intelligence
#1

Heya,
So, well after dozens of failed projects I went back to the roots and finally there is an little Plaything which seems fine so far.

It is a turn based Strategy 2D Game, at the moment completly tile oriented.

Now I want an Computer AI.
And would need to know how to make decisions, especially in an bigger context and not only depending on the turn.
So, how to tell the AI to produce Units /which ones, or produce Technology, to attack etc…
And this, since it´s an Strategy Game, with many Units in one turn.

Of course I came to Behavioural Trees, but they doesn´t seem to fit, or I don´t understand them correctly.
Like, how can I say there: “Okay I have enough Pawns, now produce a Technology”.

When to attack and how to place my Units too…
And all of my Units have different Stats, another thing to care about.

Could you please give me some ideas /Examples how todo that?

#2

This,this
I hope i helped! :smiley:

#3

Thanks, but didn´t helped that much.

Now I knew that I will need Influence Maps - gonna check out how to develop nice ones.

The most Stuff in the Links I have already known.
I just don´t get how to Score the importance of events properly and build the behaviour Tree.
Especially when I want to put everything in one tree it will get really big and too complex. And not that easy to cennect the Logic for ~50 turns and one turn.

But I found an other approach.
They divided it into some different Systems.

  • One for the turn, one for logistics, one which takes car for the next few rounds and one for the goal of the whole game.
    , although I don´t understand the last two.

My idea was now:
For every Unit find out what it is able todo.
If that possibility is helping me to get to an wanted goal -> consider it
In an 2nd Step check out what I need (Military, Tech, Buildings) [how todo that? how do I find out what I need? With an influence map I can tell where I have to sent my Units and maybe if the distribution is uneven that I need to produce some., But so far I have no idea how to program it so that it doesn´t produce the whole time military only.]
Or I could use Alpha/Beta too look forward for ~5 turns and check. But still no idea how to connect everything…

#4

I have some basic understanding of behavior-trees, but i never used them till now and i don’t have any experience with AI in general.
So don’t trust me, i am just writing what i think :smiley:
The main-goal, even for an AI is to kill the enemy/destroy the enemies base, but at the same time, he needs to survive.
So you might consider creating the b-tree with those two main-goals in mind. So basicly you are going backward, from the goal to the task you want to execute now.
Example: You want to attack the enemy. To attack you need units, but you don’t have units. So you need to train units. To train units you need money and camps. To get money you need ressources you can sell. At the same time, you need ressources for the camps. So you have to build factories.
And thats where you start, building factories.
Ofc the b-tree will be much more complicated, so i suggest you to think about it before starting to code. Draw the whole tree and think about it a lot, you might find unhandled scenarios you need to add. As soon as you think you are on a good way, start coding, but the bigger work will be the creation of the tree (on paper).

#5

If you’re looking for actual implementation I’m not sure of any, you could definitley check out AI programming books as there are some decent ones.

Also, there’s a good video about how they made the AI for hearthstone that touches on what you want to do for a turned based strategy game (no implementation though). I don’t remember all of the details, but you basically have the AI take into consideration how much “value” it gets out of a (one) turn, it’s stuff dying vs the enemy’s stuff dying (maximizing damage while taking the least amount). Now in your game you will probably have other things to consider such as positioning, tech, and resources, but you can score that as well. For instance what army is being built, AI builds a counter and tech in that path (factory for tank units or whatever).

Here’s the video: http://www.gamasutra.com/view/news/224101/Video_Building_the_AI_for_Hearthstone.php

Remember the AI just has to look smart.

Edit: oh and if you haven’t seen this thread…

http://www.java-gaming.org/topics/architecture-for-behaviour-trees-with-scheduled-tasks-and-or-event-system/36030/view.html

#6

Quick side note: I would avoid calling behavior trees ‘b-trees’ because that usually refers to something different.

#7

Oh damn, i just wanted to avoid writing behavior, as i use to write it wrong -.- Thanks for the tipp, i’ll correct it!

@topic: There is one more thing i want to say: In some games (Stronghold for example), the enemies have different techniques. Some are weaker and only use weak/basic units, some others use fast units, some focus on defending and have huge strongholds, others continue attacking you, so that you can’t really build a base.
So you might consider creating different enemy-characters. But i would try to start simple, with one behavior only, and then expand to different ones.

#8

I’ve done AIs for over 60 strategy games, ranging from simple movement games to complex
euros. These days, I always start with MCTS. Depending on the game, it works anywhere
from poorly to magically well - but it is trivial to implement for any particular game (once you
have a generic MCTS framework) and the work to create a basic MCTS bot for a particular game
is necessary for other methods, so no effort is wasted.

#9

[quote]Quick side note: I would avoid calling behavior trees ‘b-trees’ because that usually refers to something different.
[/quote]
Hehe thought the same thing :wink:

So, well I checked out some different techniques and AI Books, but I still haven´t found anything practical.
But after some tree drawing I came up with an idea, which seems - at least in theory- nice. It´s totally unperformant but in terms of decision making it should do the job, will check it out.

[quote]…MCTS…
[/quote]
I suppose you mean Monte Carlo Tree Search.

Could anyone explain me that? I have only found a few pages, which are mostly theoretical.
What I got is that it first produces an tree regarding the game state and then has a heuristic function to value every possibility and after that node was choosen it makes n-Random moves?
So, the difference to Alpha Beta Search is that it doesn´t have to generate all child nodes?
And how does that then apply to Strategy games? If I only choose one Node I would only choose one unit although I am able to move ~50 per turn.

#10

The basic idea is to play many games using random moves, all the way to the end. If you win the random game, give positive reinforcement to the root move of the tree. If you lose the random game, give negative reinforcement. There are many variations and different formalisms based on this idea.

AFAIK this was first used successfully in world class Backgammon programs, but it reached critical mass as the basic technique in Go playing programs.

The amazing thing is that it doesn’t require any strategy or knowledge of the game, other than recognizing the winner. Of course, adding some knowledge can help too. For example, I recently made a MCTS robot play several variations of checkers, and with absolutely no tuning it beats me flat using 10 seconds per move.

#11

Okay, one last question, then I am going back to the world :persecutioncomplex:

You say that it doesn´t have to knew any kind of the game.
Does that mean the Client=the Game is generating the possible Moves?

So your MCTS offers an Interface and your Client is in charge to generate the accoring tree and saves it, and the same thing for the valuing of the moves?

#12

You’re on the right track. The individual game has to provide some basic
interface methods, such as “copy the board” and “make a random move”,
while every thing else is done by a generic framework, which is instructed
to start with the current situation and spend N seconds finding the best
move to make.