QB64.org Forum

Active Forums => Programs => Topic started by: bplus on April 25, 2018, 03:39:39 am

Title: Battleship with AI
Post by: bplus on April 25, 2018, 03:39:39 am
Some background: https://en.wikipedia.org/wiki/Battleship_(game)

The game with some room for improvement with AI but still can play game well enough.

Some snaps: My first game with AI, the first time it beat me and current version with some debug info still showing

Update 2018-04-25 PM a new zip file replaces the old with code change of displaying only the ships SUNK.
The last screen shot is of the current code.

Update 2018-04-26 a new zip file again replaces the old code with the following:
New bas source file that now uses an outer Play Again loop and an Auto-setup for the Player for quick start to shooting Game.
Now using 3 png image files for tiles and 6 wav sound files for dramatic effect. Plus the New Player Instruction.txt file as promised.
Title: Re: Battleship with AI
Post by: bplus on April 25, 2018, 02:59:07 pm
OK next update of this game, I am definitely only going to show what ships are sunk.

All the hits on each ship (immediate feedback) is not legal intelligence and the AI is not using it.

There is a sort of referee HitEval sub that "announces when a ship is sunk" to each party and it is the part of the code that is tracking the hits on the ships.
Title: Re: Battleship with AI
Post by: bplus on April 25, 2018, 09:42:56 pm
And now, the original post has been modified with new zip and screen shot with the changes explained above.
Title: Re: Battleship with AI
Post by: FellippeHeitor on April 26, 2018, 09:47:18 am
Fun to play, bplus! Good job once again.
Title: Re: Battleship with AI
Post by: bplus on April 26, 2018, 10:07:49 am
Thanks Fellippe!

I have written up a New Player Instructions.txt file that should word wrap OK:

(Trying a code box instead of a quote box here)
Code: QB64: [Select]
  1. The object of the game is to sink all the Computer's ships before it sinks all yours.
  2.  
  3. Both the Player and the Computer are given 5 ships to lay out on a 10x10 grid.
  4.  
  5. The ships are a straight line of squares (2 to 5 squares) forming a long rectangle.
  6. The ships are laid vertically or horizontally on the 10x10 cell grid without overlap.
  7. Each square must be hit by the opponent in order to sink the ship.
  8.  
  9. The 5 ships are:
  10. Carrier    - 5 squares to hit
  11. Battleship - 4 squares to hit
  12. Cruiser    - 3 squares to hit
  13. Submarine  - 3 squares to hit
  14. Destroyer  - 2 squares to hit
  15.  
  16. The game is started by each opponent laying out their ships secretly to the other.
  17. You the Player must setup your ships on the right board.
  18. They are setup in same order I listed above.
  19.  
  20. So the first ship to set up will be the Carrier that is 5 squares long.
  21. First you will be prompted whether you want to lay it out horizontally or vertically, h or v ?
  22.  
  23. Then if horizontally is chosen, you click the cell where you want the left most square of the ship to go.
  24. Like wise if vertical v was chosen, you click the board cell where you want the top most square to go.
  25.  
  26. If there is room on board to lay out all 5 across AND this ship does not overlap another, then the rest of the ship will be drawn in.
  27. (Of course, the first ship can't overlap another but every other ship has that potential.)
  28. If there is not room or the ship would overlap another, then you must start over with the prompt to lay the ship horizontally or vertically...
  29.  
  30. When you get all 5 of your ships laid out on the 10x10 grid on the left, the shooting match begins!
  31.  
  32. You will be prompted to click a cell on the left 10x10 board to guess where a Computer's ship might be.
  33. If you hit a square on one of the Computers ships a red dot = hit appears at that cell.
  34. If you miss all the Computers ships, a white dot will appear = miss
  35.  
  36. The Computer will then take a shot and your board will show a red or white dot according to the Computer's hit or miss.
  37.  
  38. Then it's your turn again. If you had a hit the last turn you will likely want to find the rest of the ship to sink it.
  39. So click above, below, left or right of the hit = red dot.
  40. A 2nd hit will tell you if the ship is laid out horizontally or vertically.
  41. A 2nd hit would actually sink a Destroyer because it is only 2 squares long.
  42.  
  43. So you scout around the 10x10 board making random shots (or systematically cover the board with shots)
  44. until you find a ship, sink it and go hunting for the next ship to sink until you get all 5.
  45.  
  46. Meanwhile the Computer is doing the same thing, so which ever opponent sinks all the ships first, wins!
  47.  
  48. Oh a caveat!
  49. It is possible to align the ships side by side or one end up next to another ship (as long as they don't overlap).
  50. This makes it confusing as you might be hitting 2 different ships with your shots, so pay close attention to which ship is announced sunk
  51. you might have more hits in the same area than how many it took to sink the ship.
  52.  
  53. https://en.wikipedia.org/wiki/Battleship_game
  54.  
  55.  

I hope to include a file similar to this based on feedback I get from comments new player or old,
so your opinions would be appreciated. Thanks
Title: Re: Battleship with AI
Post by: bplus on April 27, 2018, 12:14:00 am
The original post has been updated with newest source code, sound and image files as well as the New Player Instruction.txt file.
Title: Re: Battleship with AI
Post by: bplus on May 14, 2018, 12:57:26 am
Battleship 5-14 Update
Title: Re: Battleship with AI
Post by: FellippeHeitor on May 14, 2018, 12:59:04 am
Wow, this seems like it's come a long way! Haven't played this update yet but it sure looks good.
Title: Re: Battleship with AI
Post by: bplus on May 14, 2018, 01:01:04 am
Thanks lot's of help with assets from Johnno.

Have fun!
Title: Re: Battleship with AI
Post by: Ashish on May 14, 2018, 01:54:04 am
Nice work bplus! I like the game!
Title: Re: Battleship with AI
Post by: bplus on May 15, 2018, 09:58:32 am
Studying systematic board coverage of "random" shots for smarter AI.

Code: QB64: [Select]
  1. CONST gsq = 40
  2. CONST gox = 200
  3. CONST goy = 100
  4. CONST nsq = 10
  5. CONST n1 = nsq - 1
  6. CONST xmax = 800
  7. CONST ymax = 600
  8. DIM SHARED rndList(n1)
  9.  
  10. main& = _NEWIMAGE(xmax, ymax, 32)
  11. SCREEN main&
  12. _SCREENMOVE 360, 60
  13.  
  14.  
  15. drawGrid gox, goy, gsq, nsq
  16. FOR modulus = 5 TO 2 STEP -1
  17.     c$ = LTRIM$(STR$(modulus))
  18.     COLOR RGB(c$ + c$ + c$)
  19.  
  20.     FOR y = 0 TO n1
  21.         offset = y MOD modulus
  22.         maxM = INT((n1 - offset) / modulus)
  23.         getRndChoice y, modulus
  24.         FOR xindex = 0 TO maxM
  25.             col = rndList(xindex)
  26.             LINE (gox + col * gsq + 3 * (7 - modulus), goy + y * gsq + 3 * (7 - modulus))-STEP(gsq - 6 * (7 - modulus), gsq - 6 * (7 - modulus)), , BF
  27.             '_DELAY 1
  28.         NEXT
  29.     NEXT
  30.     _DELAY 2
  31.  
  32. SUB getRndChoice (rc, modulus)
  33.     offset = rc MOD modulus
  34.     maxM = INT((n1 - offset) / modulus)
  35.     FOR i = 0 TO n1
  36.         rndList(i) = i
  37.     NEXT
  38.     FOR i = 0 TO maxM
  39.         n = offset + i * modulus
  40.         SWAP rndList(i), rndList(n)
  41.     NEXT
  42.     FOR i = maxM TO 1 STEP -1
  43.         r = INT((i + 1) * RND)
  44.         SWAP rndList(i), rndList(r)
  45.     NEXT
  46.     FOR i = maxM + 1 TO n1
  47.         r = INT((n1 - maxM) * RND) + maxM + 1
  48.         SWAP rndList(i), rndList(r)
  49.     NEXT
  50.  
  51. SUB drawGrid (x, y, sq, n)
  52.     d = sq * n
  53.     FOR i = 0 TO n
  54.         LINE (x + sq * i, y)-(x + sq * i, y + d)
  55.         LINE (x, y + sq * i)-(x + d, y + sq * i)
  56.     NEXT
  57.  
  58. FUNCTION RGB& (s3$) ' New Color System 1000 colors with 3 digits!!!!!!!!!!!!!!!!
  59.     l = LEN(s3$)
  60.     IF l THEN r = 28 * VAL(MID$(s3$, 1, 1)) + 3
  61.     IF l >= 2 THEN g = 28 * VAL(MID$(s3$, 2, 1)) + 3
  62.     IF l >= 3 THEN b = 28 * VAL(MID$(s3$, 3, 1)) + 3
  63.     RGB& = _RGB32(r, g, b)
  64.  
  65.  

Sometimes studies make pretty pictures.
Title: Re: Battleship with AI
Post by: bplus on May 15, 2018, 01:11:58 pm
I haven't done the math yet but I am testing a modulus 3 coverage of board. It seems to find the Destroyer faster with less shots.

With modulus 2 coverage, you are guaranteed to find all ships including Destroyer in 50 shots or less. With modulus 3 coverage you will find all ships in 34 shots guaranteed, except Destroyer, which could fall between the cracks so to speak and take up to 98 shots to find (edit: even 99!).

So what are odds of going big with mod 3 coverage and winning or playing it safe with mod 2 coverage?

Maybe this code will give you a feel for determining if the risk of M = 3 coverage and possibly needing more than 50 shots is worth it or not.

Code: QB64: [Select]
  1. _TITLE "m3 34 m2.bas 2018-05-15,  press any key to quit..."
  2.  
  3. 'in 34 shots (m = 3) I should hit all the ships length 3 and up
  4. 'and if I haven't hit destroyer yet shift to every other square m = 2
  5.  
  6. CONST gsq = 40
  7. CONST gox = 200
  8. CONST goy = 100
  9. CONST nsq = 10
  10. CONST n1 = nsq - 1
  11. CONST xmax = 800
  12. CONST ymax = 600
  13. DIM SHARED rndList(n1)
  14. DIM hits(n1, n1)
  15. main& = _NEWIMAGE(xmax, ymax, 32)
  16. SCREEN main&
  17. _SCREENMOVE 360, 60
  18.  
  19. WHILE LEN(k$) = 0
  20.     CLS
  21.     ERASE hits
  22.     drawGrid gox, goy, gsq, nsq
  23.     shotCnt = 0
  24.     Sunk = 0
  25.     dx = rand(0, n1 - 1)
  26.     dx2 = dx + 1
  27.     dy = rand(0, n1)
  28.  
  29.     FOR i = 1 TO 10
  30.         IF i MOD 2 THEN COLOR RGB("900") ELSE COLOR RGB("999")
  31.         LINE (gox + dx * gsq + 2 * i, goy + dy * gsq + 2 * i)-STEP(2 * gsq - 4 * i, gsq - 4 * i), , BF
  32.     NEXT
  33.     WHILE LEN(k$) = 0
  34.         k$ = INKEY$
  35.         y = y + 1
  36.         IF y = nsq THEN y = 0
  37.  
  38.         IF shotCnt < 34 THEN
  39.             COLOR RGB("009")
  40.             modulus = 3
  41.             offset = y MOD modulus
  42.             maxM = INT((n1 - offset) / modulus)
  43.         ELSE
  44.             IF Sunk = 0 THEN modulus = 2: COLOR RGB("990") ELSE modulus = 3: COLOR RGB("099")
  45.             maxM = n1
  46.         END IF
  47.  
  48.         xindex = 0
  49.         getRndChoice y, modulus
  50.         testx = rndList(xindex)
  51.         shoot = 1
  52.         WHILE hits(testx, y) <> 0
  53.             xindex = xindex + 1
  54.             IF xindex > maxM THEN shoot = 0: EXIT WHILE
  55.             testx = rndList(xindex)
  56.         WEND
  57.         IF shoot <> 0 THEN
  58.             col = testx
  59.             LINE (gox + col * gsq + 3 * (7 - modulus), goy + y * gsq + 3 * (7 - modulus))-STEP(gsq - 6 * (7 - modulus), gsq - 6 * (7 - modulus)), , BF
  60.             hits(col, y) = 1
  61.             shotCnt = shotCnt + 1
  62.             IF Sunk = 0 THEN
  63.                 IF (col = dx OR col = dx2) AND y = dy THEN Sunk = 1: LOCATE 1, 1: PRINT "Destroyer Hit! in"; STR$(shotCnt); " shots."
  64.             END IF
  65.             IF Sunk THEN _DELAY .01 ELSE _DELAY .25
  66.         END IF
  67.         IF shotCnt >= 100 THEN _DELAY 5: EXIT WHILE
  68.     WEND
  69. SUB getRndChoice (rc, modulus)
  70.     offset = rc MOD modulus
  71.     maxM = INT((n1 - offset) / modulus)
  72.     FOR i = 0 TO n1
  73.         rndList(i) = i
  74.     NEXT
  75.     FOR i = 0 TO maxM
  76.         n = offset + i * modulus
  77.         SWAP rndList(i), rndList(n)
  78.     NEXT
  79.     FOR i = maxM TO 1 STEP -1
  80.         r = INT((i + 1) * RND)
  81.         SWAP rndList(i), rndList(r)
  82.     NEXT
  83.     FOR i = maxM + 1 TO n1
  84.         r = INT((n1 - maxM) * RND) + maxM + 1
  85.         SWAP rndList(i), rndList(r)
  86.     NEXT
  87.  
  88. SUB drawGrid (x, y, sq, n)
  89.     d = sq * n
  90.     FOR i = 0 TO n
  91.         LINE (x + sq * i, y)-(x + sq * i, y + d)
  92.         LINE (x, y + sq * i)-(x + d, y + sq * i)
  93.     NEXT
  94.  
  95. FUNCTION RGB& (s3$) ' New Color System 1000 colors with 3 digits!!!!!!!!!!!!!!!!
  96.     l = LEN(s3$)
  97.     IF l THEN r = 28 * VAL(MID$(s3$, 1, 1)) + 3
  98.     IF l >= 2 THEN g = 28 * VAL(MID$(s3$, 2, 1)) + 3
  99.     IF l >= 3 THEN b = 28 * VAL(MID$(s3$, 3, 1)) + 3
  100.     RGB& = _RGB32(r, g, b)
  101.  
  102. FUNCTION rand% (lo%, hi%)
  103.     rand% = INT(RND * (hi% - lo% + 1)) + lo%
  104.  
  105.  

So how is your math or probability intuition? Would you go mod 3 or mod 2?
Title: Re: Battleship with AI
Post by: bplus on May 15, 2018, 05:42:23 pm
Upon second thought, if first 34 shots miss Destroyer can catch in next 30 for sure, don't know why I would switch to mod 2 after 34 shots in mod 3 covers the board. 30 = 3 more shots * 10 rows.
Title: Re: Battleship with AI
Post by: bplus on May 18, 2018, 11:24:04 pm
Wednesday, I come up with a really neat little function I am calling cover(modulus, bump, x, y) which returns TF according to whether the square is part a modulus plan to systematically cover board in every m squares.

Then I proceeded to make one blunder after another for 2 days finally getting the thing to work like this!
Code: QB64: [Select]
  1. _TITLE "shoot test,  press any to quit..."
  2.  
  3. 'first get a function to return ture/false to shoot spot x, y if it is part of coverage or not
  4. 'DONE and what a cool function it is too!!!
  5.  
  6. '2018-05-18 It's working!!! time to test in real app
  7.  
  8. CONST gsq = 40
  9. CONST gox = 200
  10. CONST goy = 100
  11. CONST sqPerSide = 10
  12. CONST n1 = sqPerSide - 1
  13. CONST xmax = 800
  14. CONST ymax = 600
  15. DIM SHARED sunk, row, col, lastm, colA, bump
  16. DIM SHARED hits(n1, n1)
  17. main& = _NEWIMAGE(xmax, ymax, 32)
  18. SCREEN main&
  19. _SCREENMOVE 360, 60
  20.  
  21. k$ = ""
  22. restart:
  23. shotCnt = 0: sunk = 0
  24. ERASE hits
  25. colA = -1 '<<<<<<<<<<<<<<< don't forget to signal start!
  26. 'draw grid
  27. rgb 999
  28. drawGrid gox, goy, gsq, sqPerSide
  29.  
  30. ''destroyer target
  31. dx = rand(0, n1 - 1)
  32. dx2 = dx + 1
  33. dy = rand(0, n1)
  34. 'draw the Destroyer
  35. FOR i = 1 TO 10
  36.     IF i MOD 2 THEN rgb 900 ELSE rgb 999
  37.     LINE (gox + dx * gsq + 2 * i, goy + dy * gsq + 2 * i)-STEP(2 * gsq - 4 * i, gsq - 4 * i), , BF
  38.  
  39. 'start shooting
  40. WHILE LEN(k$) = 0
  41.     k$ = INKEY$
  42.     shoot sx, sy
  43.  
  44.     'accounting
  45.     hits(sx, sy) = 1
  46.     shotCnt = shotCnt + 1
  47.  
  48.     'show shot
  49.     IF lastm = 2 THEN rgb 990 ELSE rgb 9
  50.  
  51.     LINE (gox + sx * gsq, goy + sy * gsq)-STEP(gsq, gsq), , BF
  52.  
  53.     'hit target first time?
  54.     IF sunk = 0 THEN
  55.         IF (sx = dx OR sx = dx2) AND sy = dy THEN
  56.             sunk = 1: rgb 999: LOCATE 1, 1: PRINT "Destroyer Hit! in"; STR$(shotCnt); " shots."
  57.         END IF
  58.         _DELAY .02
  59.     ELSE
  60.         _DELAY .1
  61.     END IF
  62.  
  63.     IF shotCnt = 100 THEN EXIT WHILE
  64. GOTO restart
  65.  
  66. 'first test cover  COMMENT OUT ABOVE CODE AND UNCOMMENT following for cool graphic!
  67. 'm = 3
  68. 'WHILE 1
  69. '    FOR bump = 0 TO m - 1
  70. '        CLS
  71. '        FOR y = 0 TO n1
  72. '            FOR x = 0 TO n1
  73. '                FOR mm = m TO 2 STEP -1
  74. '                    SELECT CASE mm
  75. '                        CASE 8: rgb 9
  76. '                        CASE 7: rgb 90
  77. '                        CASE 6: rgb 900
  78. '                        CASE 5: rgb 99
  79. '                        CASE 4: rgb 990
  80. '                        CASE 3: rgb 909
  81. '                        CASE 2: rgb 999
  82. '                    END SELECT
  83. '                    IF cover(mm, bump, x, y) THEN
  84. '                        LINE (gox + x * gsq + 1, goy + y * gsq + 1)-STEP(gsq - 2, gsq - 2), , BF
  85. '                    END IF
  86. '                NEXT
  87. '            NEXT
  88. '        NEXT
  89. '        _DISPLAY
  90. '        _LIMIT 1
  91. '    NEXT
  92. 'WEND
  93.  
  94. SUB drawGrid (x, y, sq, n)
  95.     d = sq * n
  96.     FOR i = 0 TO n
  97.         LINE (x + sq * i, y)-(x + sq * i, y + d)
  98.         LINE (x, y + sq * i)-(x + d, y + sq * i)
  99.     NEXT
  100.  
  101. SUB rgb (n) ' New (even less typing!) New Color System 1000 colors with up to 3 digits
  102.     s3$ = RIGHT$("000" + LTRIM$(STR$(n)), 3)
  103.     r = VAL(MID$(s3$, 1, 1)): IF r THEN r = 28 * r + 3
  104.     g = VAL(MID$(s3$, 2, 1)): IF g THEN g = 28 * g + 3
  105.     b = VAL(MID$(s3$, 3, 1)): IF b THEN b = 28 * b + 3
  106.     COLOR _RGB32(r, g, b)
  107.  
  108. FUNCTION rand% (lo%, hi%)
  109.     rand% = INT(RND * (hi% - lo% + 1)) + lo%
  110.  
  111. SUB shoot (col, row) 'col, row aren't inputs so mush as outputs like a double function return wo input parameters
  112.  
  113.     'i = nShips
  114.     'WHILE shipSunk(i) 'find smallest ship not sunk
  115.     '    i = i - 1
  116.     'WEND
  117.     'SELECT CASE i 'm for modulus, d for direction to run a check from
  118.     '    CASE nShips: m = 2 'still have destroyer
  119.     '    CASE nShips - 1: m = 3 'still have sub
  120.     '    CASE nShips - 2: m = 3 'still have cruiser
  121.     '    CASE nShips - 3: m = 4 'still have battleship
  122.     '    CASE nShips - 4: m = 5 'still have carrier
  123.     '    CASE ELSE: TxtBx "990", "m", "Aren't all the Player's ships sunk?": m = 7
  124.     'END SELECT
  125.     IF lastm = 7 THEN EXIT SUB
  126.     IF sunk THEN m = 3 ELSE m = 2
  127.     'IF m <> lastm THEN
  128.     lastm = m 'lastm  is solely needed for coloring in main
  129.     bc = 0 'if bc is reset to 0 each time don't need it shared
  130.     'END IF
  131.  
  132.     IF colA = -1 THEN 'col the Attact starts from notice it is random so player can't anticipate
  133.         colA = rand%(0, n1): col = colA: row = rand(0, n1): bump = rand(0, m - 1): bc = 0
  134.     END IF
  135.  
  136.     'm 7 is just in case some error occurs have fall back
  137.     IF m <> 7 THEN
  138.  
  139.         WHILE bc < m
  140.             cc = 1
  141.             WHILE cc <= sqPerSide
  142.                 rc = 0
  143.                 WHILE rc <= sqPerSide 'find a space to hit if one left in this column
  144.                     IF cover(m, bump, col, row) THEN 'are we on a place to cover board
  145.                         IF hits(col, row) = 0 THEN EXIT SUB 'good to go!
  146.                     END IF
  147.                     row = (row + 1) MOD sqPerSide
  148.                     rc = rc + 1
  149.                 WEND
  150.                 row = row - 1
  151.                 IF row < 0 THEN row = n1
  152.                 'still here means we checked all rows in col so check next col
  153.                 col = (col + 1) MOD sqPerSide
  154.                 cc = cc + 1
  155.             WEND
  156.             'still here ? then up the bump
  157.             bump = (bump + 1) MOD m
  158.             bc = bc + 1
  159.         WEND
  160.         m = 7 'error fall through
  161.  
  162.  
  163.     END IF 'm<> 7
  164.  
  165.     'rexamine all the hits and check all holes filled around them
  166.     'TO DO
  167.  
  168.     '  if all else fails
  169.     IF m = 7 THEN 'just find a hole not tried yet and exit!
  170.         lastm = 7
  171.         LOCATE 2, 1: PRINT "AI in m=7 mode !!! bc = "; bc
  172.         'FOR row = 0 TO n1
  173.         '    FOR col = 0 TO n1
  174.         '        IF hits(col, row) = 0 THEN EXIT SUB
  175.         '    NEXT
  176.         'NEXT
  177.     END IF
  178. END SUB '  128 lines to take a random shot!!!!
  179.  
  180. 'using a modulus m coverage with a bump so that opponent can't predict where
  181. 'the hardest place to plant the Detroyer will be
  182. FUNCTION cover (m, bump, c, r)
  183.     bm = bump MOD m 'make sure bump is in modulus
  184.     cm = (c + bm) MOD m
  185.     rm = r MOD m
  186.     IF rm = cm THEN cover = -1 ELSE cover = 0
  187.  
  188. 'turns out I did not need this but it should be noted:
  189. ' the cnt is different according to bump if modulus is odd
  190. 'amd maybe if nSquare is odd and modulus is even
  191. 'how many (non repeating) shots to cover a square n X n
  192. FUNCTION coverageCnt (nSquare, modulus, bump)
  193.     FOR y = 0 TO nSquare - 1
  194.         FOR x = 0 TO nSquare - 1
  195.             IF cover(modulus, bump, x, y) THEN cnt = cnt + 1
  196.         NEXT
  197.     NEXT
  198.     coverageCnt = cnt
  199.  
  200.  

Now I can systematically cover the whole board in a minimum of shots according to smallest ship not sunk yet.
It can even cover the whole board if the AI doesn't know what to do with a hit.

The new rgb function now takes even less letters to command 1 of 1000 colors, 7 letters or digits at most.

Quote
PS OK the code seems to be working fine in Battleship game, I can get rid of all that preplanned shooting junk!

Next, a smarter system for sinking ships once they've been hit.

What I like about this AI is that it plays like a merciless machine! systematically covering the board with a minimum of shots needed to find every ship. It has the personality of the terminator.
Title: Re: Battleship with AI
Post by: bplus on May 28, 2018, 08:14:32 am
Here is latest update of Battleship with the improvements to the AI play.

I am interested to know if anyone runs into any errors specially #5 specially using Linux.

Just click first screen to get fire started:
Title: Re: Battleship with AI
Post by: STxAxTIC on May 28, 2018, 01:48:49 pm
Heya bplus,

I've been following this for a while now - nice progress!

For the past week or so, I've been mucking around with a recursive solver for the AI engine. Below you can see what I decided to push to the forums. It's got a very rudimentary setup - 10x10 ocean, with a weighted random distribution of ships. The algo itself can be tweaked heavily - at this point it seems to work nicely, but maybe a few numbers could change when it's time to play against a human (or itself I suppose). Anyway, watch and be inspired. Feel free to ignore it, too:

Code: QB64: [Select]
  1. '. = open, S = ship, H = hit, ~ = Miss
  2.  
  3.  
  4. DIM SHARED ocean(10, 10) AS STRING
  5.  
  6. FOR i = 1 TO 10
  7.     FOR j = 1 TO 10
  8.         IF RND > (10 - i) * (10 - j) * .05 THEN
  9.             ocean(i, j) = "S"
  10.         ELSE
  11.             ocean(i, j) = "."
  12.         END IF
  13.     NEXT
  14.  
  15. CALL printmap
  16.     CALL tryhit(1, 10, 1, 10)
  17. LOOP UNTIL checkdone(1, 10, 1, 10) = 1
  18.  
  19. SUB tryhit (xstart, xend, ystart, yend)
  20.     IF xstart < 1 THEN xstart = 1
  21.     IF xend > 10 THEN xend = 10
  22.     IF ystart < 1 THEN ystart = 1
  23.     IF yend > 10 THEN yend = 10
  24.     IF checkdone(xstart, xend, ystart, yend) = 0 THEN
  25.         xguess = INT(xstart + RND * (xend - xstart + 1))
  26.         yguess = INT(ystart + RND * (yend - ystart + 1))
  27.         _DELAY .1
  28.         SELECT CASE ocean(xguess, yguess)
  29.             CASE "S"
  30.                 ocean(xguess, yguess) = "H"
  31.                 CALL printmap
  32.                 FOR k = 1 TO 64
  33.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
  34.                 NEXT
  35.             CASE "H"
  36.                 ocean(xguess, yguess) = "H"
  37.                 CALL printmap
  38.                 FOR k = 1 TO 8
  39.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
  40.                 NEXT
  41.             CASE ".", "~"
  42.                 ocean(xguess, yguess) = "~"
  43.                 CALL printmap
  44.                 CALL tryhit(xstart, xend, ystart, yend)
  45.         END SELECT
  46.     END IF
  47.  
  48. FUNCTION checkdone (xstart, xend, ystart, yend)
  49.     done = 1
  50.     FOR i = xstart TO xend
  51.         FOR j = ystart TO yend
  52.             IF ocean(i, j) = "." THEN
  53.                 done = 0
  54.             END IF
  55.         NEXT
  56.     NEXT
  57.     checkdone = done
  58.  
  59. SUB printmap
  60.     CLS
  61.     counter1 = 0
  62.     counter2 = 0
  63.     counter3 = 0
  64.     counter4 = 0
  65.     FOR i = 1 TO 10
  66.         FOR j = 1 TO 10
  67.             LOCATE j * 2, i * 3
  68.             PRINT ocean(i, j)
  69.             IF ocean(i, j) = "." THEN counter1 = counter1 + 1
  70.             IF ocean(i, j) = "~" THEN counter2 = counter2 + 1
  71.             IF ocean(i, j) = "S" THEN counter3 = counter3 + 1
  72.             IF ocean(i, j) = "H" THEN counter4 = counter4 + 1
  73.         NEXT
  74.     NEXT
  75.     LOCATE 20, 60: PRINT "."; counter1
  76.     LOCATE 21, 60: PRINT "~"; counter2
  77.     LOCATE 22, 60: PRINT "S"; counter3
  78.     LOCATE 23, 60: PRINT "H"; counter4
  79.     IF counter3 = 0 THEN END
  80.  
Title: Re: Battleship with AI
Post by: bplus on May 28, 2018, 03:00:33 pm
Hi STxAxTIC

I do not understand your setup of ships so I borrowed code from Battleship, autosetup.
Code: QB64: [Select]
  1. '. = open, S = ship, H = hit, ~ = Miss
  2.  
  3.  
  4. DIM SHARED ocean(10, 10) AS STRING
  5.  
  6. FOR s = 1 TO 5
  7.     IF s < 3 THEN sl = s + 1 ELSE sl = s 'ship lengths
  8.     OK = 0
  9.     WHILE OK = 0
  10.         shipHor = rand(0, 1)
  11.         IF shipHor = 1 THEN
  12.             sy = rand(1, 10)
  13.             sx = rand(1, 10 - sl)
  14.             OK = -1
  15.             FOR xx = 0 TO sl - 1
  16.                 IF ocean(sx + xx, sy) = "S" THEN OK = 0: EXIT FOR
  17.             NEXT
  18.             IF OK THEN
  19.                 FOR xx = 0 TO sl - 1
  20.                     ocean(sx + xx, sy) = "S"
  21.                 NEXT
  22.             END IF
  23.         ELSE
  24.             sx = rand(1, 10)
  25.             sy = rand(1, 10 - sl)
  26.             OK = -1
  27.             FOR yy = 0 TO sl - 1
  28.                 IF ocean(sx, sy + yy) = "S" THEN OK = 0: EXIT FOR
  29.             NEXT
  30.             IF OK THEN
  31.                 FOR yy = 0 TO sl - 1
  32.                     ocean(sx, sy + yy) = "S"
  33.                 NEXT
  34.             END IF
  35.         END IF
  36.     WEND
  37. FOR y = 1 TO 10
  38.     FOR x = 1 TO 10
  39.         IF ocean(x, y) <> "S" THEN ocean(x, y) = "."
  40.     NEXT
  41.  
  42. CALL printmap
  43.     CALL tryhit(1, 10, 1, 10)
  44. LOOP UNTIL checkdone(1, 10, 1, 10) = 1
  45.  
  46. SUB tryhit (xstart, xend, ystart, yend)
  47.     IF xstart < 1 THEN xstart = 1
  48.     IF xend > 10 THEN xend = 10
  49.     IF ystart < 1 THEN ystart = 1
  50.     IF yend > 10 THEN yend = 10
  51.     IF checkdone(xstart, xend, ystart, yend) = 0 THEN
  52.         xguess = INT(xstart + RND * (xend - xstart + 1))
  53.         yguess = INT(ystart + RND * (yend - ystart + 1))
  54.         _DELAY .1
  55.         SELECT CASE ocean(xguess, yguess)
  56.             CASE "S"
  57.                 ocean(xguess, yguess) = "H"
  58.                 CALL printmap
  59.                 FOR k = 1 TO 64
  60.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
  61.                 NEXT
  62.             CASE "H"
  63.                 ocean(xguess, yguess) = "H"
  64.                 CALL printmap
  65.                 FOR k = 1 TO 8
  66.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
  67.                 NEXT
  68.             CASE ".", "~"
  69.                 ocean(xguess, yguess) = "~"
  70.                 CALL printmap
  71.                 CALL tryhit(xstart, xend, ystart, yend)
  72.         END SELECT
  73.     END IF
  74.  
  75. FUNCTION checkdone (xstart, xend, ystart, yend)
  76.     done = 1
  77.     FOR i = xstart TO xend
  78.         FOR j = ystart TO yend
  79.             IF ocean(i, j) = "." THEN
  80.                 done = 0
  81.             END IF
  82.         NEXT
  83.     NEXT
  84.     checkdone = done
  85.  
  86. SUB printmap
  87.     CLS
  88.     counter1 = 0
  89.     counter2 = 0
  90.     counter3 = 0
  91.     counter4 = 0
  92.     FOR i = 1 TO 10
  93.         FOR j = 1 TO 10
  94.             LOCATE j * 2, i * 3
  95.             PRINT ocean(i, j)
  96.             IF ocean(i, j) = "." THEN counter1 = counter1 + 1
  97.             IF ocean(i, j) = "~" THEN counter2 = counter2 + 1
  98.             IF ocean(i, j) = "S" THEN counter3 = counter3 + 1
  99.             IF ocean(i, j) = "H" THEN counter4 = counter4 + 1
  100.         NEXT
  101.     NEXT
  102.     LOCATE 20, 60: PRINT "."; counter1
  103.     LOCATE 21, 60: PRINT "~"; counter2
  104.     LOCATE 22, 60: PRINT "S"; counter3
  105.     LOCATE 23, 60: PRINT "H"; counter4
  106.     IF counter3 = 0 THEN END
  107.  
  108. FUNCTION rand (lo, hi)
  109.     rand = INT(RND * (hi - lo + 1)) + lo
  110.  
  111.  

I can see your code better now working over a hit area. It leaves a miss occasionally but not bad for random process!

The trouble with recursive process, is that it must be interrupted for the Player to take his turn after each and every try.
Can your process stop, let the other player take a shot and then pick up where it left off?

Well I still don't fully understand how it is working over the hit area but I will see what I can do... :)
Title: Re: Battleship with AI
Post by: STxAxTIC on May 28, 2018, 03:12:57 pm
Hello,

Dang, you caught the post before I could mod it. I'll think harder about whether the whole idea was a good one when I;m not in a terrible rush. For now, here is one tweak that made it more accurate from my basic testing:

Code: QB64: [Select]
  1. '. = open, S = ship, H = hit, ~ = Miss
  2.  
  3.  
  4. DIM SHARED ocean(10, 10) AS STRING
  5.  
  6. FOR i = 1 TO 10
  7.     FOR j = 1 TO 10
  8.         IF RND > (10 - i) * (10 - j) * .05 THEN
  9.             'IF i = 5 THEN
  10.             ocean(i, j) = "S"
  11.         ELSE
  12.             ocean(i, j) = "."
  13.         END IF
  14.     NEXT
  15.  
  16. CALL printmap
  17.     CALL tryhit(1, 10, 1, 10)
  18. LOOP UNTIL checkdone(1, 10, 1, 10) = 1
  19.  
  20. SUB tryhit (xstart, xend, ystart, yend)
  21.     IF xstart < 1 THEN xstart = 1
  22.     IF xend > 10 THEN xend = 10
  23.     IF ystart < 1 THEN ystart = 1
  24.     IF yend > 10 THEN yend = 10
  25.     IF checkdone(xstart, xend, ystart, yend) = 0 THEN
  26.         xguess = INT(xstart + RND * (xend - xstart + 1))
  27.         yguess = INT(ystart + RND * (yend - ystart + 1))
  28.         _DELAY .1
  29.         SELECT CASE ocean(xguess, yguess)
  30.             CASE "S", "H"
  31.                 ocean(xguess, yguess) = "H"
  32.                 CALL printmap
  33.                 FOR k = 1 TO 64
  34.                     CALL tryhit(xguess - 1, xguess + 1, yguess - 1, yguess + 1)
  35.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
  36.                 NEXT
  37.             CASE ".", "~"
  38.                 ocean(xguess, yguess) = "~"
  39.                 CALL printmap
  40.         END SELECT
  41.     END IF
  42.  
  43. FUNCTION checkdone (xstart, xend, ystart, yend)
  44.     done = 1
  45.     FOR i = xstart TO xend
  46.         FOR j = ystart TO yend
  47.             IF ocean(i, j) = "." THEN
  48.                 done = 0
  49.             END IF
  50.         NEXT
  51.     NEXT
  52.     checkdone = done
  53.  
  54. SUB printmap
  55.     CLS
  56.     counter1 = 0
  57.     counter2 = 0
  58.     counter3 = 0
  59.     counter4 = 0
  60.     FOR i = 1 TO 10
  61.         FOR j = 1 TO 10
  62.             LOCATE j * 2, i * 3
  63.             PRINT ocean(i, j)
  64.             IF ocean(i, j) = "." THEN counter1 = counter1 + 1
  65.             IF ocean(i, j) = "~" THEN counter2 = counter2 + 1
  66.             IF ocean(i, j) = "S" THEN counter3 = counter3 + 1
  67.             IF ocean(i, j) = "H" THEN counter4 = counter4 + 1
  68.         NEXT
  69.     NEXT
  70.     LOCATE 20, 60: PRINT "."; counter1
  71.     LOCATE 21, 60: PRINT "~"; counter2
  72.     LOCATE 22, 60: PRINT "S"; counter3
  73.     LOCATE 23, 60: PRINT "H"; counter4
  74.     IF counter3 = 0 THEN END
  75.  
Title: Re: Battleship with AI
Post by: bplus on May 28, 2018, 03:44:15 pm
I have to warn, games are usually over (with Battleship 5-AI) leaving 30-40% ocean left undisturbed. I will have to run some stats.
Title: Re: Battleship with AI
Post by: Petr on May 28, 2018, 04:07:56 pm
Hi BPlus. I have found that you are not testing whether a player twice (or more than once) shoots at the same place. My version is watching this. I have a question about the used BMP pictures. Are these your extra programs outputs saved as bitmaps or do you use any graphics program?
Title: Re: Battleship with AI
Post by: bplus on May 28, 2018, 06:17:56 pm
Hi Petr,

Just like human players, my AI tracks whether it has shot at a cell or not with the hits(x, y) array.

If the idiot player wants to shoot at the same place over and over, let him! The board is tracking his shots so not needed to tell him he being wasteful of shots.

I don't understand your question of graphics used, allot of image files are used, just check out the folder loaded with them!
(Sorry, I am in a bit of a rush...)

Append: OK I think you are asking if these image files were created by the code? No, Johnno has been my supplier of image and sound files. We've collaborated on a number of projects. I did create code to generate the fire directly under the Black Battleship in the splash screen at the beginning.

Oh also, the squares that the Player has already tried (and missed) are signaled on the game board by a lighter, whiter shade water tile. Petr, maybe you did not notice the lighter shade? I myself could not see the difference in regular water tile and a water tile signaling a miss unless the tiles were side by side. In summary, the Player's misses are signaled to the Player, even if they are not checked in code.


Hi all,

The games are running much fiercer than I expected. To count how long a game takes by how much ocean remains undisturbed by hits or misses, I added this code to 5-AI at the end of the game loop:
Code: QB64: [Select]
  1. ahits = 0
  2. amisses = 0
  3. aocean = 0
  4. FOR y = 0 TO 9
  5.     FOR x = 0 TO 9
  6.         IF hits(x, y) > 0 THEN
  7.             ahits = ahits + 1
  8.         ELSEIF hits(x, y) = 0 THEN
  9.             aocean = aocean + 1
  10.         ELSE
  11.             amisses = amisses + 1
  12.         END IF
  13.     NEXT
  14. rgb 999
  15. PRINT "AI hits ="; ahits
  16. PRINT "AI misses ="; amisses
  17. PRINT "Undisturbed ocean ="; aocean
  18.  

I collected data from 25 games that I entered into this text file: 5-AI stats.txt attached. The first 14 items are my wins and the last 11 are the AI's wins.

I added up and averaged with this code:
Code: QB64: [Select]
  1. 'add stats
  2. OPEN "5-AI stats.txt" FOR INPUT AS #1
  3. FOR i = 1 TO 26
  4.     INPUT #1, fline$
  5.     IF i < 15 THEN pt = pt + VAL(fline$) ELSE at = at + VAL(fline$)
  6. PRINT "Player win average undisturbed ocean ="; pt / 14
  7. PRINT "AI win average undisturbed ocean ="; at / 11
  8. PRINT "Total average undisturbed ocean ="; (at + pt) / 25
  9.  

And the results are here in last screen shot.

56% +/- of ocean is undisturbed in game, that means on Average only 44 shots are taken before a winner is determined!!!
Title: Re: Battleship with AI
Post by: bplus on May 28, 2018, 07:41:02 pm
Hi Petr,

I have reread and thought more about your questions and comments and appended a longer reply in post above.

I hope I have answered your concerns.
Title: Re: Battleship with AI
Post by: FellippeHeitor on May 28, 2018, 08:49:05 pm
You guys seem to be on fire with this one!

I'm going to try it and see if I have any issues with sound and image as you pointed out. I'll let you know.
Title: Re: Battleship with AI
Post by: bplus on May 29, 2018, 08:56:43 am
Of course for me the latest version of Battleship 5-AI 2018-05-24 runs fine on Windows 10 (Intel CORE i5, 7th gen) laptop.
Title: Re: Battleship with AI
Post by: Petr on May 29, 2018, 12:54:51 pm
Hi BPlus. I ask, because i like very much your BMP picture that contains text BATTLESHIP. Your fire effect i like too, so i use it as VIDEO TEXTUR for text :-D Without fast _MEM functions this time:

Code: QB64: [Select]
  1. texture& = _SCREENIMAGE
  2. Fire& = _NEWIMAGE(640, 75, 256)
  3. CONST xxmax = 640
  4. CONST yymax = 75
  5. CONST Xstep = 1
  6. CONST ystep = 1
  7.  
  8. DIM SHARED f(xxmax, yymax + 2)
  9. DIM SHARED pal&(300)
  10.  
  11. FOR x = 0 TO xxmax
  12.     f(x, yymax + 1) = INT(RND * 2) * 300
  13.     f(x, yymax + 2) = 300
  14. FOR i = 1 TO 100
  15.     fr = 240 * i / 100 + 15
  16.     pal&(i) = _RGB(fr, 0, 0)
  17.     pal&(i + 100) = _RGB(255, fr, 0)
  18.     pal&(i + 200) = _RGB(255, 255, fr)
  19. SCREEN _NEWIMAGE(1024, 768, 256)
  20. F$ = ENVIRON$("SYSTEMROOT") + "\fonts\BrushSci.ttf"
  21.  
  22. Text$ = "Thank you!"
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.     FireVideo
  30.     TexturedText Fire&, Text$, 300, 384, F$, 60
  31.     _DISPLAY
  32.     _LIMIT 50
  33.  
  34. SUB FireVideo
  35.     SHARED ticker
  36.     _DEST Fire&
  37.     FOR x = 1 TO xxmax - 1 'shift fire seed a bit
  38.         r = RND
  39.         IF r < .15 THEN
  40.             f(x, yymax + 1) = f(x - 1, yymax + 1)
  41.         ELSEIF r < .3 THEN
  42.             f(x, yymax + 1) = f(x + 1, yymax + 1)
  43.         ELSEIF r < .35 THEN
  44.             f(x, yymax + 1) = INT(RND * 2) * 300
  45.         END IF
  46.     NEXT
  47.     FOR y = 0 TO yymax 'fire based literally on 4 pixels below it like cellular automata
  48.         FOR x = 1 TO xxmax - 1
  49.             f(x, y) = max((f(x - 1, y + 1) + f(x, y + 1) + f(x + 1, y + 1) + f(x - 1, y + 2)) / 4 - 5, 0)
  50.             LINE (x * Xstep, y * ystep)-STEP(Xstep, ystep), pal&(f(x, y)), BF
  51.         NEXT
  52.     NEXT
  53.     ticker = ticker + .025
  54.  
  55.  
  56.  
  57.  
  58. SUB TexturedText (texture AS LONG, text AS STRING, X AS INTEGER, Y AS INTEGER, Font AS STRING, FontSize AS INTEGER) 'FontW, FontH)
  59.     SHARED f&, v&
  60.     De = _DEST: So = _SOURCE
  61.     IF f& = 0 THEN f& = _LOADFONT(Font$, FontSize, "MONOSPACE")
  62.     IF v& = 0 THEN
  63.         v& = _NEWIMAGE(LEN(text) * _FONTWIDTH(f&) * 3, 3 * _FONTHEIGHT(f&), 256)
  64.         COLOR 15
  65.         _FONT f&, v&
  66.         _DEST v&: PRINT text$
  67.         _DEST 0
  68.     END IF
  69.  
  70.     FOR TH = 0 TO _FONTHEIGHT(f&) + 10
  71.         FOR TW = 0 TO _FONTWIDTH(f&) * LEN(text$)
  72.             _SOURCE v&
  73.  
  74.             IF POINT(TW, TH) = 15 THEN
  75.                 _SOURCE texture&: _DEST 0
  76.                 PSET (X + TW, Y + TH), POINT(TW, 32 + (TH - 12))
  77.             END IF
  78.     NEXT TW, TH
  79.     _DEST De: _SOURCE So
  80.  
  81.  
  82.  
  83. FUNCTION max (a, b)
  84.     IF a < 64 THEN a = 64 'for always visible text
  85.     IF a > b THEN max = a ELSE max = b
  86.  
  87.  
  88.  
Title: Re: Battleship with AI
Post by: bplus on May 29, 2018, 03:25:50 pm
Oh hey! very nice effect Petr!

I will study...
Title: Re: Battleship with AI
Post by: Ashish on May 29, 2018, 11:38:59 pm
@bplus
Nice Improvement with AI. Now, I'm not able to win computer. It wil be interesting to see a Computer vs Computer match.
@Petr
Nice effect!
Title: Re: Battleship with AI
Post by: bplus on May 30, 2018, 10:11:27 am
@bplus
Nice Improvement with AI. Now, I'm not able to win computer. It wil be interesting to see a Computer vs Computer match.
@Petr
Nice effect!

Hi Ashish,

Thanks for you report, I can assume the program is running fine for you. It warms my heart to know the AI can beat you, that  is impressive. 

But don't be discouraged, you are human who has capability to learn and use intuition. Learn how AI plays and use some of it's methods then it is a 50/50 chance who wins, you or it. You will edge it out because you are more flexible and learn!

PS if you think computer versus computer might be interesting, give it a shot! I think it would be boring UNLESS the programs can learn and improve from playing each other. But overall, it's just a guessing game, a matter of probability and statistics unless the computer plays a human and can pick up on the human's lack of experience with game and probability. I don't know...

A big decision with the game is deciding whether to go with mod 3 coverage or mod 2, every 2 squares or every other square. Then there is some skill in switching mod coverage according to smallest ship sunk eg if all you have left to sink is the Carrier (5 holed) you need cover the remaining uncovered ocean systematically every 5 squares! But this was discussed earlier in thread.
Title: Re: Battleship with AI
Post by: bplus on May 31, 2018, 03:58:26 pm
Well the results are in, Battleship 6 AI versus AI, the random coverage of every 2 squares clearly edges out random coverage of every other square. My instincts confirmed to go with every 2 squares to cover board faster when hunting down a ship for first hit (unless all the 3 or less length ships have been sunk.)

For 100 games in a row here is sample of results mod 2 - mod 3:
40-60
46-54
50-50 the closest they ever came!
31-69
...
I'd say 40 something versus 50 something was typical.
Title: Re: Battleship with AI
Post by: Ashish on June 01, 2018, 10:26:24 am
The result are amazing...