Battleship with AI

[bplus]

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.

[bplus]

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.

[bplus]

And now, the original post has been modified with new zip and screen shot with the changes explained above.

[FellippeHeitor]

Fun to play, bplus! Good job once again.

[bplus]

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

[bplus]

The original post has been updated with newest source code, sound and image files as well as the New Player Instruction.txt file.

[bplus]

Battleship 5-14 Update

[FellippeHeitor]

Wow, this seems like it's come a long way! Haven't played this update yet but it sure looks good.

[bplus]

Thanks lot's of help with assets from Johnno.

Have fun!

[Ashish]

Nice work bplus! I like the game!

[bplus]

Studying systematic board coverage of "random" shots for smarter AI.

Code: QB64: [Select]

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

Sometimes studies make pretty pictures.

[bplus]

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

So how is your math or probability intuition? Would you go mod 3 or mod 2?

[bplus]

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.

[bplus]

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

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.

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.

[bplus]

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: