1 Replies - 2393 Views - Last Post: 04 December 2012 - 09:53 PM Rate Topic: -----

#1 xirurg  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 03-December 12

minimax connect 4 game algorithm not working

Posted 03 December 2012 - 02:56 AM

Hi, I am trying to write a connect 4 game by trying to improve on tic tac toe algoritm from the book. My game however does not respond to my moves in any sensible way and I am failing to see way. I have been debugging for past couple of hours and my best guess is that the error is when it is trying to set the min/max values to get the best move. I would appreciate any input.

P.S. sorry for the long code

Here is my code:

There are some functions that are not being used.

main.cpp

#include <iostream>
#include "Board.h"
#include <vector>
using namespace std;

int findBestMoveComp(Board &,int &, int &, vector<int>&);
int findBestMovePlayer(Board &,int &, int &, vector<int>&);


const int DRAW = 0;
const int COMP_WIN=5;
const int COMP_LOSS=-5;


int main()
{
   
   
    int playerMove;
    int bestMove=1;
    
    
    
    
    Board b1;
    b1.printBoard();
    
    while (!b1.boardFull())
    {
        cout<<"Please Enter the player move(1-7)";
        cin>>playerMove;
        b1.addToColumn(playerMove, 1);
        b1.printBoard();
    
        if (b1.checkForWin(4, 1))
        {
            cout<<"Player Won!";
            break;
        }
        else
        {
            vector<int> ranMoves;
            int k = 5;
            
            cout<<"Response:"<<findBestMoveComp(b1, bestMove, k, ranMoves);
            cout<<endl<<"Best Move:"<<bestMove<<endl;
            b1.addToColumn(bestMove, 2);
            b1.printBoard();
            if (b1.checkForWin(4,2))
            {
                cout<<"PC Won!";
                break;
            }
        }
 
    }
    
    
    
    
    

    
    
}


int findBestMoveComp(Board &b1,int & bestMove, int &counter, vector<int>&ranMoves)
{
    
    int i, responceValue;
    int dc;
    int value;
    int player = 2;
   
    

    
    if (b1.boardFull() || counter<=0 || b1.checkForWin(4, player))
    {
        
                
                return DRAW;
        
    }
    
    else
    {
        if (b1.checkImideateWin(2, bestMove))
        {
            
             
           return COMP_WIN;
          
        }
        else
        {
            if (b1.check3(2, bestMove))
            {
                value=3;
            }
            else
            {
            
            if (b1.check3(2, bestMove))
            {
                value=3;
            }
            else
            {
                if (b1.check2(2, bestMove))
                {
                    value=2;
                }
                
                
            
        
        else
        {
            value = COMP_LOSS;
            
            
            counter--;
            for (i = 0; i < WIDTH; i++)
            {
                if (b1.addToColumn( i, player))
                {
                    
                    responceValue = findBestMovePlayer(b1, dc, counter,ranMoves);
                    b1.removeFromColumn(i, player);
                    if (responceValue>value)
                    {
                        if(responceValue==0)
                        {
                            ranMoves.push_back(i);
                        }
                        
                        value=responceValue;
                        bestMove=i;
                    }
                }
            }
        }
        }
        }
    }
    }
    return value;

}

int findBestMovePlayer(Board &b1,int & bestMove, int& counter,  vector<int>&ranMoves)
{
    
    int i, responceValue;
    int dc;
    int value;
    int player = 1;
    
    

    
    
    if (b1.boardFull() || counter<=0 || b1.checkForWin(4, player))
    {
        
        return DRAW;
    }
    
    else
    {
        if (b1.checkImideateWin(1, bestMove))
        {
        //    b1.printBoard();
            
            return COMP_LOSS;
            
        }
        else
        {
            if (b1.check3(1, bestMove))
            {
                value=-3;
            }
            else
            {
            
            if (b1.check3(1, bestMove))
            {
                value=-3;
            }
            else
            {
                if (b1.check2(1, bestMove))
                {
                    value=-2;
                }

            
           
                else
    
                {

                    value = COMP_WIN;
                    counter--;
                    for (i = 0; i < WIDTH; i++)
                    {
                if (b1.addToColumn( i, player))
                {
                    responceValue = findBestMoveComp(b1, dc, counter,ranMoves);
                    b1.removeFromColumn(i, player);
                    if (responceValue< value)
                    {
                        value=responceValue;
                        bestMove=i;
                    }
                }
            }
            }
            }
        }
        }
    }
   
    return value;
    
    
}



Board.h


#ifndef __hw6__Board__
#define __hw6__Board__

#include <iostream>
using namespace std;

 
const int WIDTH=7;
const int DEPTH=6;

class Board
{

    
private:
    int arrBoard[DEPTH][WIDTH];
    int depth;
    
public:
    Board();
    void printBoard();
    bool addToColumn(int,int);
    bool removeFromColumn(int,int);
    void tryBoard();
    bool checkForWin(int,int);
    bool checkVerticalWin(int,int);
    bool checkImideateWin(int,int&);
    bool checkHorizontalWin(int,int);
    int evaluateBoard(int,int&);
    bool boardFull();
    bool check2(int,int&);
    bool check3(int,int&);
    bool check4(int,int&);
   
    bool checkNextHorizontal(int,int,int);
    bool checkNextVertical(int,int,int);
    bool checkNext(int,int,int);
    
    int checkVerticalCount(int);
    int checkHorizontalCount(int);



};





#endif /* defined(__hw6__Board__) */






Board.cpp


#include "Board.h"

Board::Board() 
{
    
    for (int i=0; i<DEPTH; i++)
    {
        
        for (int j=0; j<WIDTH; j++)
        {
            arrBoard[i][j]=0;
        }
    }
    
}

bool Board::addToColumn(int column, int player)
{
    
    for (int i = (DEPTH-1); i >= 0 ; i--)
    {
    
        
        if( arrBoard[i][column]==0)
        {
         arrBoard[i][column]=player;
      
            return true;
        
        }
    }
  
    return false;
        
}

bool Board::removeFromColumn(int column, int player)
{
    for (int i = 0; i < DEPTH ; i++)
    {
        if( arrBoard[i][column]==player)
        {
            arrBoard[i][column]=0;
            
            return true;
            
        }
    }
    
    return false;
}


void Board::printBoard()
{
    for (int i=0; i<DEPTH; i++)
    {
        
        for (int j=0; j<WIDTH; j++)
        {
            cout<<arrBoard[i][j];
        }
        cout<<endl;
    }
    
    cout<<"-----------------------------"<<endl;;

}


bool Board::checkForWin(int i,int player)
{
    

    
    if(checkVerticalWin(i, player) || checkHorizontalWin(i, player))
    {
        
  
        return true;
    }
    
    else
    {
  
        return false;
 
    }
    
}

bool Board::checkVerticalWin(int counterLimit, int player)
{
    
    
    for (int j = 0; j<WIDTH; j++)
    {
      int counter=0; 
    for (int i = 0; i < DEPTH; i++)
    {
        if (arrBoard[i][j]==player)
        {
            counter++;
        } else
        {
            counter=0;
        }
        
        if (counter==counterLimit)
        {
           
            return true;
        }
        
    }
    }
    return false;
}

bool Board::checkHorizontalWin(int counterLimit, int player)
{
    
    
    
    for (int i = 0; i < DEPTH; i++)
    {
        int counter=0;
        for (int j = 0; j < WIDTH; j++)
            {
                if (arrBoard[i][j]==player)
                {
                    counter++;
                }
                else
                {
                    counter=0;
                }
           
                if (counter==counterLimit)
                {
                    
                    return true;
                }

            }
        
    }

    return false;
}



bool Board::checkImideateWin(int player, int&bestMove)
{
    for (int i=0; i<WIDTH; i++)
    {
        if(addToColumn(i, player))
        {
        
        
            
        if (checkForWin(4, player))
        {
            bestMove=i;
            removeFromColumn(i, player);
            return true;
        }
            removeFromColumn(i, player);
        }
        
    }
    return false;
}




bool Board::boardFull()
{
    for (int i = 0; i < WIDTH; i++)
    {
        if (arrBoard[0][i]==0)
        {
            return false;
        }
    }
    
    
    return true;
    
}


void Board::tryBoard()
{
    arrBoard[0][0]=1;
    arrBoard[1][0]=1;
    arrBoard[0][1]=1;
    printBoard();
}

int Board::evaluateBoard(int player, int&bestMove)
{
    int counter1,counter2;
    
    for (int ind=0; ind<WIDTH; ind++)
    {
        if(addToColumn(ind, player))
        {
    
        counter1=0;
        counter2=0;
        bool flag=true;
        
        for (int i = 0; i < DEPTH; i++)
        {
            if (arrBoard[i][ind]==player)
            {
                counter1++;
                flag=true;
            }
            else
            {
                if (player==1)
                {
                    if (arrBoard[i][ind]==2)
                    {
                        counter1=0;
                    }
                }
                if (player==2)
                {
                    if (arrBoard[i][ind]==1)
                    {
                        counter1=0;
                    }
                }
             }
            
            
            for (int j = 0; j < WIDTH; j++)
            {
                if (arrBoard[i][j]==player)
                {
                    counter2++;
                }
                else
                {
                    if (player==1)
                    {
                        if (arrBoard[i][j]==2)
                        {
                            counter2=0;
                        }
                    }
                    if (player==2)
                    {
                        if (arrBoard[i][j]==1)
                        {
                            counter2=0;
                        }
                    }
                }
            }

            
        }
        
    }
            cout<<"vert:"<<counter1<<endl;
            cout<<"hor:"<<counter2<<endl;
        
        
            int counter=((counter1-counter2)>0)?counter1:counter2;
            
            int sign=1;
            if (player==2)
            {
                 sign=-1;
            }
            
            removeFromColumn(ind, player);
            
                switch (counter)
            {
                    case 2:
                        
                        bestMove=ind;
                        return 2*sign;
                        break;
                        
                    case 3:
                        bestMove=ind;
                        

                        return 3*sign;
                        break;

                        
                    default:
                        break;
                
            }
        
    }
    return 0;
}


bool Board::check2(int player, int& bestMove)
{
for (int i=0; i<WIDTH; i++)
{
    if(addToColumn(i, player))
    {
        
        
        
        if (checkNext(2, i, player))
        {
            bestMove=i;
            removeFromColumn(i, player);
            return true;
        }
        removeFromColumn(i, player);
    }
    
}
return false;
}

bool Board::check3(int player, int& bestMove)
{
    for (int i=0; i<WIDTH; i++)
    {
        if(addToColumn(i, player))
        {
            
            
            
            if (checkNext(3, i, player))
            {
                bestMove=i;
                removeFromColumn(i, player);
                return true;
            }
            removeFromColumn(i, player);
        }
        
    }
    return false;
}

bool Board::check4(int player, int& bestMove)
{
    for (int i=0; i<WIDTH; i++)
    {
        if(addToColumn(i, player))
        {
            
            
            
            if (checkNext(4, i, player))
            {
                bestMove=i;
                removeFromColumn(i, player);
                return true;
            }
            removeFromColumn(i, player);
        }
        
    }
    return false;
}


bool Board::checkNextVertical(int size, int column, int player1)
{
    int counter=0;
    int player2;
    
    if (player1==1)
    {
        player2=2;
    }
    else
        player2=1;
    
    for (int i=0 ; i<DEPTH; i++)
    {
        if (arrBoard[i][column]==player1)
        {
            counter++;
        }
        
        if (arrBoard[i][column]==player2)
        {
            return false;
        }
        if (counter==size)
        {
            return true;
        }
        
    
   
    }
    return false;
}

bool Board::checkNextHorizontal(int size, int column, int player1)
{
    int counter=0;
    int player2;
    
    if (player1==1)
    {
        player2=2;
    }
    else
        player2=1;
    
    for (int i=0 ; i<DEPTH; i++)
    {
        if (arrBoard[i][column]==player1)
        {
            
            for (int j = 0; j<WIDTH; j++)
            {
                if (arrBoard[i][j]==player1)
                {
                    counter++;
                }
               
                if (arrBoard[i][j]!=player1)
                {
                    counter=0;
                }
                if (counter==size)
                {
                    return true;
                }
               
           
            }
        }
}
    return false;
    
}

bool Board::checkNext(int size, int column, int player)
{
    if (checkNextHorizontal(size, column, player))
    {
        printBoard();
        return true;
    }
    
    if (checkNextVertical(size, column, player))
    {
        printBoard();
        return true;
    }
    
    return false;
}





Is This A Good Question/Topic? 0
  • +

Replies To: minimax connect 4 game algorithm not working

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1396
  • View blog
  • Posts: 4,872
  • Joined: 19-February 09

Re: minimax connect 4 game algorithm not working

Posted 04 December 2012 - 09:53 PM

Hi, 1 to 7 is entered but the array subscript are 0 - 6.

030        cout<<"Please Enter the player move(1-7)";
031        cin>>playerMove;
032        b1.addToColumn(playerMove, 1);


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1