0
$\begingroup$

I'm looking to implement a AI for the turn-based game Mastermind in Node.JS, using Google's Tensorflow library. Basically the AI needs to predict the 4D input for the optimal 2D output [0,4] with a given list of 4D inputs and 2D outputs from previous turns in the form of [input][output].

The optimal output would be [0,4], which would be the winning output. The training data looks like this:

[1,2,3,4][0,1] [0,5,2,6][3,1] [0,2,5,6][2,2] [6,5,2,0][4,0] [5,2,0,6][0,4]

So given these previous turns

[1,2,3,4][0,1] [0,5,2,6][3,1] [0,2,5,6][2,2] [6,5,2,0][4,0]

the AI would predict an input of [5,2,0,6] for the output [0,4]. I've looked at this post but it talks about only inferring input for a output without any context. In Mastermind, the context of previous guesses and results from them are critical

My algorithm would need to use the information from previous turns to determine the best input for the winning output ([0,4]).

So my question is: How can I implement AI for Mastermind?

$\endgroup$
  • $\begingroup$ I think what you're looking for is Reinforcement Learning. $\endgroup$ – SpiderRico May 8 at 7:56
  • $\begingroup$ Mastermind is something of a special case, since although there is some randomness and strategy picking a pattern to guess and opening moves to narrow down the guess, once some data has been collected it rapidly narrows down to a logic problem. Is your question specifically about Mastermind? If so the "turn-based game with context" part may not be that important $\endgroup$ – Neil Slater May 8 at 11:39
  • $\begingroup$ @NeilSlater Yes, mainly just Mastermind $\endgroup$ – sportzpikachu May 9 at 6:51
  • $\begingroup$ I have edited to make that clearer, because you have something of an "X/Y" problem if you ask for "turn-based game with context" when you actually want to solve Mastermind. Further to that, I doubt you need tensorflow or deeplearning here to write a good automated Mastermind player - so could you clarify whether your goal is specifically to apply some kind of neural network model (which is interesting but a lot of effort and may perform poorly) or want to understand and solve Mastermind? $\endgroup$ – Neil Slater May 9 at 11:51
1
$\begingroup$

You could possibly apply neural networks, reinforcement learning to summarise results of previous choices (what you are calling context) and use score predictions to suggest the next turn's guess. However, the game of Mastermind has a small search space and it is possible to process this "context" more directly by refining a set of guesses. This will be much more efficient and simpler to understand than a neural network approach. It would be very hard to make a neural network variant which was as efficient - either in terms of CPU time, or in terms of number of turns it takes to find a solution.

In practice, a Mastermind solver is much like a Hangman solver, or a Guess Who? solver. You have an initial large set of all possible answers, and need to narrow it down to a single correct answer. You do this by processing after each guess to reduce the set of answers that meet all the constraints that the game has given you so far.

The agent needs to know the score function that compares a target value with the guess and returns the score. Let's call that score(guess, target)

The algorithm looks like this:

(Opponent sets unknown_target)
Initialise possible_answers as list of all valid targets

For each turn:
  Select one of possible_answers as this turn's guess
  Ask opponent for gscore = score(guess, unknown_target)
  If gscore is [0,4] then exit(win)
  If it was last guess then exit(lose)
  For each possible_answer in possible_answers:
    pscore = score(guess, possible_answer)
    If pscore != gscore, then remove possible_answer from possible_answers

You can finesse this for the stage Select one of possible_answers as this turns guess by trying to optimise either by psychological model of opponent or trying to find choices that are likely to cause the best reduction in size of possible_answers. However, a simple random choice should do quite well.

Also worth noting is that the algorithm does not depend on the exact nature of the scoring function, so it is applicable for many variations of guessing games. It does rely on the score providing information that will reduce the remaining set of guesses. In some games that may mean taking more care about the precise nature of a guess, in order to maximise this effect.

Out of interest, I implemented this algorithm and tested it when there were 10 choices at each position (i.e. digits 0 to 9), maximum of 10 guesses allowed, and the target to guess was set randomly. Using random guesses and the algorithm exactly as written, the above approach guessed correctly 9,996 times out of 10,000, and on average the guesser won the game in 6.2 turns.

| improve this answer | |
$\endgroup$
0
$\begingroup$

although I have seen RL solutions to this problem, (those I saw) fail to realize that the state of mastermind is not observable, as there is the "secret" we're trying to guess.

mastermind is best approached as a constraint satisfaction problem, along the lines described by Neil Slater. The whole trick is to realize that you can eliminate options from the "current possible alternatives" set by treating the latest guess as the target and eliminate any combinations that don't agree with it e.g. (using 3 digits for clarity)

last guess=123, scores [2,0] i.e. 2 white, 0 black

then the current alternatives are eliminated if they don't score [2,0] against the last guess 123:

124 [0,2] 214 [2,0] 215 [2,0] 321 [2,1]

let's say the secret is 215, you see that our method of elimination is correct, albeit we don't know the secret!

I have seen lots of different approaches (genetic engineering, information theory etc), but the plain truth is that a 50-line matlab piece of code with random guessing will give a winning stragegy that averages 4.3 guesses for the standard mastermind game (1296 alternatives)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.