Jump to content
  • Advertisement
Sign in to follow this  
n0b

Finding a fitting eval-function

This topic is 4612 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there. I was not quite sure wether to post this question under AI or MATHS so i'll just post it here 'cause its more to the topic i guess. Anyway, i'm trying to find an evaluation-function which is able to calculate the fittness of a R2 Pos. The function should only have outputs between zero and one, cause there ll be a limes which controlls if there is work to be done by the AI. -Nothing out of the ordinary here- The base of my calculations is a 20*21 2D Grid. [0/0]...[0/20] . . [19/0]...[19/20] The positions are jugde on the base of their distance to five(three) points, two are fixed. It also exists a per-field changing factor n. Lets call those fixed points A(2/2) and B(18/2), the point which arent fixed are C(c1/c2), D(d1/d2) and P(p1/p2). But the Points C and D are just optional. Sometimes they dont exist. Sometimes they are identical to A(C=A) and B(D=B). The point beeing judged is M(x/y). Playing area looks like this : [x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x] [x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x] [x][x][A][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x][x] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][C][ ][ ][ ][ ][ ][D][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][M][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ]

[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] n is a factor which lies between 0 and M. the closer n gets to M, the better. n = M is possible. I ll first presume that the points C and D are nonexistant : Because of the gamerules point M is an interesting point if : The distance MA is less than the distance MB, the distance MP is less than the distance MA, and n is quite high. therefor a field is attractive if (MB/MA) > 1, (MP/MA) > 1 and n > 0 so my eval function would be (MB * MP * n) / (MA)^2 But this ll only lead towards one thing : all points close to A will have super-high-fittniss because MB*MP*n is divided by one or a little more, even if n is not very good. And the fittness values are greater than one. if the Points C and D are existant than M is fit, if : the distance MC is less than MD, CD > CA, CB > CA, PC < PD and n high. so i could say my eval-value is good if (MD/MC) > 1, (CD/CA) > 1, (CB/CA) > 1, (PD/PC) > 1 and n high,so func = (MD * CD * CB * PD * n) / (MC * CA^2 * PC) Because C can be identical to A and D ident. to B the eq. could look like (MB * AB^2 * PB * n) / (MA * [AA^2=0] * PA). Ups, division through zero. This will also ony lead to one thing : all points close to P will have a super-high-fittness or i ll get a division error. I m not sure why but i m unable to find a function where all factors make up a value between 0 and 1 and where no places have a super-high-fittnessI feel like i left some important factors along the way ...Um...any ideas ? EDIT : dunno if it helps, here's a short review of the game : there are 5 snakes, 2 Players. To win the Player has to get more snakes to his own hole than the other does. He can do that by using some meat. Each player can place 10 meatballs in order to make the snakes move their way. The snakes always move to the closest distance, calculated using euklid. In order to find a good position for my meat balls i thought it would be good if my AI would give each field a fittness value, so each field gets a calculated fittness. If some fields exist which fitness is above the limes (dunno how to determine the limes yet, though) the AI is going to place a meatball on one of them - else no meatball will be used. This is important cause i only have ten of them. So a field is interesting if it attracts many snakes, lies in the direction of my own hole, is close to the snakes (so the enemy wont make them go his way) and is far away from the enemies hole. the point P is the midpoint of the Snakes attracted by a field. so if a field attracts three out of five snakes, P is the midpoint of these three snakes. Guess thats all to say about this game. Maybe i ll make another post in the AI section just to see if theres a better aproach to programming a valuable AI-Enemy...

Share this post


Link to post
Share on other sites
Advertisement
After all i figured out a quite good working alternativ :

( (MB+MP) / (MA+MP) ) * n

this gives me quite acceptable points but the limes doesnt work, though.

So i m using a simple gamefield analysis which quits the whole thing if there is
no need for a move.

Writing down my problems sometimes helps :D

thanks anyway :)

Share this post


Link to post
Share on other sites
It seems to me that each criteria could be used to create independent attraction/repulsion field, that are overlayed together to produce a final fitness value.

For example, the distance from each point to each snake could determine an attraction field, where the value at any point is 1/d2 (d being the distance to the snake in question, if d = 0 then set the value to something high). You could have an attraction field for your hole (either A or B). Then you could create an inverse-squared repulsion field for the opponent's hole (and meatballs?), where the value at any point is MAX_DISTANCE - 1/d2. Overlay all these fields by adding them together, and normalize to the highest value to get it into the range [0, 1]. Unless I thought this through incorrectly you should get a good fitness value for each point.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
It seems to me that each criteria could be used to create independent attraction/repulsion field, that are overlayed together to produce a final fitness value.

Yes. That's the idea i'm working on. As you can see from my first post i tried to combine all those factors into one function to calculate the fitness directly.

Quote:

Overlay all these fields by adding them together, and normalize to the highest value to get it into the range [0, 1].

Humm...Yea. Actually i thought the range [0, 1] would be helpful 'cause it would be easier to calculate a limes. 'Cause if i had a well calculated limes then the AI could choose between a number of moves which all have about the same fitness. But that should work if i didnt normalize to the highest, too. And i could make the algorithm a little faster by not normalizing each value. It's no must-have after all.

I'm not quite sure but i guess your step-by-step method would proove very helpful as soon as it comes to "look-aheads", judging using a specified depth - it would be nothing more than calculating and exchanging a value-table to get to know how the area would look after some moves.
I guess i ll try out both methods. They are not that different, after all.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!