F# – genetic algorithms to help you catch monsters

The mon­ster trap­ping mechan­ics in Here Be Mon­sters is fair­ly straight for­ward:

  • Mon­sters have a type and a set of stats – Strength, Speed and IQ
  • They have a rar­i­ty val­ue which deter­mines the like­li­hood of an encounter
  • They have a set of baits they like, which can increase the like­li­hood of an encounter
  • Traps can catch mon­sters of match­ing types
  • Traps also have a set of stats – Strength, Speed and Tech
  • Chance of catch­ing a mon­ster is deter­mined by the trap’s stats vs the monster’s stats

image image

It’s as sim­ple as it sounds. Unless, of course, you’re the game design­er respon­si­ble for set­ting the stats for the trap so that:

a. you achieve the intend­ed catch rate % against each of the mon­sters, and

b. the dis­tri­b­u­tion of the stats should ‘make sense’, i.e. a low-tech box trap should have high­er stats in strength than Tech


The naive approach would be to start with a guessti­mate and then use tri­al-and-error until you con­verge upon an answer or an approx­i­ma­tion to the answer that is con­sid­ered good enough. The naive approach would be labo­ri­ous and error prone, and unlike­ly to yield the opti­mal result (bar­ring the Her­culean effort of a per­sis­tent game design­er..).


To auto­mate this process and aid our game design­ers, we designed and imple­ment­ed a sim­ple genet­ic algo­rithm in F# that would search and find the opti­mal solu­tion based on:

  • intend­ed % catch rate for each mon­ster
  • an error mar­gin
  • an ini­tial set of stats that defines the ide­al dis­tri­b­u­tion of stats

The game design­ers can use our cus­tom web tool to run the algo­rithm, for exam­ple:



In sim­ple terms, a genet­ic algo­rithm starts with a set of poten­tial solu­tions and iter­a­tive­ly gen­er­ates new gen­er­a­tions of solu­tions using a selec­tion and a muta­tion process such that:

  • the selec­tion process choos­es which of the solu­tions sur­vive (sur­vival of the fittest and all) based on a fit­ness func­tion
  • the muta­tion process gen­er­ates a new solu­tions using the sur­viv­ing solu­tions

the iter­a­tion con­tin­ues until one of the ter­mi­na­tions con­di­tions have been met, for exam­ple, if a solu­tion is found or we’ve reached the max­i­mum num­ber of gen­er­a­tions allowed.



In our algo­rithm, each solu­tion is a set of stats for the trap, and the selec­tion process cal­cu­lates the catch rate for each of the mon­sters using the solu­tion, and keeps the solu­tion if it’s bet­ter than the solu­tion it’s mutat­ed from.

The muta­tion process then takes each of he sur­viv­ing solu­tions and gen­er­ates new solu­tions by tweak­ing the stats in a num­ber of ways:

  • +/- a small amount from each of Strength/Speed/Tech (gen­er­ates bet­ter solu­tions when we’re close to opti­mal solu­tions)
  • +/- a large amount from each of Strength/Speed/Tech (gen­er­ates notice­ably dif­fer­ent solu­tions we’re far from opti­mal solu­tions)

So from an ini­tial solu­tion of Strength:100, Speed:100 and Tech:200, you can end up with a num­ber of dif­fer­ent solu­tions for the next gen­er­a­tion:


This process con­tin­ues until either:

  • the max num­ber of gen­er­a­tions has been exhaust­ed, or
  • none of the new solu­tions sur­vive the selec­tion process

the final sur­vivors are then fil­tered using the error mar­gin spec­i­fied by the game design­er, and sort­ed by how close it’s to the spec­i­fied tar­get catch rates, e.g.



We have also applied the same tech­nique and imple­ment­ed genet­ic algo­rithms to:

    • find stats for a mon­ster that will give it the intend­ed catch rate for a num­ber of traps (the inverse of the above)
    • find con­fig­u­ra­tion for baits so that we can achieve the desired encounter rate with a mon­ster when using this bait (see below for an exam­ple)




So here you ago, I hope you enjoyed read­ing about anoth­er place where a bit of F# mag­ic has come in handy.

The code for the genet­ic algo­rithms is not very com­pli­cat­ed (or very long) but incred­i­bly spe­cif­ic to our spe­cif­ic domain, hence the lack of any code snip­pet in this post. But hope­ful­ly I’ve man­aged to give you at least a flavour of what genet­ic algo­rithms are and how you might be able to apply them (with F# if pos­si­ble!) in your own solu­tion.