blog/2018/06/04/bulls-and-cows

[giscus[bot]]

blog/2018/06/04/bulls-and-cows

NP-Incompleteness:

https://www.kuniga.me/blog/2018/06/04/bulls-and-cows.html

[Innoble]

Nice job, but I believe you made 1 mistake, which explains the 2 minutes run-time and left out 1 possible early optimization:

The mistake:

You assume only possible secrets are valid guesses. In bulls and cows, all guesses are valid, even the ones that can no longer be the possible secret. This means that on every turn, you have 5040 possible guesses. A guess that can no longer be a possible secret can be used to reduce the number of possible secrets and reduce the expected game length. That's why you need to include them. You can imagine what this does to the runtime.

The optimization:

You correctly explain the renaming of symbols on the second guess. Assuming the first guess is 1234, the following two second guesses are equivalent: 1235 and 1236. However, there is another kind of equivalency. 1235 is also equivalent to 1254. In both cases you are replacing a number with a new number, except you are doing it in a different position. It's a position equivalency. Also equivalent are 1324 and 1243. In both cases you are swapping two symbols. Yet another is 1342 and 2314. In both those cases you are cycling 3 symbols.

If you implement these two things you will (probably) notice you are still not able to solve bulls and cows due to the extreme branching. The paper you cited also explains some estimates for minimum game length that can be used to prune bad guesses. You will get many bad guesses if you include all of them.

If you compare the expected game length your program found to the one cited in the paper, you will probably notice yours is longer.

[kunigami]

Thanks for the detailed explanation. I ran into a similar issue while trying to create a solver for Wordle (sometimes it pays off utilizing letters known to not be present).

The author of the paper also commented on my old platform about this solving a different problem and hence the 2min was incorrect.

I'll update the post with these points.

[Innoble]

Thanks for the quick response! It is also worth it to look at this: http://slovesnov.users.sourceforge.net/bullscows/bullscows2.1.pdf

The English language is not perfect, but it's easy enough to understand. The mathematical notation is heavy, but what I understood from it, is that you can bruteforce a list of unique 1st, 2nd and 3rd sets of moves to massively reduce the search space. Also some optimizations for turn 4 and up. Combined with the information from the other paper I hope it will be enough for me to solve N = 4.

I got to this by doing https://www.codingame.com/multiplayer/optimization/bulls-and-cows-2
It's almost exactly bulls and cows except a 0 is not allowed in the first position (and it has codes of sizes between 2 and 10). I am trying to adapt the techniques to deal with that issue. It makes things more complicated.