MasterMind
Alessandro Bellucci
I'm new to operational research, I just attended a course this semester.
I have to write a model to solve the MasterMind game.
If you don't know the game:
The player has to guess an ordered sequence of 5 colors.
In each move he propose a sequence and the only things he can know are:
- the number of right color in right positions
- n. of right color in wrong positions
I thought the following was a good model :
# MasterMind model
# positions and colors.
set POSITIONS ;
set COLORS ;
# constraints due to previous moves .
set CONSTRAINTS ;
# the following matrixx has this meaning:
# m[i, j, k] = 1 if the color k is in position j in constraint k.
param m {CONSTRAINTS, POSITIONS, COLORS} ;
param N_COL_IN_RIGHT_POS {CONSTRAINTS} ;
param N_RIGHT_COL {CONSTRAINTS} ;
var x {POSITIONS, COLORS} binary ;
# just one color per position
subject to ONE_COLOR_PER_POSITION {i in POSITIONS}: sum {j in COLORS} x[i,
j] = 1 ;
subject to RIGHT_COLOR_AND_POS {i in CONSTRAINTS}:
sum {j in POSIZIONI, k in COLORI} (m[i, j, k] * x[j, k]) =
N_COL_IN_RIGHT_POS[i] ;
subject to RIGHT_COLOR {i in CONSTRAINTS}:
sum {j in POSITIONS, k in COLORS} ((1 - m[i, j, k]) * x[j, k]) =
N_RIGHT_COL[i] ;
but I get the following error with consistent data with AMPL student
edition:
presolve, constraint RIGHT_COLOR[0]:
all variables eliminated, but lower bound = 1 > 0
presolve, constraint ONE_COLOR_PER_POSITION[4]:
all variables eliminated, but lower bound = 1 > 0
presolve, constraint ONE_COLOR_PER_POSITION[3]:
all variables eliminated, but lower bound = 1 > 0
presolve, constraint ONE_COLOR_PER_POSITION[2]:
all variables eliminated, but lower bound = 1 > 0
presolve, constraint ONE_COLOR_PER_POSITION[1]:
all variables eliminated, but lower bound = 1 > 0
Infeasible constraints determined by presolve.
Could anyone please explain what those errors mean ?
I don't think the problem is infeasible, these are the constraints I passed
to the solver ( coded in the matrix m ) :
1) sequence of colors : 2 4 2 2 6 ( which correspond to the colors : GREEN
YELLOW GREEN GREEN ORANGE)
right position and color : 1 right color in wong position : 1
2) sequence of colors : 2 0 0 0 0 ( which correspond to the colors : GREEN
WHITE WHITE WHITE WHITE )
right position and color : 1 right color in wrong position : 0
You can try the game at this address:
http://billibellu.homeip.net/MasterMind/
Unfortunatly nothing seems to work fine :(
Thanks in advance,
Alessandro Bellucci .
Lutz Tautenhahn
> Infeasible constraints determined by presolve.
>
> Could anyone please explain what those errors mean ?
> I don't think the problem is infeasible, these are the constraints I
passed
> to the solver ( coded in the matrix m ) :
>
> 1) sequence of colors : 2 4 2 2 6 ( which correspond to the colors : GREEN
> YELLOW GREEN GREEN ORANGE)
> right position and color : 1 right color in wong position : 1
>
> 2) sequence of colors : 2 0 0 0 0 ( which correspond to the colors : GREEN
> WHITE WHITE WHITE WHITE )
> right position and color : 1 right color in wrong position : 0
>
> You can try the game at this address:
> http://billibellu.homeip.net/MasterMind/
> Unfortunatly nothing seems to work fine :(
>
> Thanks in advance,
> Alessandro Bellucci .
>
from 1) follows: number 2 is not in the solution, either number 4 or number
6
is in the right position (but not both), there is exactly one number 4 and
one
number 6 in the solution
from 2) follows: number 2 is in right position, there is only one number 2
in the
solution, number 0 is not in the solution
The contradiction is:
(number 2 is not in the solution)<>(number 2 is in right position)
Good luck with your further mastermind investigations!
Lutz Tautenhahn
www.tu-chemnitz.de/~luta/stroke/online.html
Paul A. Rubin
Your RIGHT_COLOR constraint is posed incorrectly. To see this, consider
your second guess in your example, in which you get one right
color/right position and zero right color/wrong position. Your
RIGHT_COLOR[2] constraint is:
sum {k<>2} x[1,k] + sum {j=2..5} sum {k<>0} x[j,k] == 0.
The first term evaluates to zero, since x[1,k]=0 for k<>2, so that's
fine. Unfortunately, the second (nested) sum must also equal 0
according to constraint, forcing x[j,k] = 0 for j=2..5 and k<>0. So in
other words, the only color this constraint allows in the last four
slots is WHITE, which the RIGHT_COLOR_AND_POS[2] constraint will rule
out. Hence your constraints are guaranteed to be inconsistent.
A logically correct (but unusable) version of RIGHT_COLOR would be:
RIGHT_COLOR {i in CONSTRAINTS}:
sum {k in COLORS} (min( sum {j in POSITIONS} x[j, k], sum {j in
POSITIONS} m[i, j, k]) - sum {j in POSITIONS} m[i, j, k]*x[j, k]) ==
N_RIGHT_COL[i];
For each color, you count up the number that actually are used and the
number you claimed in your guess, then take the smaller of those two
figures to get the number of repetitions of that color you correctly
guessed. From that you subtract the number you correctly placed. Then
total across colors.
The problem is that the min operator makes this nonlinear. A possible
workaround is to replace RIGHT_COLOR with the following:
var y {CONSTRAINTS, COLORS} integer >= 0; # number of instances of color
correctly guessed in constraint, regardless of position
subject to RIGHT_COLOR_1 {i in CONSTRAINTS, k in COLORS}:
y[i, k] <= sum {j in POSITIONS} x[j, k]; # can't guess more right than
exist
subject to RIGHT_COLOR_2 {i in CONSTRAINTS, k in COLORS}:
y[i, k] <= sum {j in POSITIONS} m[i, j, k]; # can't guess more right
than you guessed total
subject to RIGHT_COLOR_3 {i in CONSTRAINTS}:
sum {k in COLORS} (y[i, k] - sum {j in POSITIONS} m[i, j, k]*x[j, k])
== N_RIGHT_COL[i];
I think that should do it. You might be able to get by just
constraining y[i, j] >= 0, without requiring it to be integer. I think,
as long as x is binary, y will automatically turn out integer-valued.
-- Paul
--
***************************************************************************
Paul A. Rubin Phone: (517)
432-3509
Department of Management Fax: (517)
432-1111
The Eli Broad Graduate School of Management E-mail: ru...@msu.edu
Michigan State University
http://www.msu.edu/~rubin/
East Lansing, MI 48824-1122 (USA)
***************************************************************************
Mathematicians are like Frenchmen: whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different. J. W. v. GOETHE