Problem 44248. Mastermind V: Optimal Solver - average number of guesses

Created by LY Cao
Appears in Board Games II

Difficulty:Rate

Solve Later
Add To GroupÃ‚

The following description contains a copy of Richard Zapor's Mastermind IV: Optimal Solver - max of 5 guesses

Mastermind is a code breaking logic puzzle. A pattern of 6 colors(values 1:6) of four positions (1111;1112;....6666) for a possible 6^4(1296) cases is generated. The solver plays a length 4 vector with values 1:6. Accuracy of the play is returned by a count of values in the right position and a count of values(excluding those in the right positions) common to the solution.

Answer:1233  Guess:3231 Response: 2,2  as x23x are right value/position, 3xx1 are right values.

[guess]=solve_mastermind(mguess,mpegs,m,mpc,mc,mpc5c,v)

where guess is a 1x4 vector, mguess is the kx4 matrix of prior guesses and is empty on first try, mpegs is kx2 giving right [value/position, values] for mguess, m is a 1296x4 array [1 1 1 1;...6 6 6 6] of all solutions, mpc is a 1296x1296 array of 0:4 for value/position solutions, mc is a 1296x1296 array of 0:4 for value solutions, mpc5c is state array of a combined mpc and pc of values 0:20, 5*mpc+mc, and v is integer value of solutions 1111 thru 6666. will be provided.

Scoring: the average number of guesses of all 1296 cases.

See Also:

Mastermind I: Solve all 1296 cases

Mastermind II: Solve in 8 or less

Mastermind III: Solve in 1

Mastermind IV: Optimal Solver - max of 5 guesses

Solve

Solution Stats

66 Solutions
12 Solvers

Last Solution submitted on Feb 23, 2025

Last 200 Solutions

Problem Comments

14 Comments

14 Comments

Show 11 older comments

yurenchu on 3 Jul 2017

In the test script, what does "randperm(end)" do? Is that even proper MATLAB code?

LY Cao on 4 Jul 2017

@yurenchu.
Yes. The END here serves as the last index of P.

yurenchu on 4 Jul 2017

Either 7296 iterations is too much, or the test script causes an infinite loop somehow. I've tried several approaches, ones that worked smoothly in Richard Zapor's Problems, but I always get "the server encountered an error caused by long running MATLAB code". Are you sure "P(randperm(end))" does what it's supposed to do? Why not use the less ambiguous "P(randperm(numel(P)))" instead?

LY Cao on 4 Jul 2017

@yurenchu.
Cody has an approx 50 seconds time limit.
You could verify the following code:
>> a = 4:6; a(randperm(end))

yurenchu on 4 Jul 2017

I don't have MATLAB installed on a computer, so I verified your example using one of the beginner problems ("Solution 1225050"); and I'm surprised but you're right, this peculiar piece of code indeed works. So it seems the trick is in writing a function that can play the game 7300 times (= approx. 33,000 guesses) in less than 50 seconds.

LY Cao on 5 Jul 2017

@yurenchu.The challenge of the problem is to optimize average number of guesses.
For speed challenge, 7300 is not enough. I've test some solutions without speed optimization passed these tests in 10 secs.

yurenchu on 5 Jul 2017

@LY_CAO: Thanks, but I still don't understand. Your own Solution 1215381 from Zapor's "Mastermind II: Solve in 8 or less" managed to solve 1296 games with a total of 6508 guesses in only 3.02 seconds. Yet when I copy and submit the very same solution here (where I expect at most six times as many needed guesses, so a total of <20 seconds), I receive the "error due to long running MATLAB code" abort alert (see Solution 1225064). How is that possible? The only possible factor (as far as I can see) is the difference in test script.

LY Cao on 5 Jul 2017

@yurenchu.
It seems that the typo "ismemb2" error was suspressed by TRY, so the output was always [1 1 2 2].

yurenchu on 5 Jul 2017

@LY_CAO: Thanks for notifying me of my typo, which I hadn't noticed! I've finally managed to submit a working solution; but it still seems to be a challenge to keep the solution under the time limit without using ismembc2 or while applying a "minimal guess"-algorithm.

LY Cao on 5 Jul 2017

@yurenchu.
ISMEMBC2 generates the second output of ISMEMBER, so I guess it should work flawless even if 'q = ismembc2(...)' is replaced by '[~,q] = ismember(...)'.

yurenchu on 5 Jul 2017

Thanks, LY_CAO. What I meant was that before considering "ismembc2()"/"ismember()" with matrix indexing, I instead used relational operation combined with matrix multiplication, which calculates the same thing but which is apparently too time-consuming.

LY Cao on 6 Jul 2017

@yurenchu, ismember/ismembc2 perform a binary search in runtime complexity O(logn), faster than a linear search with runtime complexity O(n).
https://www.mathworks.com/matlabcentral/answers/92533-how-do-i-perform-a-binary-search-of-a-presorted-array

yurenchu on 7 Jul 2017

I wasn't aware of stuff like that. Thanks for the interesting information and weblink, it's indeed helpful. However, it seems that 7300 game iterations doesn't offer much space to implement experimentative/lengthier/more extensive algorithms (such as ones considering ps(k,:) instead of ps(k,k) as the search space for the next best guess), without hitting Cody's time limit. (At least not to a person like me who doesn't know which built-in MATLAB functions work fast and which work "slowly".) But anyway, still very interesting problem/challenge.

LY Cao on 8 Jul 2017

@yurenchu. Let's take this as an additional challenge :-)

Solution Comments

Show comments

Group

Board Games II

14 Problems
10 Finishers

Problem Recent Solvers12

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44248. Mastermind V: Optimal Solver - average number of guesses

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Board Games II

Problem Recent Solvers12

Problem Tags

Community Treasure Hunt

Players