I'm trying to get my head around these concepts, but I do better with concrete examples. I picked a game I'm familiar with that I know that has a decent ai opponent. Kannons & Katapults. If you're not familiar with the games, it's an old bbs door game that i used to play many... well we don't need to go into that. Each player chooses between several actions such as firing kannons, or katapults, buying food, drafting soldiers, buying more kannons or katapults, etc. I'm thinking a minmax solution would be best for this. Now my understanding of minmax is the computer tries to maximize their position while minimizing yours. I've looked at lots of pseudo code that shows something like this: MaxMove (GamePosition game) { if (GameEnded(game)) { return EvalGameState(game); } else { best_move < - {}; moves <- GenerateMoves(game); ForEach moves { move <- MinMove(ApplyMove(game)); if (Value(move) > Value(best_move)) { best_move < - move; } } return best_move; } } but, I'm having a hard time translating that into something I can use. For example, I don't know how to translate "best_move < - {}" into usable code. How can the computer determine what is the best move if it's selection results in a random result? For example the computer might choose to fire their kannons. This could result in no damage or massive damage depending on the result of the random numbers. Can someone show me an example of how to implement this? BTW I'm using Visual Basic. Thanks Mike

if you are dealing with random numbers you will have to dip into statistics a little bit and probability. here's a small example of how you could calculate expected damage (assuming this is a turn-based game).

Weapon - Damage - Chance of direct hit (or chance of it being used)
--------------------------------------
katapult - 200 - 15% (.15)
cannon - 150 - 60% (.6)
other weapon - 75 - 25% (.25)

the damage you could expect per turn in this example is:
200*.15 + 150*.6 + 75*.25 = 138.75 damage


of course this example is probably not completely relevant to your problem, but it does show how you can program the computer to calculate something (in this case, what damage it can expect in its current location, with it's current shields, etc.) and apply it to a minmax algorithm.

although i know this doesn't answer your question, hopefully it will give you an idea and put you in the right direction. the whole idea behind minmax is the computer needs concrete values/scores to determine the best move or whatever is trying to be accomplished.

If you can create a list of possible moves, then you can 'score' the moves. ExpectedDamage (AverageDamage * ToHit%) is a good way to assess weapon output that uses random numbers. And you can add features, like changing the ToHit% based on range, or enemy movement. Maybe the AverageDamage is adjusted, based on enemy armor, or enemy cover.

As game designer, judging the value of moves is partly the math, and partly the designer/artist making it work out the way he wants.

Quote: Original post by chuck22
if you are dealing with random numbers you will have to dip into statistics a little bit and probability. here's a small example of how you could calculate expected damage (assuming this is a turn-based game).

Weapon - Damage - Chance of direct hit (or chance of it being used)
--------------------------------------
katapult - 200 - 15% (.15)
cannon - 150 - 60% (.6)
other weapon - 75 - 25% (.25)

the damage you could expect per turn in this example is:
200*.15 + 150*.6 + 75*.25 = 138.75 damage


of course this example is probably not completely relevant to your problem, but it does show how you can program the computer to calculate something (in this case, what damage it can expect in its current location, with it's current shields, etc.) and apply it to a minmax algorithm.

although i know this doesn't answer your question, hopefully it will give you an idea and put you in the right direction. the whole idea behind minmax is the computer needs concrete values/scores to determine the best move or whatever is trying to be accomplished.

Yes it would be a turn based game.
So I would do better applying a probability of hit to the calculation also? I could establish a probaility of hit for each type of weapon. I think I like that idea.:)
Then I could add that to the best move calculation.
cannons=200*damage*probability
catapults= 3*damage*probablity

Well, I've got a lot more questions about this, but I'll let it go for now.
Thank you for the help
Mike

Quote: Original post by AngleWyrm
If you can create a list of possible moves, then you can 'score' the moves. ExpectedDamage (AverageDamage * ToHit%) is a good way to assess weapon output that uses random numbers. And you can add features, like changing the ToHit% based on range, or enemy movement. Maybe the AverageDamage is adjusted, based on enemy armor, or enemy cover.

As game designer, judging the value of moves is partly the math, and partly the designer/artist making it work out the way he wants.

How would I determine average damage? The only way I can think of is to generate a series of random numbers using whatever I random number generator I'm using for the game. Then average them.
I was planning on using a simple bell curve type random number generator. Just add two random numbers together like you would two dice. I figured I could weight the result to make the computer either harder or easier to beat.

Thanks
Mike

I would start out first by implementing a Finite State Machine (FSM). Then you would have each state that you can do different stuff, like Attacking (firing kannons, or katapults), Buying_Food, Drafting_Soldiers, Buying_Ammo, etc. Each one of those states have different goals and a FSM is a great way to manage that.

After that, you can focus in on what you need to accomplish while in each state. I'll say something on the Attacking state as that's what is being talked about most. You need some way to rate each attack option. How you do that is up to you and could take a little time to simply play with the numbers. I would not use a random number for that because you can augment the shot by a random number after you've chosen the best shot to give it some 'noise', or some random error to give it a little more human feel (as in not being perfect).

If you're having a hard time because the damage from the weapons has some random element to it, then you simply have to think about how you would factor that in when you (a human player) are playing. I'm assuming there's a minimum and a maximum damage each weapon can deal and the actual damage is a random number between that. One way to decide is to always rate based on the worst case scenario (as in only use the minimum damage to do your rating).

For example if cannons have damage between 2-10 and katapults have a damage between 6-8, worst case with the katapults is 6 dmg with cannons being 2. This is very simple and there should be other factors that go into this decision but that should give you an idea...

Hope that helps [grin]

Quote: Original post by mikebres
I've looked at lots of pseudo code that shows something like this:

MaxMove (GamePosition game) {
if (GameEnded(game)) {
return EvalGameState(game);
}
else {
best_move < - {};
moves <- GenerateMoves(game);
ForEach moves {
move <- MinMove(ApplyMove(game));
if (Value(move) > Value(best_move)) {
best_move < - move;
}
}
return best_move;
}
}

but, I'm having a hard time translating that into something I can use. For example, I don't know how to translate "best_move < - {}" into usable code.

Re-reading your original post i think i may be able to offer you more help. here's the translated version of that code in plainer english.

ChooseBestMoveFunction ()
{
if (GameIsOver())
{
return; //no need to continue with function if game is over
}
else //if game is not over, continue with minmax algorithm
{
best_move = NULL; // set the best_move variable to nothing..for now
moves = firstPossibleMove; //moves is temporary holder for current move
ForEachPossibleMove //loop through all moves possible
{
move = currentMove; //set move to currentMove in loop
if (EvaluateMoveScore(move) > EvaluateMoveScore(best_move))
{
best_move = move; //set best_move to the temporary move variable
}
}
return best_move;
}
}


this may help you better translate this into Visual Basic. i haven't done VB for a long time so i would be little help there. if you've ever written a bubble sort, the code is very similar.

obviously i've left out the code for other functions, but the main brains of the algorithm in my example will be in the EvaluateMoveScore() function. this is where you determine what score each move will receive...probably using probability as i suggested before.

Thank you SAE Superman. That makes sense.

I can see that comming up with the evaulation functions may be the most dificult part of this. I was thinking about that today. I played around with some numbers and I quickly realized I am going to have a hard time comming up with something to give me reasonable values for each possible action.

For example firing the cannons looks like a simple calculation cannons=#cannons*%tohit*Random value. I can just divide by a constant to get to be between 0 and 1 or between 1 and 100, or what ever range I choose to use. However, if I try to compare that against the decision to attack with soldiers, well that calculation's going to be a lot different.
I can see what you folks mean when you say I will have to play with the numbers to get good results.

Well, thanks for the help so far. I'm off to play with the numbers!
Mike

Quote: Original post by mikebres
How would I determine average damage? [...]I was planning on using a simple bell curve type random number generator.

averageDamage is the middle of the spread. If the weapon does 3~18 damage, then the averageDamage is 10.5, halfway between 3 and 18.

A formula to do this:
averageDamage = (maxDamage - minDamage)/2 + minDamage

[EDIT]: As chuck22 points out below, this can be done even more simply by:
averageDamage = (minDamage + maxDamage)/2

If the weapon must also roll to hit, then multiply the averageDamage times the %chance to hit. For instance if the example weapon does 3~18 damage, but only hits 80% of the time:
averageDamage(10.5) * toHit(0.80) = expectedDamage(8.4)

expectedDamage means that if you looked at all the tries to hit with that weapon and how much damage it did (including misses), half of the time it did more than 8.4 damage and half of the time it did less. It's a good number for comparing different weapons.

You can even reverse-engineer expectedDamage, if you don't know the weapon's stats. Just keep track of the outcomes of several tries, and take the average of those. But you need about 30 observations for it to be a good estimate.

[Edited by - AngleWyrm on July 18, 2007 8:27:41 PM]

yes, the calculations for using soldiers or for using cannons will be different, but you still need some way to compare the two. and like angle said you should use expected damage as the determiner. it doesn't matter how accurate or damaging a particular weapon or type of attack is, you should always have the computer choose the weapon with the highest expected damage.

lets say a cannon does 200 damage, and its accuracy is decreases by 5% every 100 yards it is from the target.
also, let's say you have a group of soldiers that can do 300 damage at 100 yards or closer, 75 damage at a range between 100 and 200 yards, and are ineffective at anything farther away. soldiers always have a 65% accuracy rate.

obviously there are 2 expected damage calculations. consider both of these scenarios:

1. you are 100 yards away. the expected damage for a cannon is 200*.95 = 190 damage. the expected damage for the group of soldiers is 300*.65 = 195. because the soldiers will have a higher expected damamge, they should be chosen.

2. you are 1000 yards away. here, it doesn't matter how much damage a cannon does because soldiers are ineffective at this range.. so a cannon should be used.

once you figure out how to calculate the expected damage for each particular attack, the rest should be trivial.


@anglewrym
i don't think i've seen an average ever calculated like that before. i suppose it does work. i have always known an average of a and b to be (a+b)/2.

[Edited by - chuck22 on July 18, 2007 3:52:02 PM]