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: [Select]

The object of the game is to sink all the Computer's ships before it sinks all yours.

Both the Player and the Computer are given 5 ships to lay out on a 10x10 grid.

The ships are a straight line of squares (2 to 5 squares) forming a long rectangle.
The ships are laid vertically or horizontally on the 10x10 cell grid without overlap.
Each square must be hit by the opponent in order to sink the ship.

The 5 ships are:
Carrier    - 5 squares to hit
Battleship - 4 squares to hit
Cruiser    - 3 squares to hit
Submarine  - 3 squares to hit
Destroyer  - 2 squares to hit

The game is started by each opponent laying out their ships secretly to the other.
You the Player must setup your ships on the right board.
They are setup in same order I listed above.

So the first ship to set up will be the Carrier that is 5 squares long.
First you will be prompted whether you want to lay it out horizontally or vertically, h or v ?

Then if horizontally is chosen, you click the cell where you want the left most square of the ship to go.
Like wise if vertical v was chosen, you click the board cell where you want the top most square to go.

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.
(Of course, the first ship can't overlap another but every other ship has that potential.)
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...

When you get all 5 of your ships laid out on the 10x10 grid on the left, the shooting match begins!

You will be prompted to click a cell on the left 10x10 board to guess where a Computer's ship might be.
If you hit a square on one of the Computers ships a red dot = hit appears at that cell.
If you miss all the Computers ships, a white dot will appear = miss

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.

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.
So click above, below, left or right of the hit = red dot.
A 2nd hit will tell you if the ship is laid out horizontally or vertically.
A 2nd hit would actually sink a Destroyer because it is only 2 squares long.

So you scout around the 10x10 board making random shots (or systematically cover the board with shots)
until you find a ship, sink it and go hunting for the next ship to sink until you get all 5.

Meanwhile the Computer is doing the same thing, so which ever opponent sinks all the ships first, wins!

Oh a caveat!
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).
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
you might have more hits in the same area than how many it took to sink the ship.

https://en.wikipedia.org/wiki/Battleship_game


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: [Select]

RANDOMIZE TIMER
CONST gsq = 40
CONST gox = 200
CONST goy = 100
CONST nsq = 10
CONST n1 = nsq - 1
CONST xmax = 800
CONST ymax = 600
DIM SHARED rndList(n1)

main& = _NEWIMAGE(xmax, ymax, 32)
SCREEN main&
_SCREENMOVE 360, 60


drawGrid gox, goy, gsq, nsq
FOR modulus = 5 TO 2 STEP -1
    c$ = LTRIM$(STR$(modulus))
    COLOR RGB(c$ + c$ + c$)

    FOR y = 0 TO n1
        offset = y MOD modulus
        maxM = INT((n1 - offset) / modulus)
        getRndChoice y, modulus
        FOR xindex = 0 TO maxM
            col = rndList(xindex)
            LINE (gox + col * gsq + 3 * (7 - modulus), goy + y * gsq + 3 * (7 - modulus))-STEP(gsq - 6 * (7 - modulus), gsq - 6 * (7 - modulus)), , BF
            '_DELAY 1
        NEXT
    NEXT
    _DELAY 2
NEXT

SUB getRndChoice (rc, modulus)
    offset = rc MOD modulus
    maxM = INT((n1 - offset) / modulus)
    FOR i = 0 TO n1
        rndList(i) = i
    NEXT
    FOR i = 0 TO maxM
        n = offset + i * modulus
        SWAP rndList(i), rndList(n)
    NEXT
    FOR i = maxM TO 1 STEP -1
        r = INT((i + 1) * RND)
        SWAP rndList(i), rndList(r)
    NEXT
    FOR i = maxM + 1 TO n1
        r = INT((n1 - maxM) * RND) + maxM + 1
        SWAP rndList(i), rndList(r)
    NEXT
END SUB

SUB drawGrid (x, y, sq, n)
    d = sq * n
    FOR i = 0 TO n
        LINE (x + sq * i, y)-(x + sq * i, y + d)
        LINE (x, y + sq * i)-(x + d, y + sq * i)
    NEXT
END SUB

FUNCTION RGB& (s3$) ' New Color System 1000 colors with 3 digits!!!!!!!!!!!!!!!!
    l = LEN(s3$)
    IF l THEN r = 28 * VAL(MID$(s3$, 1, 1)) + 3
    IF l >= 2 THEN g = 28 * VAL(MID$(s3$, 2, 1)) + 3
    IF l >= 3 THEN b = 28 * VAL(MID$(s3$, 3, 1)) + 3
    RGB& = _RGB32(r, g, b)
END FUNCTION


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: [Select]

_TITLE "m3 34 m2.bas 2018-05-15,  press any key to quit..."

'in 34 shots (m = 3) I should hit all the ships length 3 and up
'and if I haven't hit destroyer yet shift to every other square m = 2

RANDOMIZE TIMER
CONST gsq = 40
CONST gox = 200
CONST goy = 100
CONST nsq = 10
CONST n1 = nsq - 1
CONST xmax = 800
CONST ymax = 600
DIM SHARED rndList(n1)
DIM hits(n1, n1)
main& = _NEWIMAGE(xmax, ymax, 32)
SCREEN main&
_SCREENMOVE 360, 60

WHILE LEN(k$) = 0
    CLS
    ERASE hits
    drawGrid gox, goy, gsq, nsq
    shotCnt = 0
    Sunk = 0
    dx = rand(0, n1 - 1)
    dx2 = dx + 1
    dy = rand(0, n1)

    FOR i = 1 TO 10
        IF i MOD 2 THEN COLOR RGB("900") ELSE COLOR RGB("999")
        LINE (gox + dx * gsq + 2 * i, goy + dy * gsq + 2 * i)-STEP(2 * gsq - 4 * i, gsq - 4 * i), , BF
    NEXT
    WHILE LEN(k$) = 0
        k$ = INKEY$
        y = y + 1
        IF y = nsq THEN y = 0

        IF shotCnt < 34 THEN
            COLOR RGB("009")
            modulus = 3
            offset = y MOD modulus
            maxM = INT((n1 - offset) / modulus)
        ELSE
            IF Sunk = 0 THEN modulus = 2: COLOR RGB("990") ELSE modulus = 3: COLOR RGB("099")
            maxM = n1
        END IF

        xindex = 0
        getRndChoice y, modulus
        testx = rndList(xindex)
        shoot = 1
        WHILE hits(testx, y) <> 0
            xindex = xindex + 1
            IF xindex > maxM THEN shoot = 0: EXIT WHILE
            testx = rndList(xindex)
        WEND
        IF shoot <> 0 THEN
            col = testx
            LINE (gox + col * gsq + 3 * (7 - modulus), goy + y * gsq + 3 * (7 - modulus))-STEP(gsq - 6 * (7 - modulus), gsq - 6 * (7 - modulus)), , BF
            hits(col, y) = 1
            shotCnt = shotCnt + 1
            IF Sunk = 0 THEN
                IF (col = dx OR col = dx2) AND y = dy THEN Sunk = 1: LOCATE 1, 1: PRINT "Destroyer Hit! in"; STR$(shotCnt); " shots."
            END IF
            IF Sunk THEN _DELAY .01 ELSE _DELAY .25
        END IF
        IF shotCnt >= 100 THEN _DELAY 5: EXIT WHILE
    WEND
WEND
SUB getRndChoice (rc, modulus)
    offset = rc MOD modulus
    maxM = INT((n1 - offset) / modulus)
    FOR i = 0 TO n1
        rndList(i) = i
    NEXT
    FOR i = 0 TO maxM
        n = offset + i * modulus
        SWAP rndList(i), rndList(n)
    NEXT
    FOR i = maxM TO 1 STEP -1
        r = INT((i + 1) * RND)
        SWAP rndList(i), rndList(r)
    NEXT
    FOR i = maxM + 1 TO n1
        r = INT((n1 - maxM) * RND) + maxM + 1
        SWAP rndList(i), rndList(r)
    NEXT
END SUB

SUB drawGrid (x, y, sq, n)
    d = sq * n
    FOR i = 0 TO n
        LINE (x + sq * i, y)-(x + sq * i, y + d)
        LINE (x, y + sq * i)-(x + d, y + sq * i)
    NEXT
END SUB

FUNCTION RGB& (s3$) ' New Color System 1000 colors with 3 digits!!!!!!!!!!!!!!!!
    l = LEN(s3$)
    IF l THEN r = 28 * VAL(MID$(s3$, 1, 1)) + 3
    IF l >= 2 THEN g = 28 * VAL(MID$(s3$, 2, 1)) + 3
    IF l >= 3 THEN b = 28 * VAL(MID$(s3$, 3, 1)) + 3
    RGB& = _RGB32(r, g, b)
END FUNCTION

FUNCTION rand% (lo%, hi%)
    rand% = INT(RND * (hi% - lo% + 1)) + lo%
END FUNCTION


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: [Select]

_TITLE "shoot test,  press any to quit..."

'first get a function to return ture/false to shoot spot x, y if it is part of coverage or not
'DONE and what a cool function it is too!!!

'2018-05-18 It's working!!! time to test in real app

RANDOMIZE TIMER
CONST gsq = 40
CONST gox = 200
CONST goy = 100
CONST sqPerSide = 10
CONST n1 = sqPerSide - 1
CONST xmax = 800
CONST ymax = 600
DIM SHARED sunk, row, col, lastm, colA, bump
DIM SHARED hits(n1, n1)
main& = _NEWIMAGE(xmax, ymax, 32)
SCREEN main&
_SCREENMOVE 360, 60

k$ = ""
restart:
IF LEN(k$) THEN END
CLS
shotCnt = 0: sunk = 0
ERASE hits
colA = -1 '<<<<<<<<<<<<<<< don't forget to signal start!
'draw grid
rgb 999
drawGrid gox, goy, gsq, sqPerSide

''destroyer target
dx = rand(0, n1 - 1)
dx2 = dx + 1
dy = rand(0, n1)
'draw the Destroyer
FOR i = 1 TO 10
    IF i MOD 2 THEN rgb 900 ELSE rgb 999
    LINE (gox + dx * gsq + 2 * i, goy + dy * gsq + 2 * i)-STEP(2 * gsq - 4 * i, gsq - 4 * i), , BF
NEXT

'start shooting
WHILE LEN(k$) = 0
    k$ = INKEY$
    shoot sx, sy

    'accounting
    hits(sx, sy) = 1
    shotCnt = shotCnt + 1

    'show shot
    IF lastm = 2 THEN rgb 990 ELSE rgb 9

    LINE (gox + sx * gsq, goy + sy * gsq)-STEP(gsq, gsq), , BF

    'hit target first time?
    IF sunk = 0 THEN
        IF (sx = dx OR sx = dx2) AND sy = dy THEN
            sunk = 1: rgb 999: LOCATE 1, 1: PRINT "Destroyer Hit! in"; STR$(shotCnt); " shots."
        END IF
        _DELAY .02
    ELSE
        _DELAY .1
    END IF

    IF shotCnt = 100 THEN EXIT WHILE
WEND
GOTO restart

'first test cover  COMMENT OUT ABOVE CODE AND UNCOMMENT following for cool graphic!
'm = 3
'WHILE 1
'    FOR bump = 0 TO m - 1
'        CLS
'        FOR y = 0 TO n1
'            FOR x = 0 TO n1
'                FOR mm = m TO 2 STEP -1
'                    SELECT CASE mm
'                        CASE 8: rgb 9
'                        CASE 7: rgb 90
'                        CASE 6: rgb 900
'                        CASE 5: rgb 99
'                        CASE 4: rgb 990
'                        CASE 3: rgb 909
'                        CASE 2: rgb 999
'                    END SELECT
'                    IF cover(mm, bump, x, y) THEN
'                        LINE (gox + x * gsq + 1, goy + y * gsq + 1)-STEP(gsq - 2, gsq - 2), , BF
'                    END IF
'                NEXT
'            NEXT
'        NEXT
'        _DISPLAY
'        _LIMIT 1
'    NEXT
'WEND

SUB drawGrid (x, y, sq, n)
    d = sq * n
    FOR i = 0 TO n
        LINE (x + sq * i, y)-(x + sq * i, y + d)
        LINE (x, y + sq * i)-(x + d, y + sq * i)
    NEXT
END SUB

SUB rgb (n) ' New (even less typing!) New Color System 1000 colors with up to 3 digits
    s3$ = RIGHT$("000" + LTRIM$(STR$(n)), 3)
    r = VAL(MID$(s3$, 1, 1)): IF r THEN r = 28 * r + 3
    g = VAL(MID$(s3$, 2, 1)): IF g THEN g = 28 * g + 3
    b = VAL(MID$(s3$, 3, 1)): IF b THEN b = 28 * b + 3
    COLOR _RGB32(r, g, b)
END SUB

FUNCTION rand% (lo%, hi%)
    rand% = INT(RND * (hi% - lo% + 1)) + lo%
END FUNCTION

SUB shoot (col, row) 'col, row aren't inputs so mush as outputs like a double function return wo input parameters

    'i = nShips
    'WHILE shipSunk(i) 'find smallest ship not sunk
    '    i = i - 1
    'WEND
    'SELECT CASE i 'm for modulus, d for direction to run a check from
    '    CASE nShips: m = 2 'still have destroyer
    '    CASE nShips - 1: m = 3 'still have sub
    '    CASE nShips - 2: m = 3 'still have cruiser
    '    CASE nShips - 3: m = 4 'still have battleship
    '    CASE nShips - 4: m = 5 'still have carrier
    '    CASE ELSE: TxtBx "990", "m", "Aren't all the Player's ships sunk?": m = 7
    'END SELECT
    IF lastm = 7 THEN EXIT SUB
    IF sunk THEN m = 3 ELSE m = 2
    'IF m <> lastm THEN
    lastm = m 'lastm  is solely needed for coloring in main
    bc = 0 'if bc is reset to 0 each time don't need it shared
    'END IF

    IF colA = -1 THEN 'col the Attact starts from notice it is random so player can't anticipate
        colA = rand%(0, n1): col = colA: row = rand(0, n1): bump = rand(0, m - 1): bc = 0
    END IF

    'm 7 is just in case some error occurs have fall back
    IF m <> 7 THEN

        WHILE bc < m
            cc = 1
            WHILE cc <= sqPerSide
                rc = 0
                WHILE rc <= sqPerSide 'find a space to hit if one left in this column
                    IF cover(m, bump, col, row) THEN 'are we on a place to cover board
                        IF hits(col, row) = 0 THEN EXIT SUB 'good to go!
                    END IF
                    row = (row + 1) MOD sqPerSide
                    rc = rc + 1
                WEND
                row = row - 1
                IF row < 0 THEN row = n1
                'still here means we checked all rows in col so check next col
                col = (col + 1) MOD sqPerSide
                cc = cc + 1
            WEND
            'still here ? then up the bump
            bump = (bump + 1) MOD m
            bc = bc + 1
        WEND
        m = 7 'error fall through


    END IF 'm<> 7

    'rexamine all the hits and check all holes filled around them
    'TO DO

    '  if all else fails
    IF m = 7 THEN 'just find a hole not tried yet and exit!
        lastm = 7
        LOCATE 2, 1: PRINT "AI in m=7 mode !!! bc = "; bc
        'FOR row = 0 TO n1
        '    FOR col = 0 TO n1
        '        IF hits(col, row) = 0 THEN EXIT SUB
        '    NEXT
        'NEXT
    END IF
END SUB '  128 lines to take a random shot!!!!

'using a modulus m coverage with a bump so that opponent can't predict where
'the hardest place to plant the Detroyer will be
FUNCTION cover (m, bump, c, r)
    bm = bump MOD m 'make sure bump is in modulus
    cm = (c + bm) MOD m
    rm = r MOD m
    IF rm = cm THEN cover = -1 ELSE cover = 0
END FUNCTION

'turns out I did not need this but it should be noted:
' the cnt is different according to bump if modulus is odd
'amd maybe if nSquare is odd and modulus is even
'how many (non repeating) shots to cover a square n X n
FUNCTION coverageCnt (nSquare, modulus, bump)
    FOR y = 0 TO nSquare - 1
        FOR x = 0 TO nSquare - 1
            IF cover(modulus, bump, x, y) THEN cnt = cnt + 1
        NEXT
    NEXT
    coverageCnt = cnt
END FUNCTION


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: