Battleship AI

Question

hondros 25 Junior Poster

16 Years Ago

Okay, so I am creating a battleship game, I posted a thread here earlier to figure out how to place the ships, but know I'm back, because I am curious as to how I should program the AI for it. Here's my base code now, and I'll explain how the board is used.

# import needed modules
import random

# _ Shows a spot not fired at yet
# + Shows your ship placement
# X Shows a hit ship
# O Shows a miss
# 

# These are the boards
# This is the board the user uses for their ships,
# and the computer hits this board, so only one is needed
user_board = []
# This is the board the computer puts their ships on,
# and is not shown to the user
comp_board = []
# This board is empty at first, and the user sees it
comp_boardu = []
for row in range(10):
    user_board.append(['_']*10)
    comp_board.append(['_']*10)
    comp_boardu.append(['_']*10)

# This is the format of the board
# Don't ask why the variable is called comp_board
# It's a long story of experimenting, I can change it,
# but it'd be too time consuming
def show(comp_board):
    print """_____________________________________________
|===|_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|
|_A_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|""" %(comp_board[0][0], comp_board[0][1], comp_board[0][2], comp_board[0][3], comp_board[0][4], comp_board[0][5], comp_board[0][6], comp_board[0][7], comp_board[0][8], comp_board[0][9])
    print "|_B_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[1][0], comp_board[1][1], comp_board[1][2], comp_board[1][3], comp_board[1][4], comp_board[1][5], comp_board[1][6], comp_board[1][7], comp_board[1][8], comp_board[1][9])
    print "|_C_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[2][0], comp_board[2][1], comp_board[2][2], comp_board[2][3], comp_board[2][4], comp_board[2][5], comp_board[2][6], comp_board[2][7], comp_board[2][8], comp_board[2][9])
    print "|_D_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[3][0], comp_board[3][1], comp_board[3][2], comp_board[3][3], comp_board[3][4], comp_board[3][5], comp_board[3][6], comp_board[3][7], comp_board[3][8], comp_board[3][9])
    print "|_E_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[4][0], comp_board[4][1], comp_board[4][2], comp_board[4][3], comp_board[4][4], comp_board[4][5], comp_board[4][6], comp_board[4][7], comp_board[4][8], comp_board[4][9])
    print "|_F_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[5][0], comp_board[5][1], comp_board[5][2], comp_board[5][3], comp_board[5][4], comp_board[5][5], comp_board[5][6], comp_board[5][7], comp_board[5][8], comp_board[5][9])
    print "|_G_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[6][0], comp_board[6][1], comp_board[6][2], comp_board[6][3], comp_board[6][4], comp_board[6][5], comp_board[6][6], comp_board[6][7], comp_board[6][8], comp_board[6][9])
    print "|_H_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[7][0], comp_board[7][1], comp_board[7][2], comp_board[7][3], comp_board[7][4], comp_board[7][5], comp_board[7][6], comp_board[7][7], comp_board[7][8], comp_board[7][9])
    print "|_I_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[8][0], comp_board[8][1], comp_board[8][2], comp_board[8][3], comp_board[8][4], comp_board[8][5], comp_board[8][6], comp_board[8][7], comp_board[8][8], comp_board[8][9])
    print "|_J_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[9][0], comp_board[9][1], comp_board[9][2], comp_board[9][3], comp_board[9][4], comp_board[9][5], comp_board[9][6], comp_board[9][7], comp_board[9][8], comp_board[9][9])

# The boats of battleship
patrol = ["Patrol Boat", 2]
sub = ["Submarine", 3]
destroyer = ["Destroyer", 3]
battle = ["Battleship", 4]
ac = ["Aircraft Carrier", 5]

# Attempt 2 at placing ships
# Took me so long to get it right
def comp_placement2(ship):
    d = [random.randint(0, 9), random.randint(0, 9)]
    di = random.choice(["up", "down", "left", "right"])
    a = 0
    if comp_board[d[0]][d[1]] == "+":
        a = 0
    elif comp_board[d[0]][d[1]] == "_":
        if di == "up":
            if d[0] - ship[1] < 0:
                a = 0
            elif d[0] - ship[1] >= 0:
                a = 1
                for x in range(0, ship[1]):
                    if comp_board[d[0]-x][d[1]] == "+":
                        a = 0
                if a == 1:
                    for x in range(0, ship[1]):
                        comp_board[d[0]-x][d[1]] = "+"
                        a = 1
        elif di == "down":
            try:
                trying = comp_board[d[0]+ship[1]]
                a = 1
                for x in range(0, ship[1]):
                    if comp_board[d[0]-x][d[1]] == "+":
                        a = 0
                if a == 1:
                    for x in range(0, ship[1]):
                        comp_board[d[0]+x][d[1]] = "+"
                    a = 1
            except:
                a = 0
        elif di == "left":
            if d[1] - ship[1] < 0:
                a = 0
            elif d[1] - ship[1] >= 0:
                a = 1
                for x in range(0, ship[1]):
                    if comp_board[d[0]][d[1]-x] == "+":
                        a = 0
                if a == 1:
                    for x in range(0, ship[1]):
                        comp_board[d[0]][d[1]-x] = "+"
                        a = 1
        elif di == "right":
            try:
                trying = comp_board[d[1]+ship[1]]
                a = 1
                for x in range(0, ship[1]):
                    if comp_board[d[0]][d[1]+x] == "+":
                        a = 0
                if a == 1:
                    for x in range(0, ship[1]):
                        comp_board[d[0]][d[1]+x] = "+"
                    a = 1
            except:
                a = 0
    comp_placement2.a = a

def comp_place2():
    a = 0
    while a == 0:
        comp_placement2(patrol)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(sub)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(destroyer)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(battle)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(ac)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0

# This is the AI I have so far
# Right now, it just shoots completely randomly
# This is where I would like some help,
# Any help would be appreciated, ie formatting,
# good shooting, etc.
a = [0, 0]
h = "miss"
def comp_turn_o():
    comp_turn_o.h = h
    if comp_turn_o.h == "miss":
        a = [random.randint(0, 9), random.randint(0, 9)]
        while user_board[a[0]][a[1]] == 'X' or user_board[a[0]][a[1]] == 'O':
            a = [random.randint(0, 9), random.randint(0, 9)]
        if user_board[a[0]][a[1]] == '+':
            user_board[a[0]][a[1]] = 'X'
            comp_turn_o.h = "hit"
        elif user_board[a[0]][a[1]] == '_':
            user_board[a[0]][a[1]] = 'O'
            comp_turn_o.h = "miss"
    if comp_turn_o.h == "hit":
        a = a[0]

I left out all the user input stuff, so it's shorter. Any critique on my code would be appreciated. Also, I just would like to know some good tactics for battleship, and how to go about doing it. I've been here for a few days now, and I'm at a lost, and google doesn't really seem to help me much. Either that or I'm not using the search terms right :/

python

3 Contributors
4 Replies
2K Views
2 Years Discussion Span
Latest Post 14 Years Ago Latest Post by woooee

Dani AI

Generated 10 Months Ago

Nice start, . For Battleship AIs, a simple and strong baseline is hunt/target with parity. Hunt phase fires only on cells that match a modulus pattern so you never waste shots where a remaining ship of length L cannot fit. Your X(3)X(3) idea is exactly that with step=3. Start with step = min(remaining_ship_lengths). That means step=2 at the beginning; once you sink the size-2 patrol boat, switch to step=3. When you get a hit, switch to target mode: probe the 4 neighbors; after two aligned hits, extend in that line until the ship sinks.

Here is a compact drop-in selector you can call each computer turn. It keeps state (shots taken, a queue of promising cells, and the current cluster of hits) and adapts parity based on remaining ship sizes:

import random
from collections import deque

N = 10
shots = set()
queue = deque()
cluster = []            # current contiguous-hit cluster
remaining = [5, 4, 3, 3, 2]

def next_shot():
    step = min(remaining)
    # target mode
    while queue:
        r, c = queue.popleft()
        if (r, c) not in shots:
            return (r, c)
    # hunt mode with parity
    cells = [(r, c) for r in range(N) for c in range(N)
             if (r + c) % step == 0 and (r, c) not in shots]
    if not cells:  # fallback when parity exhausted
        cells = [(r, c) for r in range(N) for c in range(N) if (r, c) not in shots]
    return random.choice(cells)

def on_feedback(r, c, result):
    shots.add((r, c))
    if result == 'hit':
        cluster.append((r, c))
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in shots:
                queue.append((nr, nc))
        _orient_and_extend()
    elif result == 'sunk':
        cluster[:] = []
        # also do: remaining.remove(size_of_sunk_ship)

def _orient_and_extend():
    if len(cluster) < 2: return
    rs, cs = zip(*cluster)
    if len(set(rs)) == 1:  # horizontal
        row, cmin, cmax = rs[0], min(cs), max(cs)
        for c in [cmin - 1, cmax + 1]:
            if 0 <= c < N and (row, c) not in shots:
                queue.appendleft((row, c))
    elif len(set(cs)) == 1:  # vertical
        col, rmin, rmax = cs[0], min(rs), max(rs)
        for r in [rmin - 1, rmax + 1]:
            if 0 <= r < N and (r, col) not in shots:
                queue.appendleft((r, col))

Notes:

’s refactor is great; follow the same idea for your AI by centralizing state and logic instead of globals like comp_turn_o.h.
For placement and bounds, do explicit range checks (0 <= r < 10) instead of try/except for IndexError.
: an index-out-of-range on printing usually means comp_board is not 10x10 or your row/col order is flipped. Print len(comp_board) and len(comp_board[0]), and log (x, y) right before indexing to confirm.

All 4 Replies

woooee 814 Nearly a Posting Maven

16 Years Ago

Replace this

def show(comp_board):
    print """_____________________________________________
|===|_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|
|_A_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|""" %(comp_board[0][0], comp_board[0][1], comp_board[0][2], comp_board[0][3], comp_board[0][4], comp_board[0][5], comp_board[0][6], comp_board[0][7], comp_board[0][8], comp_board[0][9])
    print "|_B_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[1][0], comp_board[1][1], comp_board[1][2], comp_board[1][3], comp_board[1][4], comp_board[1][5], comp_board[1][6], comp_board[1][7], comp_board[1][8], comp_board[1][9])
    print "|_C_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[2][0], comp_board[2][1], comp_board[2][2], comp_board[2][3], comp_board[2][4], comp_board[2][5], comp_board[2][6], comp_board[2][7], comp_board[2][8], comp_board[2][9])
    print "|_D_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[3][0], comp_board[3][1], comp_board[3][2], comp_board[3][3], comp_board[3][4], comp_board[3][5], comp_board[3][6], comp_board[3][7], comp_board[3][8], comp_board[3][9])
    print "|_E_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[4][0], comp_board[4][1], comp_board[4][2], comp_board[4][3], comp_board[4][4], comp_board[4][5], comp_board[4][6], comp_board[4][7], comp_board[4][8], comp_board[4][9])
    print "|_F_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[5][0], comp_board[5][1], comp_board[5][2], comp_board[5][3], comp_board[5][4], comp_board[5][5], comp_board[5][6], comp_board[5][7], comp_board[5][8], comp_board[5][9])
    print "|_G_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[6][0], comp_board[6][1], comp_board[6][2], comp_board[6][3], comp_board[6][4], comp_board[6][5], comp_board[6][6], comp_board[6][7], comp_board[6][8], comp_board[6][9])
    print "|_H_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[7][0], comp_board[7][1], comp_board[7][2], comp_board[7][3], comp_board[7][4], comp_board[7][5], comp_board[7][6], comp_board[7][7], comp_board[7][8], comp_board[7][9])
    print "|_I_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[8][0], comp_board[8][1], comp_board[8][2], comp_board[8][3], comp_board[8][4], comp_board[8][5], comp_board[8][6], comp_board[8][7], comp_board[8][8], comp_board[8][9])
    print "|_J_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|_%s_|" %(comp_board[9][0], comp_board[9][1], comp_board[9][2], comp_board[9][3], comp_board[9][4], comp_board[9][5], comp_board[9][6], comp_board[9][7], comp_board[9][8], comp_board[9][9])

with

letters = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' ]
print "_____________________________________________"
print "|===|_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|"
for x in range(0, 10):
    str_print = "|_%s_|" % (letters[x])
    for y in range(0, 10):
        str_print += "_%s_|" % (comp_board[x][y])
    print str_print

And similiarly

def comp_place2():
    a = 0
    while a == 0:
        comp_placement2(patrol)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(sub)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(destroyer)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(battle)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0
    a = 0
    while a == 0:
        comp_placement2(ac)
        if comp_placement2.a == 1:
            a = 1
        if comp_placement2.a == 0:
            a = 0 
##
##==========  replace with  =======================
def comp_place2():
    for ship in [patrol, sub, destroyer, battle, ac]:
        a = 0
        while a == 0:
            comp_placement2(ship)
            a = comp_placement2.a

As far as strategy goes, I think you want to choose squares that are some distance apart as most ships are more than one square long, so you would start at the middle column of the middle row, and then try the 1/4 position of that row, and then maybe divide by two again. Then divide the remaining rows by 2, etc. But I am not a battleship player.

I found this http://www.answerbag.com/q_view/168447 http://boardgames.lovetoknow.com/Battleship_Game http://www.wikihow.com/Win-at-Battleship

Edited 16 Years Ago by woooee because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

hondros 25 Junior Poster · Answer 1 · 2010-01-03T15:00:09+00:00

:D Thanks, that sure does shorten a lot of code. And thank you for the links, that helps me a lot. So right now I am trying to create the AI based off the X(3)X(3) pattern. any tips on how to save space for creating the list of co-ordinates? I'll think about a way first though. I won't mark this thread as solved until I get my program finished, and I'll come back in and update with how it's coming along. And I know there are plenty of battleship programs already made >>

crazy99 0 Newbie Poster · Answer 2 · 2012-03-06T05:50:55+00:00

If I run this piece of code:
letters = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' ]
print "_____________________________________________"
print "|===|_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|"
for x in range(0, 10):
str_print = "|_%s_|" % (letters[x])
for y in range(0, 10):
str_print += "_%s_|" % (comp_board[x][y])
print str_print
I get an error index out of range could you tell me what I'm doing wrong?

woooee 814 Nearly a Posting Maven · Answer 3 · 2012-03-06T06:56:06+00:00

No, because we have no idea how big comp_board is and since you did not post the entire error message, no idea if the error message is actually in the code posted. Print x and y before the statement
str_print += "_%s_|" % (comp_board[x][y])
and compare to the dimensions of comp_board.

This code works, so the print statements are O.K. when the board dimensions are correct.

comp_board = [['o' for x in range(10)] for y in range(10)]
letters = [ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' ]
print "_____________________________________________"
print "|===|_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|"
for x in range(0, 10):
    str_print = "|_%s_|" % (letters[x])
    for y in range(0, 10):
        str_print += "_%s_|" % (comp_board[x][y])
    print str_print

Battleship AI

Dani AI

Recommended Answers Collapse Answers

All 4 Replies

Recommended Answers