Battleships “AI” function
logic/presentation

You are mixing presentation and business logic. Both when signalling the AI won, as with the board. 
Do you want to look through your whole code if you decide that "_" s a better representation for clear sea than "O", or you want it in another colour than white?

Tile

As far as I remember correctly, a tile on a battleships board has a few states: (clear sea, vessel, shot but no hit, hit vessel), where clear sea and vessel have the same representation to the opponent. So instead of using a string to represent this state, better would be to use an enum

from enum import Enum

class Tile(Enum):
    CLEAR = "CLEAR"
    VESSEL = "VESSEL"
    SHOT = "SHOT"
    HIT = "HIT"


Board

I assume your board at this moment is just a list of lists of strings. It is worth it to make a slightly smarter board

class Board:
    def __init__(self, width=10, height=10):
        self.width = width
        self.height = height
        self._board = [[Tile.CLEAR] * width for _ in range(height)]


is used to create an empty board

By overloading __getitem__ and __setitem__, you can make accessing the board a lot more intuitive:

def _exists(self, x, y):
    return 0 &lt; x &lt;= self.height and 0 &lt; y &lt;= self.width

def __getitem__(self, coord):
    x, y = coord
    if not self._exists(x, y):
        raise IndexError
    return self._board[x-1][y-1]

def __setitem__(self, coord, state):
    x, y = coord
    if not self._exists(x, y):
        raise IndexError
    self._board[x-1][y-1] = state


now you can do stuff like

b = Board()
b[2, 3]



Tile.Clear



b[2, 3] = Tile.Vessel
b[2, 3]



Tile.Vessel



This way, you don't bother the user directly with the 0-indexed list of lists in a 1-indexed environment. You can even work with row names A to J if you want with only a slight adaptation to those 2 methods.

Then you can add a ship like this:

def add_ship(self, length, x, y, orientation='horizontal'):
    directions = {
        'horizontal': (1, 0),
        'vertical': (0, 1),
    }
    dx, dy = directions[orientation]
    coordinates = [
        (x + i * dx, y + i *dy)
        for i in range(length)
    ]
    try:
        if any(self[x, y] != Tile.CLEAR for x, y in coordinates):
            raise ValueError("No room for this ship")
    except IndexError: # over the edge
        raise ValueError("No room for this ship")
    for x, y in coordinates:
        self._board[x, y] = Tile.VESSEL


In your implementation of the AI, after a hit, you have the AI check all the neighbours. This can be simplified by implementing a neighbours function on the Board

def already_shot(self, x, y):
    return self[x, y] in {Tile.SHOT, Tile.HIT}

def neighbours(self, x, y):
    coordinates = ((x-1, y), (x+1, y), (x, y-1), (x, y+1))
    for x, y in coordinates:
        try:
            yield (x, y), self.already_shot(x, y)
        except IndexError:
            pass


Same goes for the actual shooting itself:

def shoot(self, x, y):
    if self.already_shot(x, y):
        raise ValueError("Already targeted this square")

    if self[x, y] == Tile.VESSEL:
        self[x, y] = Tile.HIT
        return True
    self[x, y] = Tile.SHOT
    return False 


You will need to implement a method to check whether all ships are sunk to determine whether someone has won. This method belongs to the Board, instead of on the AI method

Testing

using a class like this to keep track of the state of the board allows you to test parts of your program piece-meal. You can write a test suite so test the placing of the ships, the shooting, etc.

Turns

Where do turns show up in this? As far as I understand this, the AI keeps shooting as long as it can hit. I would expect the AI to be implemented as a class, which remembers what it has already shot etcetera, and which gets queried for a coordinate to aim at by the Game

Random shooting

If the minimum length of a ship is 2, you only need to target half of the field in while randomly looking for a ship, so only those where (x + y) % 2 is either 1 or 0, depending on where you start

AI class

This is a first shot at it. The _last_hit can use some improvement, and using a collections.deque or even a set here seems more logical than using a single value. But it shows how different methods can be used for defined beahviour

class AI:
    def __init__(self, opponent_board):
        self._board = opponent_board
        self._last_hit = None

    def random_shot(self):
        while True:
            x = random.randint(1, self._board.height)
            y = random.randint(1, self._board.width)
            if (x + y) % 2 == 0:
                continue
            try:
                hit = self._board.shoot(x, y)
                self.mark_hit(x, y, hit)
                return hit
            except ValueError:
                continue

    def mark_hit(self, x, y, hit):
        if hit:
            self._last_hit = x, y
        else:
            self._last_hit = None

    def next_turn(self):
        if self._last_hit is None:
            return self.random_shot()
        x, y = self._last_hit
        if self._board[x, y] == Tile.HIT:
            for x_, y_ in self._board.neighbours(x, y):
                try:
                    hit = self._board.shoot(x, y)
                    self.mark_hit(x, y, hit)
                    return hit
                except ValueError:
                    pass
            self._last_hit = None

        # No adjacent tiles to aim at if this got through here
        return self.random_shot()