[HD 3] AI

Discuss everything related to HD3
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

[HD 3] AI

Postby Greywing » Sun Jan 12, 2014 2:52 pm

Todays blogpost goes in more detail about the 'outer' structure or framework of the AI - this the code that makes sure the AI goes through a number of steps each turn, calling upon actual AI code that allows it to make decisions. This framework isn't that complex in itself, but it's required before i can get started on adding in actual AI code itself.

read the blogpost here : http://nulll-void.com/games/wiki/doku.p ... _ai_cycles
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
Ken Ddoox
Posts: 185
Joined: Wed Jul 31, 2013 11:40 am

Re: [HD 3] AI

Postby Ken Ddoox » Sun Jan 12, 2014 5:14 pm

So this stuff itself is very technical and I couldn't imagine how you (and some people too) could write all of this by yourself. Explaining the details seems complicating enough, let alone understanding it and the write the whole thing down. I study some excel and coding when I was younger but that's literally just kid stuff when compared to this level of complexity. I'm really just amazed! There's not much on-topic things that I can say really, you are awesome! Writing AI and stuff :D
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Jan 12, 2014 5:55 pm

At the core what i'm doing is trying to turn into code what i would do in various situations. With a game like HD, there's not really a correct answer to what is the best thing to do in a given situation (perhaps in some situations, yes, but in most it's not that clear). There isn't f.i. a mathematical formula that i can come up with that would make the AI do the ideal thing for every possible combination of boardstates and playable cards.
The hardest part (imo) is trying to figure out what i would do in hypotetical situations and turn that into code. The AI (as a whole) is probably the biggest and most complex element in HD, all the rest is mostly pure logic and math, but an AI needs to be more 'organic'.

Next week i'll likely talk about the different AI setups in have in mind, the framework is nothing compared to that when it comes to complexity :p
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
FrancoK
Posts: 346
Joined: Wed Nov 16, 2011 7:51 am

Re: [HD 3] AI

Postby FrancoK » Sun Jan 12, 2014 8:05 pm

A couple of things that AI should take care of:
1. Spare Structure (maybe ship, too). Keep some structure in hand just in case the enemy A. destroys one of the deployed ones or B. force AI to drop a card in hand (increase the chance to drop a "less useful" redundant structure instead of the life saving card).

2. The energy production is very important at the beginning of the game, less important if you have 99+. Now AI destroys structure that protect/retaliate/attack substituting them with energy producing ones, even if it has plenty of energy (the energy they use and need I mean). Sometimes this make it suffers less (I can kill it more quickly), sometimes let me launch ship I won't be able to cast if that structure was in play.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Jan 12, 2014 8:44 pm

1. Ai has never been good at preserving stuff for future turns, this is rather hard to do, but it will be looked into.

2. The AI does take into account the amount of energy it has in stock when deciding things. Every turn, the AI calculates the average and maximum costs of cards still in the deck and hand, and it uses these numbers to determine how important additional energy generation would be. Structure recycling will be completely overhauled, so some of the problems you mention might be fixed by that (as i doubt they were a result of the AI wanting more energy).
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
FrancoK
Posts: 346
Joined: Wed Nov 16, 2011 7:51 am

Re: [HD 3] AI

Postby FrancoK » Mon Jan 13, 2014 2:20 am

1. You can try an incentive if there are 2 free spots or more up to 100% (unless void, meteors or other environment kicks in), lower the actual chance by 80% if there is only a spot (like reasoning: this is the last "free" spot, is the card correct?) and finally lowering to 1(0)% of the actual chance if you have to destroy a previous structure unless:
1.A The AI already has a copy of the destroying structure in hand (use 50% in this chase)
1.B The new structure is an upgrade of the old one (same structure, higher level, produce the same energy and more, and so on, 90% should fit)
1.C The new structure is a lifesaver (increase resistance/HP or so) without it the base is destroyed next turn (100% chance of course)

Of course adjust the % as you see them fit. ;D



2. Good. :D
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Jan 19, 2014 1:58 pm

A new blogpost - quite long and a bit technical - to explain simulating boardstates for the AI : http://nulll-void.com/games/wiki/doku.p ... imulations

Basically, the AI needs to be able to predict the outcome of abilities it can play, to see how beneficial those abilities would be to the AI. HDx ran a local simulation setup : the AI tried to predict the effects of abilities or cardplays, but only looked at a small part of the board and thus it only had to predict the impact on this part of the board. Next to being not completely accurate, there's also the risk of the AI not being able to take into account all the effects of playing a card or activating an ability.

I'm currently investigating if a full-simulation setup can work for HD3. In such a setup, the AI makes an exact copy of the current board, then simulates the effects of the card or ability it wants to play on this copy. Since this copy is a full board, and the accuracy is much higher (due to the AI using existing ability code, rather than its own code), the AI has access to a very good prediction of a future where this card would have been played - and then it can compare this with the current boardstate to see if it likes the differences between these two boards.
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
Ken Ddoox
Posts: 185
Joined: Wed Jul 31, 2013 11:40 am

Re: [HD 3] AI

Postby Ken Ddoox » Sun Jan 19, 2014 2:07 pm

New post!

While reading, all I could think of was, since that's how the AI works, maybe now would be the time to implement the "invisible" ability that lasts for a few turns, only the positions of the ships and structures are shown, all energy, stats, actions ect is hidden. This might trick the AI into taking less calculated moves. Works for human better, so cards that have effects like this could be restricted to PvP only.

Also, the post is VERY long, and with a wide screen, my eyes have to move horizontally too much. Not to complain, I like reading your blog posts but they're just simply a very tiring task :P
User avatar
FrancoK
Posts: 346
Joined: Wed Nov 16, 2011 7:51 am

Re: [HD 3] AI

Postby FrancoK » Sun Jan 19, 2014 3:34 pm

Greywing wrote:A new blogpost - quite long and a bit technical - to explain simulating boardstates for the AI : http://nulll-void.com/games/wiki/doku.p ... imulations

Basically, the AI needs to be able to predict the outcome of abilities it can play, to see how beneficial those abilities would be to the AI. HDx ran a local simulation setup : the AI tried to predict the effects of abilities or cardplays, but only looked at a small part of the board and thus it only had to predict the impact on this part of the board. Next to being not completely accurate, there's also the risk of the AI not being able to take into account all the effects of playing a card or activating an ability.

I'm currently investigating if a full-simulation setup can work for HD3. In such a setup, the AI makes an exact copy of the current board, then simulates the effects of the card or ability it wants to play on this copy. Since this copy is a full board, and the accuracy is much higher (due to the AI using existing ability code, rather than its own code), the AI has access to a very good prediction of a future where this card would have been played - and then it can compare this with the current boardstate to see if it likes the differences between these two boards.

Very good!

About 4. random elements, if the AI tries to figure what is going to happen, in not cheating, even when includes random numbers. in the example. anyway the AI should consider that there is one change on three to kill the enemy.

About 5. invisibility You can log everything and mark every line with a flag(visible for all/only for debugging) and show normally only the log for "visible for all" and use a special key combination to see them all, if/when needed.

About simulation, to see the full effect of a move (I.E. launch a ship) you should simulate what happens after the launch, after the attack, after the counterattack (as is, like if the enemy do not play anything, but with all the auto effects) up to the next turn, after the maintenance phase, IMO. Going any further is useless; if this takes too much time you can use it only for some cards, anyway the AI should check it at least once, without any card played, to see if the next turn is going to lose the battle.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Jan 19, 2014 3:38 pm

I think it would actually be harder to create an AI that has to make decisions on partial information - if you ignore the unkown info, then it's easy (as you have less data your AI needs to take into account), if you don't and you try to make educated guesses then things get complex.

If i were to add abilities like that i would have to make a new AI or set up some filter in the system that copies the current board, so that only a part of the data is copied (whatever is not hidden).

But i don't see much tactical use in such an ability. Perhaps more like a environment. I remember something like this was mentioned on the forum before : new cards start out with no visible stats (except play abils as they trigger when cards enter play), when ships attack, you learn their attack strength, when cards activate abils, you learn their actis, etc.
But as a player you have the advantage that you can remember cards and if you see a red card with the auto abil of a vector, you have a good chance of knowing its a vector. Again, that's something much harder to implement for an AI. So something like this might be more interesting when both players only have custom cards, so there can't be any guessing at all.
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Jan 19, 2014 3:47 pm

FrancoK wrote:About 4. random elements, if the AI tries to figure what is going to happen, in not cheating, even when includes random numbers. in the example. anyway the AI should consider that there is one change on three to kill the enemy.


The thing is that there's no middle ground - making an AI that can guess is very hard. Averaging the results of all possibilities can work for some abilities, but definately not all - especially when the difference between some of the possibilities can be very large (as in the example of the blogpost - if an ship deals 3 to 5 damage to a player with tons of HP, the ability gets a low cost, if the same happens to a player with 4 HP, the ability might get a high score, but end up doing 3 damage).
Thus, predicting the random outcome makes the AI much stronger in these cases. Technically it's cheating, but since the AI will never be as good as a player, maybe it deserves a (rather small) cheat like this. It's hard to say at this point as it depends on the number and strength of abilities that have random components.

FrancoK wrote:About 5. invisibility You can log everything and mark every line with a flag(visible for all/only for debugging) and show normally only the log for "visible for all" and use a special key combination to see them all, if/when needed.


Tracing out all information is possible, but the AI will be doing multiple simulations, for various cards, over various targets, so the amount of info that needs to be checked is huge. Its a big difference between looking at an image of the boardstate compared to looking at a list of data that represents this - just imaging what it takes to write out the state of an entire board : att/def for all ships, contents of energy stock and so on.
Also, i can't just render this data easily, the simulation only exists as data, but so does the real board - the renderer then interprets this data to draw correct things on the screen. This renderer is complex as is : many images, like cards are made up in layers, but it's also a mix of stuff that has been rendered in the past and is preserved and stuff that gets rendered anew every frame (this all related to performance). So i can't really add a button for instance for testing, that allows the game to render the state of the simulation - if that were possible it would help, but even then it would also mean slowing down the AI so that it doesn't makes 15-100 simulations a second (the renderer can't even do this much work this fast anyways).

FrancoK wrote:About simulation, to see the full effect of a move (I.E. launch a ship) you should simulate what happens after the launch, after the attack, after the counterattack (as is, like if the enemy do not play anything, but with all the auto effects) up to the next turn, after the maintenance phase, IMO. Going any further is useless; if this takes too much time you can use it only for some cards, anyway the AI should check it at least once, without any card played, to see if the next turn is going to lose the battle.


Yup, this has to be seen on a per-card or even per-ability basis. The big inaccuracy comes from the fact that a simulation that goes past the own turn simply can't take into account the other cards AI might play, or that the other player might play. It gets worse in games with multiple players, since then players can choose who to attack, etc.
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
FrancoK
Posts: 346
Joined: Wed Nov 16, 2011 7:51 am

Re: [HD 3] AI

Postby FrancoK » Mon Jan 20, 2014 7:07 am

Sorry, my typo; where I wrote "in not cheating" I mean "is not cheating".

To calculate the minimax of the damage is something I usually do, as most players I think, so nothing wrong if AI does the same.
Sure the AI can be more precise than us, but with those numbers, there isn't a lot of difference. It will be very different if/when you'll implement the "thousand change", so when vector is going to have (I invent) 1024 attack +0,1% for experience +0,5% for the ancient enemy + 0,3% for an already beaten enemy and so on.

About AI, since it can't guess the result, using the average of the results is fine (no need to calculate all the result and get the average, get the average damage and calculate the results of the fights on that), but (a big but) let AI calculate the chance to win instantly (1/3 in the example). With 5 damage it kills the enemy base, with 4 it doesn't. So if another cards deals exactly 4 damages, the average is the same, but the card in the example as also 33% to kill the base and AI should prefer it.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Mon Jan 20, 2014 1:26 pm

It needs to be seen on a per-ability basis as well. Some abilities with random components won't have a big influence on the board - example : drain X random energy from opp, where X is randomly chosen amount. In this example, you can average the X and do simulations with that number - it won't be 100% accurate, but it's much simpler to setup.

But in cases where an ability can have a large impact on the board, i think accuracy should be as close to perfect as possible. In a case like this i would still prefer to have an AI that can predict the future (ie it knows what the random number will be) and let it make decisions based on that knowledge.
Yes in your example, if the opposing base has 4 HP, if the AI has a card that can deal guaranteed 4 damage and one that deals 3-5, the AI should choose the guaranteed 4 damage card - but if you average 3 to 5, you have 4 as well, so now the AI has two cards that deal 4 damage in a simulation, yet one simulation is not guaranteed to be correct. With a setup like this you need (after the sim) to add something so the AI is capable of seeing the difference between the guaranteed and random action, and that is something that's not
available in the sim, since both sims will have the same result (both actions dealt 4 damage).

If the Ai has an ability that does 3-5 and the base has 4 HP left, and the ai does a sim with the average, but the action ends up doing 3 damage, then what? The AI might have no energy left to play other cards - it could have had other options that would have guaranteed a kill, yet this card received a high score since it killed the opponent in the sim. Then players tell me the AI is stupid - in cases like this i think it's important to avoid situations where the AI can make stupid decisions.
If i were in that position as a player, i wouldn't have played that card unless i was sure there was nothing else i could try.

For some random abilities, you can average, for others it might be better to take the lowest number, for other it might be the highest number - for some the only solution could be to run simulations for all values. I don't know, since i haven't had to write code yet for AI that deals with random elements (there's only a very small set of cards in the game right now). To keep things (relatively) simple, giving AI access to the random number generator so it can predict random values seems the best overall solution. That way, when the AI needs to simulate an action that deals 4 damage, or one that deals 3-5 damage, it only needs to look at the random number generator to see what the next value is that it would generate, instead of trying to figure out if it needs to average, min/max or multi-sim this ability.

Anyway, that's my theory at the moment - i need to have a look at all abilities with random components to get an idea of their potential
impact on the game, before i take a decision.
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
joacobanfield
Posts: 791
Joined: Tue Apr 02, 2013 2:56 am
Location: Home.

Re: [HD 3] AI

Postby joacobanfield » Tue Jan 21, 2014 4:20 pm

I like the AI fixes for HD3. I´m tired of stupid mistakes. (reading posts took me sooooo long)
We are "Joacobanfield".
I joined up about 2 years ago.
Wrote a bit of TTOFH and a little secret project.
Oh, I also love Disney/Pixar´s Inside Out.
User avatar
FrancoK
Posts: 346
Joined: Wed Nov 16, 2011 7:51 am

Re: [HD 3] AI

Postby FrancoK » Wed Jan 22, 2014 2:06 am

Greywing wrote:It needs to be seen on a per-ability basis as well. Some abilities with random components won't have a big influence on the board - example : drain X random energy from opp, where X is randomly chosen amount. In this example, you can average the X and do simulations with that number - it won't be 100% accurate, but it's much simpler to setup.

But in cases where an ability can have a large impact on the board, i think accuracy should be as close to perfect as possible. In a case like this i would still prefer to have an AI that can predict the future (ie it knows what the random number will be) and let it make decisions based on that knowledge.
Yes in your example, if the opposing base has 4 HP, if the AI has a card that can deal guaranteed 4 damage and one that deals 3-5, the AI should choose the guaranteed 4 damage card - but if you average 3 to 5, you have 4 as well, so now the AI has two cards that deal 4 damage in a simulation, yet one simulation is not guaranteed to be correct. With a setup like this you need (after the sim) to add something so the AI is capable of seeing the difference between the guaranteed and random action, and that is something that's not
available in the sim, since both sims will have the same result (both actions dealt 4 damage).

If the Ai has an ability that does 3-5 and the base has 4 HP left, and the ai does a sim with the average, but the action ends up doing 3 damage, then what? The AI might have no energy left to play other cards - it could have had other options that would have guaranteed a kill, yet this card received a high score since it killed the opponent in the sim. Then players tell me the AI is stupid - in cases like this i think it's important to avoid situations where the AI can make stupid decisions.
If i were in that position as a player, i wouldn't have played that card unless i was sure there was nothing else i could try.

For some random abilities, you can average, for others it might be better to take the lowest number, for other it might be the highest number - for some the only solution could be to run simulations for all values. I don't know, since i haven't had to write code yet for AI that deals with random elements (there's only a very small set of cards in the game right now). To keep things (relatively) simple, giving AI access to the random number generator so it can predict random values seems the best overall solution. That way, when the AI needs to simulate an action that deals 4 damage, or one that deals 3-5 damage, it only needs to look at the random number generator to see what the next value is that it would generate, instead of trying to figure out if it needs to average, min/max or multi-sim this ability.

Anyway, that's my theory at the moment - i need to have a look at all abilities with random components to get an idea of their potential
impact on the game, before i take a decision.

All right, I'll tell you what I see:
An already independent, capable developer/analyst/producer able to listen to the clients (the people that plays your games) that has no problems to reinvent the game itself, keeping the same initial spirit in it.

About me, I hope discussing it with you publicly will help you to see what some players perceive/want from the game and help other players with even different ideas to do the same.

Back to the point.
The example is: AI has 2 cards in hands 1 deal 4 damage to enemy base, the other 3 to 5; the enemy base has 5 HP left. AI has energy only for one of the 2 cards.
We have to give AI a chance to understand is better to use the second card.
My idea is to let AI average both damage to 4, but in the result for each card launch, it has to write down the % of killing the other base.
The results should be 3:
1. Do nothing. 0% to win.
2. Launch card 1. 0% to win.
3. Launch card 2. 33% to win.

This way the choice should be to launch card 2 to maximize the winning chance.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Wed Jan 22, 2014 9:50 am

Heh i like talking about mechanics in game - writing out and explaining how they work with examples is something i do before actually starting to implement complex mechanics. Going over it again afterwards with different examples occasionally leads to me finding special cases that need special extra code to handle them - or even a complete overhaul of the system.

In your example, whether or not AI wins depends on the random roll of just one card. That's the situation i'm trying to avoid to begin with, but there's always going to be rare cases i guess.
The problem is that the AI needs a starting value of the damage this card could deal before it can being a simulation. So it needs to decide what to take (fi 4 - the average) first. Once the simulation is done, the AI needs to interpret the results, and neither case has a sim where the opponent dies. So if the AI needs to take into account the possibility of one card having 1/3rd chance of killing the opposing base, the AI can only know this if there is a sim where the opposing base actually dies. For that to happen, the AI would have to run a sim with the card it's max damage (5) or run 3 sims and somehow average the results (which i'm trying to avoid). In the first case, we're back at what i said before - the AI needs a step where it can decide what value of a random card will it use to run the sim? And the simplest solution is to give the AI the correct value via the pseudo random number generator. Sure it's cheating a bit, but the more i look at this, i'm convinced that the impact will be minimal.
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
FrancoK
Posts: 346
Joined: Wed Nov 16, 2011 7:51 am

Re: [HD 3] AI

Postby FrancoK » Thu Jan 23, 2014 3:06 am

Greywing wrote:Heh i like talking about mechanics in game - writing out and explaining how they work with examples is something i do before actually starting to implement complex mechanics. Going over it again afterwards with different examples occasionally leads to me finding special cases that need special extra code to handle them - or even a complete overhaul of the system.

In your example, whether or not AI wins depends on the random roll of just one card. That's the situation i'm trying to avoid to begin with, but there's always going to be rare cases i guess.
The problem is that the AI needs a starting value of the damage this card could deal before it can being a simulation. So it needs to decide what to take (fi 4 - the average) first. Once the simulation is done, the AI needs to interpret the results, and neither case has a sim where the opponent dies. So if the AI needs to take into account the possibility of one card having 1/3rd chance of killing the opposing base, the AI can only know this if there is a sim where the opposing base actually dies. For that to happen, the AI would have to run a sim with the card it's max damage (5) or run 3 sims and somehow average the results (which i'm trying to avoid). In the first case, we're back at what i said before - the AI needs a step where it can decide what value of a random card will it use to run the sim? And the simplest solution is to give the AI the correct value via the pseudo random number generator. Sure it's cheating a bit, but the more i look at this, i'm convinced that the impact will be minimal.

Ok, here you are a quick procedure to use in AI:
The cards damages the opponent base? If not set 0% kill go on as usual (GOAU).
The base damage is fixed? if yes set 100% kill if it kill the enemy or 0% kill if it doesn't then GOAU.
The max base damage kills the enemy? If not set 0% kill and GOAU.
The min base damage kills the enemy? If yes set 1000% kill and GOAU.
Calculate the chance of other results and the % kill accordingly, then GOAU.

You can add it when evaluating if a cards has to be played, before any other evaluation.
Most of the time only the first question is going to be done, at the end you're going to know for every cards if they have the chance to kill the enemy and how much it is.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Jan 26, 2014 2:14 pm

New devblog post : http://nulll-void.com/games/wiki/doku.p ... n_accuracy

Ran into an interesting problem when looking at how to set up simulations for combat phases. At least i'm getting real close now to finishing the 2nd layer of the AI, then i can start on the actual code that allows the AI to make proper decisions.
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
Greywing
Posts: 3071
Joined: Sat Nov 06, 2010 5:47 pm
Contact:

Re: [HD 3] AI

Postby Greywing » Sun Feb 02, 2014 2:59 pm

2nd layer is in, from the coming week onwards i can finally start on the code that does the actual scoring of cards and abilities.

Devblog : http://nulll-void.com/games/wiki/doku.p ... #ai_layers
SVC - NULLL games.
Found a bug or have a question? PM me or post on the forum.
User avatar
Ken Ddoox
Posts: 185
Joined: Wed Jul 31, 2013 11:40 am

Re: [HD 3] AI

Postby Ken Ddoox » Sun Feb 23, 2014 2:25 pm

Gosh I've been slacking on blogpost these past few weeks.

Well, I can't seem to find anything to say. The only thing I can muster now is how much I admire you. Seriously, everything from art to coding. How many lines are there as of now? It must be countless hours and coffee I presume? :D

Return to “Hidden Dimensions 3”

Who is online

Users browsing this forum: No registered users and 1 guest