3

I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the policy suitable for updating the weights of the function. One policy I have in mind is to check whether a move is good or bad before updating weights but I don't really know how to implement it. Thus I need ideas and pseudo code please.

Improve this question
6
  • 2
    This question is probably more suitable for the Programmers SE.
    – Henry Keiter
    Commented Aug 25, 2014 at 16:04
  • This question is more suitable for Stack Overflow SE.
    – AlwaysLearningNewStuff
    Commented Aug 25, 2014 at 19:15
  • 4
    You might want to look at chess programming wiki.
    – Pete Becker
    Commented Aug 25, 2014 at 19:37
  • 1
    This is a really hard problem, I don't think any strong chess engines update the weights automatically.
    – RemcoGerlich
    Commented Aug 26, 2014 at 11:21
  • 1
    Deep Blue self trained its evaluation function based on how well it could match the moves of GMs... so this is a common strategy.
    – tbischel
    Commented Aug 26, 2014 at 23:42

2 Answers 2

Reset to default
2

In Chess, you use SPSA and CLOP. Those are the algorithms used by Stockfish in Fishtest to tune its parameter. The algorithm worked so well that it made Stockfish be the strongest engine in the world.

Please note that the algorithms are very complicated mathematically. One could write a PHD thesis on this topic. In SPSA, you start from a best guess from the value. Then play games, use those games to derive a better gradient for the next series of parameters.

The maths is very hard, but it all boils down to some statistics - you play games, and use those games to derive a distribution to update the parameters you want to tune.

Please read:

http://talkchess.com/forum/viewtopic.php?start=0&t=50823&topic_view=flat

and

https://groups.google.com/forum/#!searchin/fishcooking/SPSA/fishcooking/WNrxeXAJ6VI/ZkCnRv4I_qEJ

Improve this answer
1

I might approach this via genetic algorithm.

  1. Each param in the gene represents one weight you use for tuning.
  2. Have a fairly large test suite of positions + moves made by grandmasters (randomly over many middle game positions).
  3. Create a random initial population of genes to be used in competition. You can include any feature weights you already believe to be good as well.
  4. For each gene, for each position, do a shallow search based on how much training time you want to take.
  5. For every position where your program produces the same move as a grandmaster, add one to a total associated with a gene. This total is what the GA should try to maximize.
  6. Random pairing for mating rights competition based on above score, and breed the results using standard GA techniques.
  7. Run until convergence.

Whatever final weight you get becomes your feature weight.

Improve this answer
6
  • 1
    +1, and I hope someone will perform the following offshoot of this idea: for a handful of top players, craft an evaluation function via the described method using only the moves of a single player in order to test gene fitness. Then, build engines that are identical except for the individually-tuned evaluation functions, and have them duke it out. It may be the closest we could ever come to, say, answering the age-old question of who would have won the Fischer-Karpov match that never happened :-) ... (cont'd)
    – ETD
    Commented Aug 27, 2014 at 0:51
  • (cont'd) ... I don't seriously think we could draw historical conclusions, of course, but it would be somewhat interesting in and of itself if one player's engine version tended to outperform another's empirically.
    – ETD
    Commented Aug 27, 2014 at 0:52
  • -1 While it's not wrong, it makes no attempt to how the algorithm can be applied in chess. Stockfish has ALREADY APPLIED a SPSA algorithm. Read my answer.
    – SmallChess
    Commented Aug 27, 2014 at 4:00
  • 1
    what are you talking about? I explicitly laid out how to apply it to chess. I suspect you didn't read the steps. There are many papers in scholastic literature that follow a similar approach btw. Just because Stockfish has chosen a different approach to numerical optimization of heuristic coefficients doesn't mean this answer should be down voted.
    – tbischel
    Commented Aug 27, 2014 at 17:35
  • 1
    @StudentT, tbischel's entire answer is precisely a detailed recipe for applying the idea in question to chess. Given that fact, and that you say yourself this answer is in no way wrong, your downvote is rather puzzling.
    – ETD
    Commented Aug 27, 2014 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.