Krdytkyu

Found this project online and looking for some guidance. I'm in the process of developing a Battleship AI that will play against different computer difficulties.

The "barebones" part of the project is already completed. I don't need to develop the game board, create a makefile, write a tester, or anything like that. All I'm doing is creating a single AI that will play against the computer.

The playground is a 10x10 board.

There are :

• 
  3 ships of length 5
  


• 
  2 ships of length 4
  


• 
  1 ship of length 3
  

There are four different levels of difficulty (that I'm supposed to beat) :

• Beginner


• Normal Player


• Gambler


• Learning Gambling

I am unable to see the code for any of these "players". From the names of the difficulties you can guess how they play the game.

So here's the code I developed last night. Everything runs fine and smooth, but I'm only able to defeat the first two difficulties (Beginner and Normal Player). My AI gets absolutely crushed by the later two (I simulated 500 games for each and I maybe won 50 games total).

It would be great is someone could help optimize my code for me. Improving the AI obviously has something to do with the piece placement strategy, but I'm not exactly sure where to go from here. Any help would be greatly appreciated!

ourPlayer.h

#ifndef DUMBPLAYERV2_H          // Double inclusion protection

#define DUMBPLAYERV2_H



using namespace std;



#include "PlayerV2.h"

#include "Message.h"

#include "defines.h"



// DumbPlayer inherits from/extends PlayerV2



class ourPlayer: public PlayerV2 {

    public:

            ourPlayer( int boardSize );

            ~ourPlayer();

            void newRound();

            Message placeShip(int length);

            Message getMove();

            void update(Message msg);



    private:

        void initializeBoard();

        bool isLegal(Direction dir, int row, int col, int length);

        void killFunction();

        void markShip(Direction dir, int row, int col, int length);

        int dts;

        int scanRow;

        int scanCol;

        int huntRow;

        int huntCol;

            int numShipsPlaced;

        char board[MAX_BOARD_SIZE][MAX_BOARD_SIZE];

        char oppBoard[MAX_BOARD_SIZE][MAX_BOARD_SIZE];

};



#endif

ourPlayer.cpp

#include <iostream>

#include <cstdio>

#include<cstdlib>



#include "ourPlayer.h"



ourPlayer::ourPlayer( int boardSize )

    :PlayerV2(boardSize)

{

    // Could do any initialization of inter-round data structures here.

}



/**

 * @brief Destructor placeholder.

 * If your code does anything that requires cleanup when the object is

 * destroyed, do it here in the destructor.

 */

ourPlayer::~ourPlayer( ) {}



/*

 * Private internal function that initializes a MAX_BOARD_SIZE 2D array of char to water.

 */

void ourPlayer::initializeBoard() {

    for(int row=0; row<boardSize; row++) {

        for(int col=0; col<boardSize; col++) {

            this->board[row][col] = WATER;

            this->oppBoard[row][col]=WATER;

        }

    }

}



Message ourPlayer::getMove() {

    bool hunting=false;

    dts= (rand()%4)+1;



    if (scanCol==-3){

        scanCol=0;

        scanRow=0;

        huntRow=0;

        huntCol=0;

    }



    if (oppBoard[scanRow][scanCol]==HIT){

        hunting=true;

        huntRow=scanRow;

        huntCol=scanCol;

    }

    // Deal with KILL somewhere



    if (hunting){

        killFunction();

    }else {// if (!hunting)

//        while (oppBoard[scanRow][scanCol]!=WATER){

        scanCol+=3;

        if( scanCol >= boardSize ) {

            scanRow++;

            scanCol= scanRow%3;

        }

        if( scanRow >= boardSize ) {

            scanCol = 0;

            scanRow = 0;

        }

        huntRow = scanRow;

        huntCol=scanCol;

  // }

    }



    Message result( SHOT, huntRow, huntCol, "Bang", None, 1 );

    return result;

}



void ourPlayer::killFunction(){



    // Hunt north

    for (int row=huntRow-1;row>-1;row--){

        char ch=oppBoard[row][huntCol];

        if (ch==WATER){

            huntRow=row;

            return;

        }

        else if(ch==MISS||ch==KILL){

            break;

        }

        else{

            //HIT=keep going

        }

    }

    //Hunt south

    for (int row=huntRow+1;row<boardSize;row++){

        char ch=oppBoard[row][huntCol];

        if (ch==WATER){

            huntRow=row;

            return;

        }

        else if(ch==MISS||ch==KILL){

            break;

        }

        else{

            //HIT=keep going

        }

    }

    // Hunt east

    for (int col=huntCol+1;col<boardSize;col++){

        char ch=oppBoard[huntRow][col];

        if (ch==WATER){

            huntCol=col;

            return;

        }

        else if(ch==MISS||ch==KILL){

            break;

        }

        else{

            //HIT=keep going

        }

    }

    //Hunt west

    for (int col=huntCol-1;col>-1;col--){

        char ch=oppBoard[huntRow][col];

        if (ch==WATER){

            huntCol=col;

            return;

        }

        else if(ch==MISS||ch==KILL){

            break;

        }

        else{

            //HIT=keep going

        }

    }



}



void ourPlayer::newRound() {

    /* DumbPlayer is too simple to do any inter-round learning. Smarter players

     * reinitialize any round-specific data structures here.

     */

    this->scanRow = 0;

    this->scanCol = -3;

    this->numShipsPlaced = 0;



    this->initializeBoard();

}



/**

 * @brief Gets the AI's ship placement choice. This is then returned to the caller.

 * @param length The length of the ship to be placed.

 * @return Message The most important parts of the returned message are

 * the direction, row, and column values.

 *

 * The parameters returned via the message are:

 * 1. the operation: must be PLACE_SHIP

 * 2. ship top row value

 * 3. ship top col value

 * 4. a string for the ship name

 * 5. direction Horizontal/Vertical (see defines.h)

 * 6. ship length (should match the length passed to placeShip)

 */

Message ourPlayer::placeShip(int length) {

    char shipName[10];

    snprintf(shipName, sizeof shipName, "Ship%d", numShipsPlaced);



    if (numShipsPlaced==0){

        int row=boardSize-1;

        int col=boardSize-1-length;

        markShip(Horizontal,row,col,length);

        Message response(PLACE_SHIP,row,col,shipName,Horizontal,length);

        numShipsPlaced++;

        return response;

    }else{

        while(true){

            Direction dir=Direction((rand()%2)+1);

            int row;

            int col;

            if(dir==Horizontal) {

                row=(rand()%(boardSize));

                col=(rand()%(boardSize-length+1));

            } else {

                row=(rand()%(boardSize-length+1));

                col=(rand()%(boardSize));

            }

            if(isLegal(dir,row,col,length)){

                markShip(dir,row,col,length);

                Message response( PLACE_SHIP, row, col, shipName, dir, length );

                numShipsPlaced++;

                return response;

            }

        }

    }

}



void ourPlayer::markShip(Direction dir, int row, int col, int length){

    if (dir==Horizontal){

        for (int i=0;i<length;i++){

            board[row][col+i]=SHIP;

        }

    }else{

        for (int i=0;i<length;i++){

            board[row+i][col]=SHIP;

        }

    }

}



bool ourPlayer::isLegal(Direction dir,int row,int col,int length){

    if (dir==Horizontal){

        if ((col+length)>boardSize){

            return false;

        }

        for (int i=0;i<length;i++){

            if (board[row][col+i]==SHIP/*||

                board[row][col+i+1]==SHIP||

                board[row][col+i-1]==SHIP||

                board[row+1][col+i]==SHIP||

                board[row-1][col+i]==SHIP*/){

                return false;

            }

        }

        return true;

    }else{

        if ((row+length)>boardSize){

            return false;

        }

        for(int i=0;i<length;i++){

            if (board[row+i][col]==SHIP/*||

                board[row+i][col+1]==SHIP||

                board[row+i][col-1]==SHIP||

                board[row+1+i][col]==SHIP||

                board[row-1+i][col]==SHIP*/){

                return false;

            }

        }

        return true;

    }

}



/**

 * @brief Updates the AI with the results of its shots and where the opponent is shooting.

 * @param msg Message specifying what happened + row/col as appropriate.

 */

void ourPlayer::update(Message msg) {

    switch(msg.getMessageType()) {

        case HIT:

        case KILL:

        case MISS:

            oppBoard[msg.getRow()][msg.getCol()] = msg.getMessageType();

            break;

        case WIN:

            break;

        case LOSE:

            break;

        case TIE:

            break;

        case OPPONENT_SHOT:

            // TODO: get rid of the cout, but replace in your AI with code that does something

            // useful with the information about where the opponent is shooting.

            //cout << gotoRowCol(20, 30) << "DumbPl: opponent shot at "<< msg.getRow() << ", " << msg.getCol() << flush;

            break;

    }

}

EDITS

• Ships are allowed to touch both vertically and horizontally.




• Diagonal ships are not allowed




• You receive confirmation after every move. The AI will known once a ship has sunk.




• Since this is technically AI vs. AI, I have no say over where the specific ships are placed on the board.

I've already read tons of blogs online talking about similar projects. Problem is I'm a total novice at this stuff so conceptually it's hard for me to actually implement the "strategies" found online.

Here's a sample picture of the AI vs. AI action:

The final output when the simulations are complete:

Can you add some rules on ship placement? Can they touch horizontally or vertically? Can they touch diagonally? Do you get a confirmation when you have sunk a ship?

Why do you reset 'hunting' each turn? I would put this as class member.
Do you use the variable 'dts'?

I see you already implemented the parity strategy, so according to the blog, probability density function are your next best bet.
This involves calculating all possible locations for the remaining enemy ships, and calculating the probability of a present ship for each tile.
http://www.datagenetics.com/blog/december32011/