Simulated Annealing and Yahtzee!
- by Jasie
I've picked up Programming Challenges and found a Yahtzee! problem which I will simplify:
There are 13 scoring categories
There are 13 rolls by a player (comprising a play)
Each roll must fit in a distinct category
The goal is to find the maximum score for a play (the optimal placement of rolls in categories); score(play) returns the score for a play
Brute-forcing to find the maximum play score requires 13! (= 6,227,020,800) score() calls.
I choose simulated annealing to find something close to the highest score, faster. Though not deterministic, it's good enough. I have a list of 13 rolls of 5 die, like:
((1,2,3,4,5) #1
(1,2,6,3,4),#2
...
(1,4,3,2,2) #13
)
And a play (1,5,6,7,2,3,4,8,9,10,13,12,11) passed into score() returns a score for that play's permutation.
How do I choose a good "neighboring state"? For random-restart, I can simply choose a random permutation of nos. 1-13, put them in a vector, and score them. In the traveling salesman problem, here's an example of a good neighboring state:
"The neighbours of some particular
permutation are the permutations that
are produced for example by
interchanging a pair of adjacent
cities."
I have a bad feeling about simply swapping two random vector positions, like so:
(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one
But I have no evidence and don't know how to select a good neighboring state. Anyone have any ideas on how to pick good neighboring states?
