Author Topic: Code Breaker  (Read 4946 times)

0 Members and 1 Guest are viewing this topic.

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Code Breaker
« on: September 15, 2021, 03:37:47 pm »
A little game I was playing around with making to just give my little grand-niece something to waste time on when she comes to visit.

Code: QB64: [Select]
  1. Dim Shared f, f1, lastsolved, guess(10), guesses
  2. Screen _NewImage(640, 480, 32)
  3. f = _LoadFont("courbd.ttf", 64, "monospace")
  4. f1 = _LoadFont("courbd.ttf", 32, "monospace")
  5. Color Black, none
  6.  
  7. n$ = GetNum(5)
  8.  
  9.     Cls
  10.     guess$ = "": wheel = 0: Xon = 0
  11.     For i = 1 To Len(n$)
  12.         guess$ = guess$ + _Trim$(Str$(guess(i)))
  13.     Next
  14.     DrawLock guess$, n$
  15.  
  16.     While _MouseInput: wheel = wheel + _MouseWheel: Wend
  17.     X = _MouseX: y = _MouseY: mb = _MouseButton(1): mb2 = _MouseButton(2)
  18.  
  19.     If y > 105 And y < 195 Then 'we're on the proper spot to be in the combination area
  20.         Xon = Int((X - 105) / (300 / Len(n$)) + 1) 'this is the tumbler we're on
  21.         If Xon > 0 And Xon <= Len(n$) Then
  22.             If wheel Then
  23.                 guess(Xon) = guess(Xon) + wheel
  24.             End If
  25.             If mb And Not oldmouse Then guess(Xon) = guess(Xon) + 1
  26.             If mb2 And Not oldmouse2 Then guess(Xon) = guess(Xon) - 1
  27.             If guess(Xon) > 9 Then guess(Xon) = 0
  28.             If guess(Xon) < 0 Then guess(Xon) = 9
  29.         End If
  30.     End If
  31.     If mb And Not oldmouse Then
  32.         If y > 205 And y < 295 Then 'in the solved row
  33.             If X > 105 And X < 395 Then 'in the Last row
  34.                 lastsolved = 0: guesses = guesses + 1
  35.                 For i = 1 To Len(n$)
  36.                     If Asc(guess$, i) = Asc(n$, i) Then lastsolved = lastsolved + 1
  37.                 Next
  38.             End If
  39.         End If
  40.     End If
  41.     oldmouse = mb: oldmouse2 = mb2
  42.     _Display
  43.     _Limit 15
  44. Loop Until lastsolved = Len(n$)
  45. Color White
  46. Print "YAY!  You got it in"; lastsolved; "tries!"
  47.  
  48. Function GetNum$ (size)
  49.     For i = 1 To size
  50.         n = Int(Rnd * 11)
  51.         GetNum$ = GetNum$ + _Trim$(Str$(n))
  52.     Next
  53.  
  54. Sub DrawLock (guess$, num$)
  55.     _Font f
  56.     Color Black, none
  57.     size = Len(num$)
  58.     s = 300 / size
  59.     Line (100, 100)-(400, 200), SlateGray, BF
  60.     Line (100, 100)-(400, 300), SlateGray, BF
  61.     Line (105, 105)-(395, 195), LightGray, BF
  62.     Line (105, 205)-(395, 295), Green, BF
  63.     For i = i To (size - 1)
  64.         Line (100 + i * s, 100)-Step(5, 100), SlateGray, BF
  65.         t$ = Mid$(guess$, i, 1)
  66.         left = 105 + (s - _FontWidth) / 2
  67.         _PrintString (left + (i - 1) * s, 150 - _FontHeight / 2), t$
  68.     Next
  69.     t$ = Mid$(guess$, i, 1)
  70.     _PrintString (left + (i - 1) * s, 150 - _FontHeight / 2), t$
  71.     _Font f1
  72.     _PrintString (110, 210), "Last:" + _Trim$(Str$(lastsolved))
  73.     _PrintString (110, 250), "Guesses:" + _Trim$(Str$(guesses))

This should be easy enough to figure out: 
Use the mouse wheel or the buttons to increase or decrease the values of a tumbler. 
Click in the green area to make a guess and see how many numbers you got correct out of your attempt.

Match the actual combination and win!



At this point, this only runs through the creation and puzzle process a single time, for a single 5-digit combination lock.  I suppose all it really needs at this point to become a "replayable game" is to offer an option to select difficulty (it can generate anywhere up to 9-digit locks for increased difficulty), and then an option to replay/quit again afterwards -- but that's a simple enough mod for another day, when I have a little more free time again.

Now the question is:  How fast can someone solve these type of puzzles?  What's the best strategy to get to the win in the least possible number of moves normally? 

Randomly type in a number and you *could* get it in one guess, but where's the logic in that? 

Type in each number one at a time, click to check, and you're guaranteed to get the solution in 10 * wordlength guesses.

Type in all 5 digits the same, and you can eliminate a whole number from your guess each time.  (For example guess five zeros 00000, find out that there's no matches, you've now dropped the possible data pool down to only using numbers 1 to 9.  Do it for each of the numbers from 0 to 10, and you've eliminated half the puzzle in 10 guesses, as your 5 digit number can't hold 10 different values!)

Now that I've came up with the little problem to create the puzzles, I'm now left pondering on what might be the best solution for an AI to use to guess the puzzle in the fewest amount of tries possible.  Anyone have any thoughts on a surefire Code Breaker solution routine with the fewest possible attempts usually? 

I may end up trying to incorporate some sort of competition where a player tries to compete against the computer to shoot for the answer first, so various ideas for AI attempts could be written into the game as different opponents to try your luck against.  Suzy might just try random numbers.  Jane might do the meticulous one by one approach.  Fred might do an elimination approach to solving.  Anybody have any other methods to attempt for an AI?
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Code Breaker
« Reply #1 on: September 15, 2021, 04:32:52 pm »
Hi Steve,

Something is off with the guess counter. I set the number of numbers to 3, because you haven't Randomized Timer the answer is always 756. I get it in one guess yet it says, "Yeah I got it in 3.", all the time.

This reminds of Bulls and Cows there is an AI strategy for that I remember working out long ago possibly with you?

Marked as best answer by SMcNeill on September 15, 2021, 12:49:09 pm

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Code Breaker
« Reply #2 on: September 15, 2021, 04:46:54 pm »
Hi Steve,

Something is off with the guess counter. I set the number of numbers to 3, because you haven't Randomized Timer the answer is always 756. I get it in one guess yet it says, "Yeah I got it in 3.", all the time.

This reminds of Bulls and Cows there is an AI strategy for that I remember working out long ago possibly with you?

The print statement at the win is printing the wrong variable...

Change:

Print "YAY!  You got it in"; lastsolved; "tries!"   

To:

Print "YAY!  You got it in"; guesses; "tries!"

Somehow, that makes a difference.  LOL!



I don't remember Bulls and Cows off the top of my head.  I'll have to do a forum search for it and see how it compares and what we came up with for it before, then.  :)
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Code Breaker
« Reply #3 on: September 15, 2021, 04:58:11 pm »
The date I worked on Bulls and Cows was 2019-01-31

It was a Rosetta Code problem for 4 non repeating digits. Bull is when you get a digit right in the right place, cow is correct digit wrong place. Takes about 5 guesses. By 6 for sure!
« Last Edit: September 15, 2021, 04:59:32 pm by bplus »

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Code Breaker
« Reply #4 on: September 15, 2021, 05:29:10 pm »
I've seen an easier version of this online somewhere before, where the difference was they highlight each number as you guess it correctly.  1234 might be your guess, you click the guess button, and then the 3 turns green and the others turn red...  Which really seems to take all the challenge and logic out of the puzzle to me.  Guess each number from 0 to 9, stop when one turns green -- guaranteed win in a max of 10 turns!

By only telling you the number correct, it adds a little more difficulty to the puzzle.  Guess 1234, get one right, but which one is it?

More options = more strategies to try and get to the correct answer the fastest! 

The way it exists now, I think it'd take an average of 5 * length to guess a code if you do one digit at a time sequentially.  A 3 number game would take about 15 moves, a 5 number game about 25...

I'm thinking the same games, if you eliminate the missing numbers first, might be faster on average to solve.  10 tries max to eliminate 5 numbers, changing the puzzle from 5 digits of 0 to 9 to a puzzle of 5 digits of 0 to 4.  It should take an average of 2.5 guesses per digit after that, if you go sequentially for the solution, turning your 25 turn average down to a 22.5 turn average to win...

Random attempts, I just don't see any luck in at all.  I guess eventually you'd get a win, but I'd hate to calculate how many tries it'd take for you to do it on average.  :P
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Code Breaker
« Reply #5 on: September 15, 2021, 05:36:51 pm »
Another AI method I've been thinking of would be to change 2 digits at once sequentially.  Instead of one digit at a time, until you get the right answer, do 2 digits at once.

00.. fail
11.. fail
22.. one number right!
23...   if zero numbers right, then the 2 to the right is correct.  If one number is right, then the 2 to the left is correct.  If two numbers are right, then they're both correct.  Either way, you've found your solution and reduced the number pool for the second number somewhat.  You don't have to go sequentially from 0 to 9 again; you just have to go from the last digit you checked to 9..

I very well may end up sitting down and working up half a dozen different ways to try to get a solution to this problem, and have fun just comparing which one would be the most efficient in the long run for me.  :)
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline rickclark58

  • Newbie
  • Posts: 18
    • View Profile
    • YouTube Channel
Re: Code Breaker
« Reply #6 on: September 21, 2021, 06:23:45 pm »
The Mastermind game has a number of algorithms associated with it that might be of use. https://en.wikipedia.org/wiki/Mastermind_(board_game)
Rick Clark

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Code Breaker
« Reply #7 on: September 22, 2021, 12:11:54 am »
Well here is the best AI so far, one that is actually coded and works ;-))

Only roughed out for 3 digit lock:
Code: QB64: [Select]
  1. _Title "Guess number - with less help than Hi, Lo Game" 'b+ 2021-09-21
  2.  
  3. Dim Shared guesses
  4.     ans$ = ""
  5.     For i = 1 To 3
  6.         ans$ = ans$ + Mid$("0123456789", Int(Rnd * 10) + 1, 1)
  7.     Next
  8.     guesses = 0
  9.     Print: Print "follow along: "; ans$ ' <<< debug
  10.  
  11.     While g$ <> ans$
  12.         Print "Guess my"; 3; "digit number "
  13.         'Input "enter guess > "; g$
  14.         g$ = AI3Guess$(-1) ' <<< signal for guess with -1
  15.         Print "B+ AI guesses "; g$
  16.         If g$ = "" Then System
  17.         guesses = guesses + 1
  18.         If g$ = ans$ Then
  19.             Print "You got it in"; guesses; "guesses!": Print
  20.         Else
  21.             right = 0
  22.             For i = 1 To Len(ans$)
  23.                 If Asc(ans$, i) = Asc(g$, i) Then right = right + 1
  24.             Next
  25.             Print "Your AI guess has"; right; "right."
  26.             dummy$ = AI3Guess$(right) ' >>> give the AI the feed back
  27.         End If
  28.         Print "press any to continue..."
  29.         Sleep
  30.         Print
  31.     Wend
  32.  
  33. Function AI3Guess$ (guessOrFeedback As Integer) ' no feedback means it guessed right and a new game started
  34.     Static lastGuess$, nRight, tI, a$, b$, c$
  35.  
  36.     g$ = "000111222333444555666777888999abccabbcabacacbcba" ' 10 digits 6 combo 16 tries
  37.     If guesses = 0 Then 'starting new game
  38.         lastGuess$ = "": nRight = 0: tI = 0
  39.     End If
  40.     If guessOrFeedback <> -1 Then 'feedback
  41.         If nRight < 3 Then
  42.             If guessOrFeedback = 1 Then
  43.                 If nRight = 0 Then
  44.                     a$ = Mid$(lastGuess$, 1, 1): nRight = 1
  45.                 ElseIf nRight = 1 Then
  46.                     b$ = Mid$(lastGuess$, 1, 1): nRight = 2
  47.                 ElseIf nRight = 2 Then
  48.                     c$ = Mid$(lastGuess$, 1, 1): nRight = 3: tI = 10
  49.                 End If
  50.             ElseIf guessOrFeedback = 2 Then
  51.                 If nRight = 0 Then
  52.                     a$ = Mid$(lastGuess$, 1, 1): b$ = Mid$(lastGuess$, 1, 1): nRight = 2
  53.                 ElseIf nRight = 1 Then
  54.                     b$ = Mid$(lastGuess$, 1, 1): c$ = Mid$(lastGuess$, 1, 1): nRight = 3: tI = 10
  55.                 End If
  56.             End If
  57.         Else
  58.             'we are going to be a little stupid  for now  just want to see if this works
  59.         End If
  60.  
  61.     Else 'guess time
  62.         tI = tI + 1
  63.         lastGuess$ = Mid$(g$, (tI - 1) * 3 + 1, 3)
  64.         If nRight < 3 Then
  65.             AI3Guess$ = lastGuess$
  66.         Else
  67.             For i = 1 To 3
  68.                 If Mid$(lastGuess$, i, 1) = "a" Then Mid$(lastGuess$, i, 1) = a$
  69.                 If Mid$(lastGuess$, i, 1) = "b" Then Mid$(lastGuess$, i, 1) = b$
  70.                 If Mid$(lastGuess$, i, 1) = "c" Then Mid$(lastGuess$, i, 1) = c$
  71.                 AI3Guess$ = lastGuess$
  72.             Next
  73.         End If
  74.     End If
  75.