Battleship with AI

[STxAxTIC]

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. RANDOMIZE TIMER
4.  
5. DIM SHARED ocean(10, 10) AS STRING
6.  
7. FOR i = 1 TO 10
8.     FOR j = 1 TO 10
9.         IF RND > (10 - i) * (10 - j) * .05 THEN
10.             ocean(i, j) = "S"
11.         ELSE
12.             ocean(i, j) = "."
13.         END IF
14.     NEXT
15. NEXT
16.  
17. CALL printmap
18. SLEEP
19. DO
20.     CALL tryhit(1, 10, 1, 10)
21. LOOP UNTIL checkdone(1, 10, 1, 10) = 1
22. END
23.  
24. SUB tryhit (xstart, xend, ystart, yend)
25.     IF xstart < 1 THEN xstart = 1
26.     IF xend > 10 THEN xend = 10
27.     IF ystart < 1 THEN ystart = 1
28.     IF yend > 10 THEN yend = 10
29.     IF checkdone(xstart, xend, ystart, yend) = 0 THEN
30.         xguess = INT(xstart + RND * (xend - xstart + 1))
31.         yguess = INT(ystart + RND * (yend - ystart + 1))
32.         _DELAY .1
33.         SELECT CASE ocean(xguess, yguess)
34.             CASE "S"
35.                 ocean(xguess, yguess) = "H"
36.                 CALL printmap
37.                 FOR k = 1 TO 64
38.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
39.                 NEXT
40.             CASE "H"
41.                 ocean(xguess, yguess) = "H"
42.                 CALL printmap
43.                 FOR k = 1 TO 8
44.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
45.                 NEXT
46.             CASE ".", "~"
47.                 ocean(xguess, yguess) = "~"
48.                 CALL printmap
49.                 CALL tryhit(xstart, xend, ystart, yend)
50.         END SELECT
51.     END IF
52. END SUB
53.  
54. FUNCTION checkdone (xstart, xend, ystart, yend)
55.     done = 1
56.     FOR i = xstart TO xend
57.         FOR j = ystart TO yend
58.             IF ocean(i, j) = "." THEN
59.                 done = 0
60.             END IF
61.         NEXT
62.     NEXT
63.     checkdone = done
64. END FUNCTION
65.  
66. SUB printmap
67.     CLS
68.     counter1 = 0
69.     counter2 = 0
70.     counter3 = 0
71.     counter4 = 0
72.     FOR i = 1 TO 10
73.         FOR j = 1 TO 10
74.             LOCATE j * 2, i * 3
75.             PRINT ocean(i, j)
76.             IF ocean(i, j) = "." THEN counter1 = counter1 + 1
77.             IF ocean(i, j) = "~" THEN counter2 = counter2 + 1
78.             IF ocean(i, j) = "S" THEN counter3 = counter3 + 1
79.             IF ocean(i, j) = "H" THEN counter4 = counter4 + 1
80.         NEXT
81.     NEXT
82.     LOCATE 20, 60: PRINT "."; counter1
83.     LOCATE 21, 60: PRINT "~"; counter2
84.     LOCATE 22, 60: PRINT "S"; counter3
85.     LOCATE 23, 60: PRINT "H"; counter4
86.     IF counter3 = 0 THEN END
87. END SUB
88.  

[bplus]

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

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... :)

[STxAxTIC]

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. RANDOMIZE TIMER
4.  
5. DIM SHARED ocean(10, 10) AS STRING
6.  
7. FOR i = 1 TO 10
8.     FOR j = 1 TO 10
9.         IF RND > (10 - i) * (10 - j) * .05 THEN
10.             'IF i = 5 THEN
11.             ocean(i, j) = "S"
12.         ELSE
13.             ocean(i, j) = "."
14.         END IF
15.     NEXT
16. NEXT
17.  
18. CALL printmap
19. SLEEP
20. DO
21.     CALL tryhit(1, 10, 1, 10)
22. LOOP UNTIL checkdone(1, 10, 1, 10) = 1
23. END
24.  
25. SUB tryhit (xstart, xend, ystart, yend)
26.     IF xstart < 1 THEN xstart = 1
27.     IF xend > 10 THEN xend = 10
28.     IF ystart < 1 THEN ystart = 1
29.     IF yend > 10 THEN yend = 10
30.     IF checkdone(xstart, xend, ystart, yend) = 0 THEN
31.         xguess = INT(xstart + RND * (xend - xstart + 1))
32.         yguess = INT(ystart + RND * (yend - ystart + 1))
33.         _DELAY .1
34.         SELECT CASE ocean(xguess, yguess)
35.             CASE "S", "H"
36.                 ocean(xguess, yguess) = "H"
37.                 CALL printmap
38.                 FOR k = 1 TO 64
39.                     CALL tryhit(xguess - 1, xguess + 1, yguess - 1, yguess + 1)
40.                     CALL tryhit(xguess - 2, xguess + 2, yguess - 2, yguess + 2)
41.                 NEXT
42.             CASE ".", "~"
43.                 ocean(xguess, yguess) = "~"
44.                 CALL printmap
45.         END SELECT
46.     END IF
47. END SUB
48.  
49. FUNCTION checkdone (xstart, xend, ystart, yend)
50.     done = 1
51.     FOR i = xstart TO xend
52.         FOR j = ystart TO yend
53.             IF ocean(i, j) = "." THEN
54.                 done = 0
55.             END IF
56.         NEXT
57.     NEXT
58.     checkdone = done
59. END FUNCTION
60.  
61. SUB printmap
62.     CLS
63.     counter1 = 0
64.     counter2 = 0
65.     counter3 = 0
66.     counter4 = 0
67.     FOR i = 1 TO 10
68.         FOR j = 1 TO 10
69.             LOCATE j * 2, i * 3
70.             PRINT ocean(i, j)
71.             IF ocean(i, j) = "." THEN counter1 = counter1 + 1
72.             IF ocean(i, j) = "~" THEN counter2 = counter2 + 1
73.             IF ocean(i, j) = "S" THEN counter3 = counter3 + 1
74.             IF ocean(i, j) = "H" THEN counter4 = counter4 + 1
75.         NEXT
76.     NEXT
77.     LOCATE 20, 60: PRINT "."; counter1
78.     LOCATE 21, 60: PRINT "~"; counter2
79.     LOCATE 22, 60: PRINT "S"; counter3
80.     LOCATE 23, 60: PRINT "H"; counter4
81.     IF counter3 = 0 THEN END
82. END SUB
83.  

[bplus]

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.

[Petr]

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?

[bplus]

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. NEXT
15. rgb 999
16. PRINT "AI hits ="; ahits
17. PRINT "AI misses ="; amisses
18. PRINT "Undisturbed ocean ="; aocean
19.  

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. NEXT
7. CLOSE #1
8. PRINT "Player win average undisturbed ocean ="; pt / 14
9. PRINT "AI win average undisturbed ocean ="; at / 11
10. PRINT "Total average undisturbed ocean ="; (at + pt) / 25
11.  

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!!!

[bplus]

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.

[FellippeHeitor]

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.

[bplus]

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.

[Petr]

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

[bplus]

Oh hey! very nice effect Petr!

I will study...

[Ashish]

@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!

[bplus]

@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.

[bplus]

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.

[Ashish]

The result are amazing...