• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 247
  • Last Modified:

The Game of Eight Tree

0
edelossantos
Asked:
edelossantos
  • 2
  • 2
2 Solutions
 
jkrCommented:
As posted - but, please make 'pointer' Qs 20, not 500 points
0
 
edelossantosAuthor Commented:
jkr, having problems with compilation...is this because of the missing methods?  Please advise, Del.

**********************************code*********************************

# Makefile:
#        It uses the C++ Compiler with all warnings and
#        full debugging; will create a single executable called 'main'
# ---------------------------------------------------------------
# the compiler
CPP = g++
# compiler flags
CFLAGS = -L/usr/lib/cmplrs/cxx -DPOSIX_4D9 -w -g
# linker flags to link in the libraries libm.a and libtask.a
LFLAGS = -lm -ltask
#
RM = rm -f
# ----------------------------------------------------------------
# Explanation of macros:
#     $< is any dependent file which is out of file1
#     $* is the target's basename (without extension)
#     $@ is the target's fullname
#
# add suffix .cpp since it is not a default with make util
.SUFFIXES:      .cpp .o
#
# implicit rule for compilation only:
.cpp.o:
      ${CPP} -c ${CFLAGS} $<

OFILES=            main.o stack.o util.o move.o board.o

HFILES=            stack.h util.h board.h move.h

# dependencies
#
default:      main      
#
main:           $(OFILES)
            ${CPP} ${CFLAGS} ${LFLAGS} $(OFILES) -o $@

main.o:            main.cpp stack.h
stack.o:      stack.cpp stack.h
util.o:            util.cpp util.h
board.o:      board.cpp board.h
move.o:            move.cpp move.h

#
clean:
      ${RM} *.o
      ${RM} core
#
veryclean:      clean
      ${RM}  main  

****************************

#ifndef UTIL_H  
#define UTIL_H

/* type bool and  false & true are already defined in dUNIX C++
typedef int bool;
const bool false = 0;  
const bool true = 1;  */

/* this is also in /usr/include/stddef.h which is used in <stdlib.h> */
#define NULL 0L

/* some useful definitions for flag and screen operations */
#define STDSCREEN 80        
#define DOWN 0                        
#define UP   1
#define END   0
#define START 1
#define MISS -1
#define HIT   1

/* some useful error codes */
enum Error_code { success, fail, range_error, underflow, overflow, fatal,
                  not_present, duplicate_error, entry_inserted, entry_found,
                  internal_error };

/* screen functions */
void clearScreen ();                   // clears all rows of the screen
void clearTop();                       // clears top row 0 only
void clearBelowTop();                 // clears row 1 down on a vt100 screen
void goTop();                          // moves cursor to the top row 0  
void topLine(const char * text = " "  );   // displays text at row 0
void bottomLine (char * text = " "); // displays text at row 23, column 10

/* I/O functions */
void hitAnyKey ();                   // "Hit any key to continue..." prompt
void flushInput ();                    // reads 80 chars from stdin
void Warning(char *);                  /* writes message to stderr          */
void Error(char *);                    /* writes message to stderr & exits  */
bool promptYesNo(char * prompt="");    /* prompts user to enter yes no */
void EatWhiteSpace(void);              /* discards white space input        */

#endif

*****************************

#include "util.h"

#include <iostream>
#include <ctype.h>
#include <stdlib.h>

using namespace std;

 /* --------- SCREEN HANDLING FUNCTIONS -
   vertical position goes from 0 - 23
   horizontal position goes from 0 - 79 */

void clearScreen (void)
// Clear everything on screen
{
  cout << "\033[2J";           /* Clear the entire screen. */
  cout << "\033[;f";          /* Move cursor to upper left corner */
}

void clearTop()
// Goto Top-Left corner; Clear to end of line
  {cout << "\033[0;0f" << "\033[0K";}

void clearBelowTop()
// Clear everything except top row
  {cout << "\033[1;0f" << "\033[1B" << "\033[J";}

void goTop ()
// to to the Top-Left corner;
  {cout << "\033[0;0f";}

void topLine(const char str[])
// Goto top-left corner; clear to end of line; print str
  {cout << "\033[0;0f" << "\033[0K" << str;}

void bottomLine (char * str)
  // goto line 23 ; clear line 23; write text
  {cout << "\033[23;0Hf" << "\033[2K" << str;}

/* ----------------  I/O FUNCTIONS */

/* Precondition: the input buffer is empty */
void hitAnyKey ()
{
   char ch;
   bottomLine ("Hit any key to continue...");
   cin.get(ch);
   clearScreen();
}

void flushInput ()
// flush input buffer
{
   char buff[81];
   if (cin)
      cin.getline(buff,80);   // flush the input buffer of 80 characters
}

void Warning(char *message)
{
   cerr << message;
}

void Error(char *message)
{
   cerr << message;
   exit(1);
}

void EatWhiteSpace()
/* discard leading white space */
{
    char ch;
    do {
      cin.get(ch);
    }
    while(isspace(ch));

    if(ch != EOF)
      cin.putback(ch);
}

bool promptYesNo(char * c)
{
   char ch;
   cout << c << " [y|n]?";
   do {
      cin.get(ch);  
      tolower(ch);
      } while (ch != 'y' && ch != 'n');
   return (ch == 'y');
}

************************

// stack.h

#include "util.h"

#ifndef STACK_H
#define STACK_H

#include <iostream>

using namespace std;


typedef const Entry_type;

const int MAXSIZE = 100;

class Stack {

public:

    Stack();
    Error_code push(const Entry_type &);
    Error_code pop();
    Error_code top(Entry_type &) const;
    bool empty() const;
    bool full() const;
    Error_code pop_top(Entry_type &);
    void clear();
    int size() const;

private:

   int stack_top;
   Entry_type stack[MAXSIZE];

};

#endif

*****************************

// stack.cpp

#include "stack.h"

Stack::Stack()
/* Pre:  none.
   Post: -1 designates an empty stack  */
{
   stack_top = -1;
}

Error_code Stack::push( const Entry_type & item )
/* Pre:  -1 <= stack_top <= MAXSIZE -1.
   Post: overflow error_code is returned or
         item is added to stack_top of stack, stack_top points to the item and a
         success code has been returned */
{
   if ( stack_top >= MAXSIZE - 1)
      return overflow;
   else
      stack[++stack_top] = item;
   return success;
}

Error_code Stack::pop( )
/* Pre:  the top of the stack is initialized to -1 thus:
         -1 <= stack_top <= MAXSIZE -1.
   Post: error code is returned. stack_top is >= -1 */
{
   if (stack_top == -1)
      return underflow;
   else
      stack_top--;
   return success;
}


Error_code Stack::top( Entry_type &item ) const
/* Pre:  the top of the stack is initialized to -1, thus:
         -1 <= stack_top <= MAXSIZE -1.
   Post: error_code is returned. item has a value. stack_top is unchanged */
{
   if (stack_top == -1)
      return underflow;
   else
      item = stack[stack_top];
   return success;
}

bool Stack::empty() const
/* Pre:  the top of the stack is initialized to -1 thus:
         -1 <= stack_top <= MAXSIZE -1.
   Post: error_code is returned. stack_top is unchanged */
{
   if ( stack_top == -1 )
       return true;
   else
      return false;
}

bool Stack::full() const
/* Pre:  the top of the stack is initialized to -1 thus:
          -1 <= stack_top <= MAXSIZE -1.
   Post: boolean is returned. */
{
   if (stack_top == MAXSIZE - 1)
      return true;
   else
      return false;
}

Error_code Stack::pop_top(Entry_type & item)
/* Pre:  the top of the stack is initialized to -1 thus:
          -1 <= stack_top <= MAXSIZE -1.
   Post: return error_code. stack_top is decremented and is >= -1. */
{
   if ( stack_top == -1 )
      return underflow;
   else
   {
      item = stack[ stack_top-- ];
   }  
   return success;
}

void Stack::clear()
/* Pre:  the top of the stack is reinitialized to -1:
   Post: stack_top is -1 */
{
   stack_top = -1;  // a loop is not necessary
}

int Stack::size() const
/* Pre:  the top of the stack is initialized to -1 thus:
          -1 <= stack_top <= MAXSIZE -1.
   Post: a value >= 0 is returned. stack_top is unchanged. */
{
   return stack_top + 1;
}

****************************

// move.h

#include "stack.h"

#ifndef MOVE_H
#define MOVE_H


class Move {

public:

     Move();
     ~Move(){;}
     Move(int r, int c);
     int row;
     int col;

};

typedef Move Stack_entry;

#endif

********************************
// move.cpp

#include "move.h"

// Post: The move is initialized to an illegal default value.
Move::Move() {

     row = 3;
     col = 3;

}

// Post: The move is initialized to the given coordinates
Move::Move(int r, int c) {

     row = r;
     col = c;

}

***********************************

// board.h

#include "move.h"
#include "stack.h"

#include <stack>

using namespace std;

#ifndef BOARD_H
#define BOARD_H

class Board {

public:

     Board();
     ~Board(){;}
     bool done()const;
     void print() const;
     void instructions() const;
     bool better(int value, int old_value) const;
     void play(Move try_it);
     int worst_case() const;
     int evaluate() const;
     int legal_moves(Stack &moves) const;
     int look_ahead(const Board &game,int depth, Move &recommended);

private:

     int squares[3][3];
     int moves_done;
     int the_winner() const;

};

#endif
     
************************************
// board.cpp

#include "board.h"

// Post: The Board is intialized as empty.
Board::Board() {

     int i;
     int j;

     for(i = 0; i < 3; i++)
          for(j = 0; j < 3; j++)
               squares[i][j] = 0;
     moves_done = 0;

}

// Pre: Board game represents a legal game position.
// Post: An evaluation of the game, based on looking ahead depth moves, is returned.
// The best move that can be found for the mover is recorded as Move recommended.
// Uses: The classes Stack, Board, and Move, together with the function look_ahead
// recursively.
// !!!THE FUNCTION LOOK_AHEAD NEEDS TO INCORPORATE ALPHA-BETA PRUNNING!!!
int Board::look_ahead(const Board &game, int depth, Move &recommended) {

char Player = 'X'; // undeclared below
int Score = 0; // undeclared below
int Beta = 0; // undeclared below
int Alpha = 0; // undeclared below
int Sq = 0; // undeclared below
int Best_Square = 0; // undeclared below
int *Square = 0; // undeclared below

     if(game.done() || depth == 0)
          return game.evaluate();
     else {
          Stack moves;
          game.legal_moves(moves);
          int value, best_value = game.worst_case();

          while(!moves.empty()) {
               Move try_it, reply;
               moves.top(try_it);
               Board new_game = game;
               new_game.play(try_it);
               value = look_ahead(new_game, depth - 1, reply);

               if(game.better(value, best_value)) {

                    best_value = value;
                    recommended = try_it;

               }
               moves.pop();
          }
          return best_value;

     }
     /* Perform alpha-beta pruning */
     if (Player == 'X') {
         if (Score >= Beta) {
          int Square = Sq;
          return Score;
         } else if (Score > Alpha) {
          Alpha = Score;
          Best_Square = Sq;
         }  

     } else {
         if (Score <= Alpha) {
          *Square = Sq;
          return Score;
         } else if (Score < Beta) {
          Beta = Score;
          Best_Square = Sq;
         }
    }
    *Square = Best_Square;
    if (Player == 'X')
     return Alpha;
    else
     return Beta;
}



// Post: The Move try_it is played on the Board.
void Board::play(Move try_it) {

     squares[try_it.row][try_it.col] = moves_done % 2 + 1;
     moves_done++;

     return;

}

// Post: Return either a value of 0 for a position where neither player has won,
// a value of 1 if the first player has won, or a value of 2 if the second player
// has won.
int Board::the_winner() const {

     int i;

     for(i = 0; i < 3; i++)
          if(squares[i][0]&&squares[i][0]==squares[i][1]&&squares[i][0]&&squares[i][2])
               return squares[i][0];
     for(i = 0; i < 3; i++)
          if(squares[0][i]&&squares[0][i]==squares[1][i]&&squares[0][i]==squares[2][i])
               return squares[0][i];
     if(squares[0][0]&&squares[0][0]==squares[1][1]&&squares[0][0]&&squares[2][2])
          return squares[0][0];
     if(squares[0][2]&&squares[0][2]==squares[1][1]&&squares[2][0]==squares[0][2])
          return squares[0][2];

     return 0;

}

// Post: Return true if the game is over, either because a player has already won
// or because all nine squares have been filled.
bool Board::done() const {

     return moves_done == 9 || the_winner() > 0;

}

// Post: The parameter Stack moves is set up to contain all possible legal moves
// on the Board.
int Board::legal_moves(Stack &moves) const {

     int count = 0;

     while(!moves.empty())moves.pop();

     for(int i = 0; i < 3; i++)
          for(int j = 0; j < 3; j++)
               if(squares[i][j] == 0) {

                    Move can_play(i,j);
                    moves.push(can_play);
                    count++;

               }
               return count;

}

// Post: Return either a value of 0 for a position where neither player has won, a
// positive value between 1 and 9, if the first player has won, or a negative value
// between -1 and -9 if the second player has won.
int Board::evaluate() const {

     int winner = the_winner();
     if(winner == 1) return 10 - moves_done;
     else
          if(winner == 2) return moves_done - 10;
          else
               return 0;

}

********************************
// main.cpp -> given

#include "board.h"
#include "stack.h"
#include "util.h"

#include <iostream>
#include <stack>

using namespace std;

//#include "../../AppC/include/ansiut.h"
//#include "../../AppC/utility.cpp"
#include "move.h"
//#include "move.cpp"

//typedef Move Stack_entry;   //  Type for Stack entries.

//#include "../../chapter2/stack/stack.h"
//#include "../../chapter2/stack/stack.cpp"
//#include "board.h"
//#include "board.cpp"

/*
int look_ahead(const Board &game, int depth, Move &recommended)


Pre:  Board game represents a legal game position.
Post: An evaluation of the game, based on looking ahead
depth moves, is returned.  The best move that can be found
for the mover is recorded as Move recommended.
Uses: The classes Stack, Board, and Move, together with
function look_ahead recursively.

*/
/*
{
   if (game.done() || depth == 0)
      return game.evaluate();

   else {
      Stack moves;
      game.legal_moves(moves);
      int value, best_value = game.worst_case();

      while (!moves.empty()) {
         Move try_it, reply;
         moves.top(try_it);
         Board new_game = game;
         new_game.play(try_it);
         value = look_ahead(new_game, depth - 1, reply);
         if (game.better(value, best_value)) { //  try_it is the best move yet found
            best_value = value;
            recommended = try_it;
      }
      moves.pop();
      }
      return best_value;
   }
}*/


int main(void) {

   Board game;
   Move next_move;
   game.instructions();
   cout << " How much lookahead?";
   int looka, tmplooka, human, humanMove;
   cin >> looka;
   cout << "\nDo you want to move first or second(Enter 1 or 2): ";
   cin >> human;
   cout << endl;

   while (!game.done()) {
   // See if computer or human makes first move
      if (human  == 1) {
          tmplooka = looka;
          looka = 0;
          humanMove = 1;
          human = 2;
      }

      if (looka > 0) {
         game.look_ahead(game, looka, next_move);
         human = 1;
      }
      else {
         Stack moves;
         game.legal_moves(moves);
         moves.top(next_move);

         if (humanMove) {
            int row, column;
            cout << "Enter row: ";
            cin >> row;
               row--;
            cout << "\nEnter column: ";
            cin >> column;
            column--;
            cout << endl;
            Move myMove(row, column);
            next_move = myMove;
            humanMove = 0;
            looka = tmplooka;
         }
      }
      game.play(next_move);
      game.print();
   }

return 0;
}

**********************************
main:

 make
g++ -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9 -w -g main.cpp
In file included from move.h:4,
                 from board.h:4,
                 from main.cpp:3:
stack.h:13: ANSI C++ forbids declaration `Entry_type' with no type
main.cpp: In function `int main()':
main.cpp:91: no matching function for call to `Stack::top (Move &)'
stack.h:24: candidates are: enum Error_code Stack::top(const Entry_type &) const
make: *** [main.o] Error 1





0
 
jkrCommented:
>>stack.h:13: ANSI C++ forbids declaration `Entry_type' with no type

That's the line

typedef const Entry_type;

I assume that should have been

typedef Move Entry_type;

Then it should compile. The missing methiods are

Board::better(int,int)const
Board::worst_case(void)const
Board::print(void)const
Board::instructions(void)const
0
 
itsmeandnobodyelseCommented:
>>>> stack.h:13: ANSI C++ forbids declaration `Entry_type' with no type

In stack.h you need #include <move.h>

In move.h you have to remove #include <stack.h>

Regards, Alex

0
 
edelossantosAuthor Commented:
Excellent!!! Still working on code :o) -> Del
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

  • 2
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now