----

Master Mind

----

Cette page est aussi disponible en franšais.

In may 2005, the Evolution Artificielle association organized a master mind contest whose goal was to solve the 10x10 problem (10 colors, 10 holes) with a time constraint, and with a minimal number of tries.

We had previously studied this problem for smaller sizes (up to 8x8) and knew that for these sizes "brute forcish" algorithms were extremely efficient, and that the best method was to choose at each step the move which minimized the number of remaining possibilities.

For the 10x10 problem, this solution was not applicable as such, but a "brute-forcish" algorithm could anyway be designed, which solved the 10x10 problem in 4/100s in C, and in 2/10s in OCAML. Thus, the rules of the contest were changed, and the problem became a 13x13 problem.

Here, the pure enumerative algorithm wasn't so easy to use, and we tried to tackle the problem with constraints programming methods. However, our "home made" constraint programming software (FACILE) seemed to be slightly too slow, so we decided to adapt the 10x10 program to the 13x13 problem, but we had to make some compromises between speed and efficiency.

We designed an adaptative program, with 2 distinct steps. First, the program finds the 13 colors of the code, without trying to find their positions, but trying to create the maximal number of constraints gathered from the answers to the codes submitted: we tried different techniques to achieve this goal, the one finally used is a combination of a shifting strategy and a "no-twice-the-same-place" strategy. In the second step, the algorithm tries to find a solution consistent with existing constraints by a brute-forcish "optimized" method, but with a time constraint. If the alloted time is over and the program hasn't been able to find a solution, it uses the "best" solution found so far.

The performance of the program depends on the available time. With an unlimited amount of time, it solves the 13x13 problem in less than 16 moves (on the average). For the contest, we were quite conservative (probably too much) and implemented a (too) strong time constraint; thus the algorithm solved the problem in about 17 moves.

After the contest, we realized that we should have rewritten and used the C program, which was faster than the OCAML one. But we had not the courage to do it: programming optimized C programs is quite a pain, while (re)writing OCAML programs is fast and easy. We will try to do better next time...

PS: the main author of the program is Nicolas Durand. You can get in touch with him for more information.


Page written by Jean-Marc Alliot, who also wrote the 10x10 C program, and was too lazy to rewrite it to accomodate the 13x13 problem...


Last Update: