gamesmathematical programsotherabout author

Optimal algorithms for mastermind and bulls-cows games

ru

Bulls-cows and mastermind are popular paper and pencil games. The site concerns two optimization criteria of this games.

First optimization criterion

Bulls and cows. It's known that there is no algorithm which could solve all secret numbers using up to six turns, and there are algorithms which could solve any secret number using up to seven turns. The goal is to find algorithm which minimizes amount of secret numbers which algorithm can guess using exactly seven turns (all others should be guessed for up to six turns). Optimal algorithm guesses fifty numbers using exactly seven turns. See crushBullsCows algorithm results.

Mastermind. It's known that there is no algorithm which could solve all secret numbers using up to four turns, and there are algorithms which could solve any secret number using up to five turns. The goal is to find algorithm which minimizes amount of secret numbers which algorithm can guess using exactly five turns (all others should be guessed for up to four turns). Optimal algorithm guesses 539 numbers using exactly five turns. See crushMastermind algorithm results.

Second optimization criterion

Bulls and cows. The second criterion is minimize average amount of turns for guess arbitrary secret number - minimal average game length. The best average game length is 26274/5040=5.21 turns. See avgBullsCows algorithm results.

Mastermind. The second criterion is minimize average amount of turns for guess arbitrary secret number - minimal average game length. The best average game length is 5626/1296=4.34 turns if it's possible to do maximum five turns. See avgMastermind5 algorithm results. Minimal average game length is 5625/1296=4.34 turns if it's possible to do any number of turns (six turns are sufficient). See avgMastermind algorithm results.

For all of the algorithms trees are builded on javascript language and count statistics of them. Also it's possible play online using one of the algorithms. As well it was created article which includes mathematical part, programming part and part with the results.