Author Topic: Bulls and Cows AI  (Read 4991 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Bulls and Cows AI
« on: January 31, 2019, 10:09:23 pm »
Review the Bulls and Cows Game here: http://rosettacode.org/wiki/Bulls_and_cows

The code below has a Bulls and Cows Game commented out, if you want to try your hand at playing the game and to help appreciate the AI program.

Now for the AI player:
Code: QB64: [Select]
  1. _TITLE "Bulls and Cows AI" ' for QB64 B+ started 2019-01-31
  2. DEFINT A-Z
  3. DIM SHARED secret$
  4. DIM SHARED possibles(1 TO 9876) 'permutation T or F
  5.  
  6. 'As suggested by Rosetta,
  7. '  "One method is to generate a list of all possible numbers that could be the answer,"
  8. '  "then to prune the list by keeping only those numbers that would give an equivalent"
  9. '  "score to how your last guess was scored. Your next guess can be any number from the"
  10. '  "pruned list. Either you guess correctly or run out of numbers to guess, which"
  11. '  "indicates a problem with the scoring."
  12.  
  13.  
  14. 'Creating a list of all possible permutations of the 10 digits
  15. 'taken 4 at a time = 10*9*8*7 possibles = 5040.
  16. 'Loading such that if a nonrepeating 4 digit number then -1 else leave at 0
  17. FOR i = 123 TO 9876
  18.     IF noRepeat(RIGHT$("000" + LTRIM$(STR$(i)), 4)) THEN possibles(i) = -1: count = count + 1
  19.     'check noRepeat function
  20.     'PRINT i, possibles(i)
  21.     'INPUT "OK press enter "; wate$
  22. 'check possibles count
  23. PRINT "Possible permutations of 4 non repeating digits ="; count 'equals 5040?
  24.  
  25. createSecretNumber
  26.  
  27. 'test score$ with a regular game of Bulls and Cows
  28. 'PRINT secret$
  29. 'guesses = 0
  30. 'DO
  31. '    INPUT "Please enter your 4 digit guess "; guess$
  32. '    guesses = guesses + 1
  33. '    PRINT score$(secret$, guess$)
  34. '    PRINT
  35. 'LOOP WHILE secret$ <> guess$
  36. 'PRINT "You found the number in"; guesses; " guesses."
  37.  
  38.  
  39. 'OK now for the main event
  40. PRINT "Here is the secret number so you can follow along: "; secret$
  41.     'INPUT "Please enter your 4 digit guess "; guess$
  42.  
  43.     'insert AI player here
  44.     r = INT(RND * 9876) + 1
  45.     WHILE possibles(r) = 0
  46.         r = r + 1
  47.         IF r > 9876 THEN r = 123
  48.     WEND
  49.     guess$ = RIGHT$("000" + LTRIM$(STR$(r)), 4)
  50.  
  51.     'display the guess and it's score
  52.     PRINT "AI guesses "; guess$
  53.     guesses = guesses + 1
  54.     sc$ = score$(secret$, guess$)
  55.     PRINT "Scores: "; LEFT$(sc$, 1); " bull(s), "; RIGHT$(sc$, 1); " cow(s)"
  56.     IF sc$ <> "40" THEN
  57.         'now AI will use that score to eliminate all possibles that would not yeild the cattle count
  58.         changes = 0: remainder = 0
  59.         FOR i = 123 TO 9876
  60.             IF possibles(i) <> 0 THEN
  61.                 is$ = RIGHT$("000" + LTRIM$(STR$(i)), 4)
  62.                 tsc$ = score$(guess$, is$)
  63.                 'PRINT "i string$ "; is$; "  score is "; tsc$
  64.  
  65.                 IF score$(guess$, is$) <> sc$ THEN possibles(i) = 0: changes = changes + 1 ELSE remainder = remainder + 1
  66.                 'INPUT "OK press enter "; wate$
  67.             END IF
  68.         NEXT
  69.         PRINT "AI reduced number of possible permutations by"; RTRIM$(STR$(changes)); ", so"; remainder; "possible(s) remain."
  70.         INPUT "OK press enter "; wate$
  71.     END IF
  72.     PRINT
  73. LOOP WHILE secret$ <> guess$
  74. PRINT "AI found the number in"; guesses; "guesses."
  75.  
  76.  
  77. SUB createSecretNumber
  78.     digits$ = "0123456789": secret$ = ""
  79.     FOR i = 1 TO 4
  80.         p = INT(RND * LEN(digits$)) + 1
  81.         secret$ = secret$ + MID$(digits$, p, 1)
  82.         digits$ = MID$(digits$, 1, p - 1) + MID$(digits$, p + 1)
  83.     NEXT
  84.  
  85. FUNCTION noRepeat (d$)
  86.     IF LEN(d$) <> 4 THEN EXIT FUNCTION
  87.     FOR i = 1 TO 3
  88.         c$ = MID$(d$, i, 1)
  89.         FOR j = i + 1 TO 4
  90.             IF c$ = MID$(d$, j, 1) THEN EXIT FUNCTION
  91.         NEXT
  92.     NEXT
  93.     noRepeat = -1
  94.  
  95. FUNCTION score$ (secret$, test$)
  96.     FOR i = 1 TO 4
  97.         c$ = MID$(test$, i, 1)
  98.         IF MID$(secret$, i, 1) = c$ THEN
  99.             bulls = bulls + 1
  100.         ELSEIF INSTR(secret$, c$) THEN
  101.             cows = cows + 1
  102.         END IF
  103.     NEXT i
  104.     score$ = LTRIM$(STR$(bulls)) + LTRIM$(STR$(cows))
  105.  

What does it mean when you create something that "thinks" better than you?
 
Bulls and Cows AI in 3 guesses.PNG

Sure the AI was lucky here in guessing, but even when not lucky it does better than I.

Offline _vince

  • Seasoned Forum Regular
  • Posts: 422
    • View Profile
Re: Bulls and Cows AI
« Reply #1 on: January 31, 2019, 11:11:26 pm »
Pretty cool

Offline Dimster

  • Forum Resident
  • Posts: 500
    • View Profile
Re: Bulls and Cows AI
« Reply #2 on: February 01, 2019, 12:35:24 pm »
A couple of questions bplus - 1st, QB64 does not have a way to search a variable of numbers without the conversion to a string? for example Today = 20190201 so Day = Left(Today,2). Is that correct?
 2nd, in The Bulls and Cows AI search you have a line "FOR i = 123 TO 9876", where does the 123 come from? Is that ceding the order of a correct answer or just simply reducing the number of iterations?

Thanks

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Bulls and Cows AI
« Reply #3 on: February 01, 2019, 01:05:18 pm »
A couple of questions bplus - 1st, QB64 does not have a way to search a variable of numbers without the conversion to a string? for example Today = 20190201 so Day = Left(Today,2). Is that correct?
Thanks

Today = 20190201
Day = Today MOD 100
Month = (Today MOD 10000 ) \ 100
Year = Today \ 1000

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: Bulls and Cows AI
« Reply #4 on: February 01, 2019, 01:49:24 pm »
I just learned of a mistake I made with Bulls and Cows game. Apparently it is played with only the digits 1 to 9 with only 3024 possible permutations, not played with digits 0 to 9 and 5040 permutations.

Ah well, could probably set this up to play with any amount of letters and digits, just a matter of getting a list of all possible perms for the AI to prune with guesses.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Bulls and Cows AI
« Reply #5 on: February 01, 2019, 01:58:51 pm »
A couple of questions bplus - 1st, QB64 does not have a way to search a variable of numbers without the conversion to a string? for example Today = 20190201 so Day = Left(Today,2). Is that correct?
 2nd, in The Bulls and Cows AI search you have a line "FOR i = 123 TO 9876", where does the 123 come from? Is that ceding the order of a correct answer or just simply reducing the number of iterations?

Thanks

I think Steve might have question 1 covered. Day would be right$(today, 2) if today is a string, left$ or right$ won't work on a number.

as to 2nd question,
I started at 123 because I was going in numeric order from lowest non repeating "4" digit "numbers" to 9876 highest non repeating 4 digit number. 123 = 0123 in 4 digit string form, testing non repeats from 4 digit strings to build the original set of possible permutations. 0000 to 0122 will all have repeat digits, so I was skipping those tests.
« Last Edit: February 01, 2019, 02:08:00 pm by bplus »

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Bulls and Cows AI
« Reply #6 on: February 01, 2019, 02:41:51 pm »
OK so here is the AI fixed up for only digits 1 to 9:
Code: QB64: [Select]
  1. _TITLE "Bulls and Cows AI for digits 1 to 9" ' for QB64 B+ started 2019-01-31
  2. '2019-02-01 fix for digits 1 to 9
  3.  
  4. DEFINT A-Z
  5. DIM SHARED secret$
  6. DIM SHARED possibles(1 TO 9876) 'permutation T or F
  7.  
  8. 'As suggested by Rosetta,
  9. '  "One method is to generate a list of all possible numbers that could be the answer,"
  10. '  "then to prune the list by keeping only those numbers that would give an equivalent"
  11. '  "score to how your last guess was scored. Your next guess can be any number from the"
  12. '  "pruned list. Either you guess correctly or run out of numbers to guess, which"
  13. '  "indicates a problem with the scoring."
  14.  
  15.  
  16. 'Creating a list of all possible permutations of the 9 digits
  17. 'taken 4 at a time = 9*8*7*6 possibles = 3024.
  18. 'Loading such that if a nonrepeating 4 digit number then -1 else leave at 0
  19. FOR i = 1234 TO 9876
  20.     IF noRepeat(LTRIM$(STR$(i))) THEN possibles(i) = -1: count = count + 1
  21. 'check possibles count
  22. PRINT "Possible permutations of 4 non repeating digits ="; count 'equals 5040?
  23.  
  24. createSecretNumber
  25.  
  26. 'test score$ with a regular game of Bulls and Cows
  27. 'PRINT secret$
  28. 'guesses = 0
  29. 'DO
  30. '    INPUT "Please enter your 4 digit guess "; guess$
  31. '    guesses = guesses + 1
  32. '    PRINT score$(secret$, guess$)
  33. '    PRINT
  34. 'LOOP WHILE secret$ <> guess$
  35. 'PRINT "You found the number in"; guesses; " guesses."
  36.  
  37.  
  38. 'OK now for the main event
  39. PRINT "Here is the secret number so you can follow along: "; secret$
  40.     'INPUT "Please enter your 4 digit guess "; guess$
  41.  
  42.     'insert AI player here
  43.     r = INT(RND * 9876) + 1
  44.     WHILE possibles(r) = 0
  45.         r = r + 1
  46.         IF r > 9876 THEN r = 1234
  47.     WEND
  48.     guess$ = LTRIM$(STR$(r))
  49.  
  50.     'display the guess and it's score
  51.     PRINT "AI guesses "; guess$
  52.     guesses = guesses + 1
  53.     sc$ = score$(secret$, guess$)
  54.     PRINT "Scores: "; LEFT$(sc$, 1); " bull(s), "; RIGHT$(sc$, 1); " cow(s)"
  55.     IF sc$ <> "40" THEN
  56.         'now AI will use that score to eliminate all possibles that would not yeild the cattle count
  57.         changes = 0: remainder = 0
  58.         FOR i = 1234 TO 9876
  59.             IF possibles(i) <> 0 THEN
  60.                 is$ = RIGHT$("000" + LTRIM$(STR$(i)), 4)
  61.                 ' tsc$ = score$(guess$, is$)
  62.                 'PRINT "i string$ "; is$; "  score is "; tsc$
  63.  
  64.                 IF score$(guess$, is$) <> sc$ THEN possibles(i) = 0: changes = changes + 1 ELSE remainder = remainder + 1
  65.                 'INPUT "OK press enter "; wate$
  66.             END IF
  67.         NEXT
  68.         PRINT "AI reduced number of possible permutations by"; RTRIM$(STR$(changes)); ", so"; remainder; "possible(s) remain."
  69.         INPUT "OK press enter "; wate$
  70.     END IF
  71.     PRINT
  72. LOOP WHILE secret$ <> guess$
  73. PRINT "AI found the number in"; guesses; "guesses."
  74.  
  75.  
  76. SUB createSecretNumber
  77.     digits$ = "123456789": secret$ = ""
  78.     FOR i = 1 TO 4
  79.         p = INT(RND * LEN(digits$)) + 1
  80.         secret$ = secret$ + MID$(digits$, p, 1)
  81.         digits$ = MID$(digits$, 1, p - 1) + MID$(digits$, p + 1)
  82.     NEXT
  83.  
  84. FUNCTION noRepeat (d$)
  85.     IF LEN(d$) <> 4 THEN EXIT FUNCTION
  86.     IF INSTR(d$, "0") THEN EXIT FUNCTION
  87.     FOR i = 1 TO 3
  88.         c$ = MID$(d$, i, 1)
  89.         FOR j = i + 1 TO 4
  90.             IF c$ = MID$(d$, j, 1) THEN EXIT FUNCTION
  91.         NEXT
  92.     NEXT
  93.     noRepeat = -1
  94.  
  95. FUNCTION score$ (secret$, test$)
  96.     FOR i = 1 TO 4
  97.         c$ = MID$(test$, i, 1)
  98.         IF MID$(secret$, i, 1) = c$ THEN
  99.             bulls = bulls + 1
  100.         ELSEIF INSTR(secret$, c$) THEN
  101.             cows = cows + 1
  102.         END IF
  103.     NEXT i
  104.     score$ = LTRIM$(STR$(bulls)) + LTRIM$(STR$(cows))
  105.  
« Last Edit: February 01, 2019, 02:56:04 pm by bplus »