Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: SMcNeill on September 15, 2021, 03:37:47 pm

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

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