3
$\begingroup$

I'm currently writing the Alpha-Beta pruning algorithm for a board game. Now I need to come up with a good evaluation function. The game is a bit like snakes and ladders (you have to finish the race first), so for a possible feature list I came up with the following:

  • field index should be high
  • in the lower fields my fuel should be high, when coming to the end it should be low (maximum of '10' required to enter the goal)
  • all 'power-ups' must be spent to enter the goal, so prioritize them
  • if it is possible to enter the goal (a legit move), do it!

There could be some more for some special cases.

I've read somewhere that it is the best (and easiest) to combine them in a linear function, for example:

$$0.75 * i - 5 * p - 0.25 * |(f - \text{MAX_FIELD_INDEX}/i)|,$$

where

  • $i$ = field index
  • $p$ = power-ups
  • $f$ = fuel

Since I can't ask an expert and I'm not an expert by myself, I have nobody to ask if those parameters are good, if I've forgotten something or if I've combined the factors correctly.

The parameters aren't that big of a deal because I could use a genetic algorithm or something else to optimize them.

My problem and question is: What do I have to do to find out how to put together my features optimally (how can I optimize the function/parameter arrangement itself)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Based on your description, I'd maximize the following terms:

  • i
  • -max(f - 10 - (MAX_FIELD_INDEX - i), 0) - assuming consumption of one fuel per field; this becomes negative when you have too much fuel
  • a similar function of p, as spending them gets more important when approaching the goal

As having fuel is probably a good thing in the beginning, you could use a term like f. Similarly for the "power packs" (or are they rather "weakness packs"?).

I'd combine the terms using a linear function like you did and let it optimize. You may need more such terms. Maybe it's simpler to get rid of the power packs when you have enough fuel? Then something like -max(p-f, 0) may help.

You may generate some ad-hoc expressions or add some products of your terms as new terms. You may want to do this after the coefficients of the simpler terms have already been optimized (so you help the more complex optimization with a good staring point).

Improve this answer
$\endgroup$
3
  • $\begingroup$ The fuel gets calculated as following: 1 + 2 + 3 + 4 = 10 for 4 fields and so on.. (the little gauss) so going it costs more to go more fields at once. Would this change anything in your function? I think if I have time I'll add the whole game instructions to the question later $\endgroup$
    – po0l
    Jan 12, 2018 at 6:09
  • $\begingroup$ I meant for advancing 4 fields.. e.g. advancing 6 fields whereever you are costs 1+2+3+4+5+6 = 21 fuel $\endgroup$
    – po0l
    Jan 12, 2018 at 6:54
  • $\begingroup$ @po0l Then you may need -max(f - 10 - (MAX_FIELD_INDEX - i) * (MAX_FIELD_INDEX - i + 1) / 2, 0) instead or in addition to the above expression. $\endgroup$
    – maaartinus
    Jan 12, 2018 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .