next »

[t-recx]

Hi!

Reich is a turn-based tactics videogame I've been developing in my free time for almost a year now. It borrows inspiration from Advance Wars and Fire Emblem and to a lesser extent other turn-based games I've played while growing up: HOMM 2, Panzer General, Civilization, etc.

It's loosely based on the events that unfolded during WWII. I chose to theme it around WWII history because that would provide me with a framework, lots of reference pics, maps, etc. You start with an easier axis campaign and I'm planning that if you complete all the missions you'll unblock a harder allies campaign.

After reading the wonderful Genetic Programming: An Introduction, I got really interested in genetic algorithms and genetic programming and that was what motivated me to start coding this game. So, the first thing I actually coded when I started was the AI. I made an interpreter for a small c-like language, an algorithm to create random mini programs and another to mix and match programs according to their fitness. So each unit is actually generating about 200 mini programs before it decides which one to use on its move.

Most of the game engine is programmed by now. I'm currently working on a powerup system (similar to the CO power in advance wars) that you activate using cards that you gain as a function of your performance on the various missions. Much of the work left is on the unit and mission design and gameplay balance.

Thanks for reading and hope you've enjoyed the screenies :3

[happymonster]

This looks totally awesome! Love the graphics, and the idea of genetic AI. Please tell us more! :D

[t-recx]

This looks totally awesome! Love the graphics, and the idea of genetic AI. Please tell us more! :D

Thanks :3

Well, I have a series of fitness functions that each AI player uses that I've divided into three types:
R - Recon, functions that evaluate how good the performance of the mini-program that is being analised is at reaching new places and patrolling areas;
A - Attack, functions that evaluate how good is the performance of the mini-program when it comes to getting closer to enemy units/structures and attacking them;
D - Defense, functions that analise how good the mini-program is at finding the best tiles to stand on, how close the unit is to structures that are under-attack and so on.

I then have variables that measure how much energy is allocated to each of the three types, basically a percentage. At the end of the turn I record the game's current state (number of cpu units, number of structures, ammount of tiles that are under fog-of-war, etc) and how effective the current parameter attributes were on advancing the computer's position. Later on the cpu will poll this information in order to adjust the parameters for a given game state. The mini-programs with the best fitness results are also recorded and polled on other turns, to hopefully get some inter-generational evolution as well.

Here's a screenshot of an early test of the interpreter with the genetic algorithm:



In this picture you can see a child mini-program on the top with his parents on the bottom and an ascii representation of a map on the left.

[rivon]

Looks nice. You have the Germany flag wrong though - the swastika should be rotated by 45 degress.

[K1lo]

That's an interesting approach, if I understand correctly you end up effectively brute forcing a good number of move permutations per turn and pick the best performing. Is there a noticeable pause between turns as this calculation + simulation is carried out? An advantage of turn based is you can do a fair bit of offline processing without grinding the game to a halt ;-)

Looking forward to fiddling with I result to see how the AI performs. The visual style is cool too!  

[t-recx]

Thanks for the repplies, guys :3

Looks nice. You have the Germany flag wrong though - the swastika should be rotated by 45 degress.

I had it like this initially, but I felt it looked too blurred...

Genetic algorithms? Fitness functions? Are you sure about this?

Don't worry, if this ends up creating Skynet it will be so slow we'll have plenty of time to destroy it before it destroys us

Will the combat action be presented in cutscenes or on the grid?

Currently combat happens on the grid. When games have cutscenes that are there only for cosmetic reasons I always end up disabling them.

That's an interesting approach, if I understand correctly you end up effectively brute forcing a good number of move permutations per turn and pick the best performing.

Yep, that is the case. One of my colleagues said I was pointing my bazooka to solve the problem.

Is there a noticeable pause between turns as this calculation + simulation is carried out?

With the current configuration (number of individuals x number of generations) a computer player with 15 units takes about 25 seconds to end its turn on my i5. The move generation occurs on a separate thread and the camera focuses on the units that are inside the human player vision range while they move. Everything is awfully unoptimized at this point.

An advantage of turn based is you can do a fair bit of offline processing without grinding the game to a halt ;-)

I've considered it, but most of my fitness functions expect that all other players' units have moved already so I'm not sure yet on how to go at it.

[happymonster]

I remember that Advance Wars and Fire Emblem have more of a bold font. Have you tried that and see how it fits in?

[Paul Jeffries]

The idea for genetic AI here sounds interesting, but I wonder if you're really using the right tool for the right job.  I've done a fair bit with GAs at work (using them to optimise the geometry of building structures) and find them useful, but generally they can only really get you 90% of the way for that particular problem - i.e. its 'best' design can still be improved upon by an experienced human.  Compared to other optimisation algorithms they are also horrifically inefficient.

The clear benefit I would have thought you could get from using them in game AI would be to give the AI the appearance of learning over time and adapting to the player's tactics.  But it seems like you're not using them in this way - you're treating each unit's move as a separate optimisation problem and running the GA only on that without reference to anything else, correct?  If so, what I would suggest is actually using a simpler algorithm for individual unit moves and instead using GAs for the broader-strokes medium- and long-term tactical decisions that set the Goals that the simpler AI subsystems would then try to achieve.  What would be super cool about that is, you could maintain a database of the most effective strategies that the AI has found in similar scenarios and mix those in as seed values, so over time the AI would figure out what strategies were effective and which weren't and so 'learn' the game.

[Mef]

This looks like a really fine idea. I mean, even "loosely
based" on historical events is still better than blue vs red
or some other generic made up factions.

Since I got no experience on coding, I can only comment the
gfx part, here goes:

- The dirt/grass/water tiles a very "grainy" when compared
to AW style. They could be more plain and have less contrast
so that the units and buildings stand out more.
- I like these little tanks and planes, but since every army
uses their own gfx for those, not only differently coloured
ones, why not make them look more like what they're supposed
to represent? I guess the triple-propeller airplane is the
Ju 52? What is the one with two engines? If it's He 111 then
glass front is in order. Tanks and armored cars look nothing
like the usual german vehicles and the soldiers could use
proper german helmets at the expense of smaller body to fit
into their tile size.

[t-recx]

Thanks for the feedback :3

I remember that Advance Wars and Fire Emblem have more of a bold font. Have you tried that and see how it fits in?

Not yet, but it's something I'll probably experiment with at some point.

The idea for genetic AI here sounds interesting, but I wonder if you're really using the right tool for the right job.

It might not be.

Compared to other optimisation algorithms they are also horrifically inefficient.

Agreed.

The clear benefit I would have thought you could get from using them in game AI would be to give the AI the appearance of learning over time and adapting to the player's tactics.  But it seems like you're not using them in this way - you're treating each unit's move as a separate optimisation problem and running the GA only on that without reference to anything else, correct?

No, and I believe that I'm doing what you suggest. Maybe I should have explained better how things are currently working.
Here's a couple of diagrams that go into more technical detail about the AI:

The AI has a set of variables that I'm calling AI Parameters:


Each AI Parameter has a corresponding Fitness Function, these basically attribute a score that ranges from 0 to 1 to each move that a program creates:


The AI Parameters combined with the Fitness Functions help classify a given program:


This ends up shapping behaviour without telling the unit what to do exactly. A bigger percentage attributed to the Recon parameters, for instance, will have the unit roaming about the terrain trying to uncover foggy tiles. While having more in the Attack will encourage agressive behaviours (more proximity to enemy tiles, more attacks, etc.)

Every time the CPU starts a turn it defines how much of a percentage it is going to attribute to each parameter:


This is done by polling past records of turns and selecting the turns with the higher fitness for a given GameState. By GameState I mean how the CPU is perceiving the game in a current turn: How much units do the CPU has? How much enemy units do I see? How many tiles are uncovered? etc.
After I get a sample of turns filtered by the GameState, I use the AI Parameters for the ones with the best fitness and randomize them a little. The ammount of variance I use when randomizing the Parameters is a function of how many records I have on my database. I'm doing this because I believe that I can have a bigger confidence in the results as the number of recordings increase.

Generating the Unit movement is standard GA practice:


Here, too, I have a datatable with programs used in past turns. These are used to get some inter-generational evolution to complement the regular intra-generational one provided by a GA cycle. I filter the datatable by the GameState and randomly pick a program with the ones with the bigger average fitness having a bigger chance to be selected.
After this particular program is evaluated I record its performance back to the datatable.
The best program to come out from the GA cycle is recorded on the datatable as well.

After the turn is done I record the performance of every unit averaging the fitness by its UnitType:


The process is repeated in the next turn.

There are still improvements to be made. For example, I'm thinking about slashing the past performance of units when the CPU loses a structure or the entire game, so that whatever behaviour was incentived in the past turns will be less so in future games.

Despite being aware of its limitations I still consider this to be a good framework.

- The dirt/grass/water tiles a very "grainy" when compared
to AW style. They could be more plain and have less contrast
so that the units and buildings stand out more.

Could you provide me with an edit so I can see what you mean? I used unsaturated colours on the tiles and black outlining on the units to make them stand out.

- I like these little tanks and planes, but since every army
uses their own gfx for those, not only differently coloured
ones, why not make them look more like what they're supposed
to represent?

Small tile size and not very good pixelling skills make that a bit hard, I'm affraid.

I guess the triple-propeller airplane is the
Ju 52? What is the one with two engines? If it's He 111 then
glass front is in order. Tanks and armored cars look nothing
like the usual german vehicles and the soldiers could use
proper german helmets at the expense of smaller body to fit
into their tile size.

Here's the two planes alongside reference pics I used while making them:


Sorry for the long post and thanks again for the feedback :3

[Paul Jeffries]

Aha!  Ignore that post, then - it looks like you're already doing what I was suggesting.  I got confused by your first post where you said that each unit was generating about 200 mini programs and assumed that the GAs were only working on a unit by unit basis.  Really looking forward to seeing how this turns out - it should be a fascinating AI experiment at the very least. 

[Mef]

Here's an original AW screenshot so show my point with the grass tiles.
They're using only 2 colors which are very slightly apart and the whole
thing is very light thus provides much better contrast for viewing the
units.

Plus the green duded have German-like helmets too!

As for the units gfx, I'm shit with pixels, so I can't hep much apart
from voicing my opinion.
 

[t-recx]

I was stuck in crunch time at work during the last week but I did manage to get the card functionality working:

I'm not really happy with the design of the cards at this moment but I'll stay with it until I think of anything better. I made cards that, for a turn, decrease the number of fog tiles, increase the attack points of units and increase the defense points of units. If you have more ideas for powerup cards, I'd love to hear them...

I've also begun iterating the structures panel. Currently I'm showing a list of the structures that the player currently owns with the units that are nearby showing on the list as well. I think that makes it easier for the player to recognize possible enemy threats.

[Mef]

Card ideas:
- Blitz! Move target unit again after attacking.
- Goebels' Propaganda. Target enemy unit can't attack this turn.
- Räder müssen rollen für den Sieg! All player's units have +1 move for this turn.
- Führer's fury. Target enemy unit moves backwards for its full movement range.
 

[Ingshtrom]

I was a Fire Emblem/Advanced Wars junky way back in the day on the GBA.  I like the more gritty and darker colors as compared to the previously mentioned games.  It makes it a bit more realistic and serious in my opinion. 

I am definitely following this!  Keep up the good work.

[impulse9]

This is pretty neat! I love your AI concept. I'm curious how it behaves in practice.

Lovely graphics as well.

[t-recx]

Thanks guys!

Card ideas:
- Blitz! Move target unit again after attacking.
- Goebels' Propaganda. Target enemy unit can't attack this turn.
- Räder müssen rollen für den Sieg! All player's units have +1 move for this turn.
- Führer's fury. Target enemy unit moves backwards for its full movement range.
 

Those are wonderful Mef :3

[Moczan]

As a big Advance Wars and Fire Emblem fan, I'm definitely following this!

[eigenbom]

just found this, wow, will follow to the end!

[deadlyhabit]

Sweet, can never have too many tactics games.
Gonna keep my eyes on this one.