JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Marathon Matches Marathon Match 2 Re: Post your approach Revision History (1 edit)
Re: Post your approach (response to post by MightyByte)
My approach was very similar to what has been already posted:

* Phase 1
Calculate frequency of each color (K-1 guesses at most)

* Phase 2
Generate random permutation (1 guess)

* Phase 3
Search for a code that minimizes:
cost = sum over all guesses{ abs(expected hits - code hits) }

(in other words, search for the code "more consistent" with all the previous guesses)

The search was performed in the following way:

a) start with the best guess so far (the one with the most hits)
b) randomly mutate the guess by swapping two pegs (of different color)
c) calculate the delta of the cost; improvements (ie. negative deltas) are always kept while degradations are randomly kept (I used a simulated annealing probability schedule)
d) repeat from step b until the temperature reaches zero

BTW, I also thought about adding the brute-force algorithm for the smaller cases since it scored way higher (more than 3 on average on my tests) but I didn't wanted to take (again) the risk of submitting in the final hours (my entries have already "suffered" enough because of that). Anyway, I keep wondering how big an improvement I did despise... lyc1977: do you have an estimate on your improvement for brute-forcing the smaller cases?
Re: Post your approach (response to post by MightyByte)
My approach was very similar to what has been already posted:

* Phase 1
Calculate frequency of each color (K-1 guesses at most)

* Phase 2
Generate random permutation (1 guess)

* Phase 3
Search for a code that minimizes:
cost = sum over all guesses{ abs(expected hits - code hits) }

(in other words, search for the code "more consistent" with all the previous guesses)

The search was performed in the following way:

a) start with the best guess so far (the one with the most hits)
b) randomly mutate the guess by swapping two pegs (of different color)
c) calculating the delta of the cost; improvements (ie. negative deltas) are always kept while degradations are randomly kept (I used a simulated annealing probability schedule)
d) repeat from step b until the temperature reaches zero

BTW, I also thought about adding the brute-force algorithm for the smaller cases since it scored way higher (more than 3 on average on my tests) but I didn't wanted to take (again) the risk of submitting in the final hours (my entries have already "suffered" enough because of that). Anyway, I keep wondering how big an improvement I did despise... lyc1977: do you have an estimate on your improvement for brute-forcing the smaller cases?