oops for chess board game.

[sam_cit]

Hi Everyone,

I'm working on developing a chess game and i decided to use c++ for
its object oriented approach. I have a bass class unit and is
inherited to distinct number of units (like king, queen, pawns
etc...), i will have pure virtual functions in the base class for
move(), attack() etc which are applicable to all units and would
override them in the child classes. Function specific to pawn like
recovering of another unit once it reaches the end of the chess board
will be implemented in the child class specific to pawn.

I also plan to use a global 2D (10*10) array of structure used to
represent the chess board along with status of each location (free/
occupied, color).

Is this a good approach? People do say that global variables in
case of oops programming, Is that correct?

Thanks in advance!!!

 

[Ivan Vecerina]

: I'm working on developing a chess game and i decided to use c++ for
: its object oriented approach. I have a bass class unit and is
: inherited to distinct number of units (like king, queen, pawns
: etc...), i will have pure virtual functions in the base class for
: move(), attack() etc which are applicable to all units and would
: override them in the child classes. Function specific to pawn like
: recovering of another unit once it reaches the end of the chess board
: will be implemented in the child class specific to pawn.
:
: I also plan to use a global 2D (10*10) array of structure used to
: represent the chess board along with status of each location (free/
: occupied, color).
:
: Is this a good approach? People do say that global variables in
: case of oops programming, Is that correct?

I do not know what kind of chess game you intend to develop,
but I wouldn't use such an approach for a chess game.

- one global variable to represent the board
This might be ok in the simplest case, but will soon be limiting.
Most chess application will have a module that explore a variety
of possible moves, to select the best possible option.
Do you intend to implement this?
Will you not keep multiple board states in memory?

- why a 10x10 board rather than 8x8 ?
If you intend to have "wall" pieces around the board, think
of what happens if a knight moves from an edge of the board.

- classes for each piece with virtual methods move(), attack(), etc
How do you intend to use these methods?
To chose a move, will you be making repeated calls to find out
a list of allowed moves?
Keep in mind that selecting moves is a computationally
intensive operation. You will rather want to have a function
that gives you a list of possible moves. And a function that
rates and scores each board, giving a score in the won..lost
range to say how good the situation is for a player.
Then, for example, apply some red/black tree for move selection...

From an OOP perspective, it seems sufficient to have a single
class representing a chess board. If you are looking at
implementing a standard chess game, there will not be any
surprises with new types of polymorphic chess pieces.
Switch statements, or maybe bit-maps representing possible
destinations for a piece seem preferable.

Of course, the design you are talking about can be interesting
from an experimental perspective, just to learn about C++.
But if you actually want to implement a chess game, you should
study prior art and the many open source games that exist, and
learn about computer strategy-game algorithms.


Cheers,
Ivan

 

[Michael DOUBEZ]

(e-mail address removed) a écrit :

Hi Everyone,

I'm working on developing a chess game and i decided to use c++ for
its object oriented approach.

OO is only one paradigm of C++. Saying that you choose C++ for its OO
approach is like saying you bought a statue for the shadow it casts.

I have a bass class unit and is
inherited to distinct number of units (like king, queen, pawns
etc...), i will have pure virtual functions in the base class for
move(), attack() etc

attack()?!?!?
Is your unit likely to loose the fight when attacking ?

which are applicable to all units and would
override them in the child classes. Function specific to pawn like
recovering of another unit once it reaches the end of the chess board
will be implemented in the child class specific to pawn.

This looks awkward. The units don't act on themselves obeing some local
rules.

I also plan to use a global 2D (10*10) array of structure used to
represent the chess board along with status of each location (free/
occupied, color).

Is this a good approach? People do say that global variables in
case of oops programming, Is that correct?

The good approach would be to start the design from the top not from the
bottom: The game of chess is composed of two players (white/black,
human/computer, net/local ...), a board(8x8), units(6 in kind ...) with
differents possible move depending on the board and the history of the
game (pawn at the beginning, roque ability) and arranged so and so at
the beginning of a game that can end by mat,pat or resign ...

We are far from deciding how to represent the board.

Generaly speaking, you should have a state for players and for board.

Learning some chess background wouldn't be bad either but it is OT here
. Alternatively, there is already some chess game in C++ around (a
little google brought up http://sourceforge.net/projects/brutalchess/).

Michael

 

[James Kanze]

(e-mail address removed) a écrit :

OO is only one paradigm of C++. Saying that you choose C++ for its OO
approach is like saying you bought a statue for the shadow it casts.

You mean, of course, that refusing to consider the OO approach
is like only considering the shadow. Support for OO is one
reason to prefer C++ to some other languages.

attack()?!?!?
Is your unit likely to loose the fight when attacking ?

The verb attack is very much a part of the vocabulary of chess.
I'm not sure, however, that it is a fundamental concept of a
piece.

For the rest, using a base class Piece, with different derived
classes for the different types of pieces, could be a good
approach. Depending on the rest of the design, of course; the
first thing to do is to define the overall program structure,
and see what fits in best. And of course, one shouldn't forget
that chess was not designed with OO in mind; the position of
other pieces, and even history, play a role in determining which
moves are legal.

This looks awkward. The units don't act on themselves obeing some local
rules.

No, but the rules do depend on the type of the piece.
Obviously, a function getListOfLegalMoves() would have to take
into account the rest of the board, and in a few cases, even the
exact type of some other piece. (A rook can only castle with a
king, in fact, only with a king that has never moved.) But
globally, putting the rules for moving each piece in a separate,
derived class, seems likely to be a good idea.

The good approach would be to start the design from the top not from the
bottom:

That is true. How the board is physically represented is really
an implementation detail, not to be decided until you have
decided on the interface of the class, and what it's exact role
in the program is to be. (In addition to maintaining game
state, it might, for example, be responsible for evaluating the
value of the position it represents.)

 

[Michael DOUBEZ]

James Kanze a écrit :

You mean, of course, that refusing to consider the OO approach
is like only considering the shadow. Support for OO is one
reason to prefer C++ to some other languages.

Other all the panel of available languages, saying that C++ is chosen
because of OO seems awkward to me, considering the cost of learning the
language.

What I mean is that there are other languages providing OO but easier to
learn than C++. My understanding of prefering C++ for it OO approach is
that there has been a pre-selection and C++ is the only OOL in this
selection.

I only wanted to point out the possibility of choosing another OO
language. Java would be a good candidate for such a project (native
support for graphical,network libraries, cross plateform) and it is OO.

The verb attack is very much a part of the vocabulary of chess.
I'm not sure, however, that it is a fundamental concept of a
piece.

I have not played chess in some times but as I remember, the units do
not attack but the player do (develop an attacking stategy).
Though, I remember an old computer chess games where the units through
in an arcade way and you could loose the fight.

[snip]

This looks awkward. The units don't act on themselves obeing some local
rules.

No, but the rules do depend on the type of the piece.
Obviously, a function getListOfLegalMoves() would have to take
into account the rest of the board, and in a few cases, even the
exact type of some other piece. (A rook can only castle with a
king, in fact, only with a king that has never moved.) But
globally, putting the rules for moving each piece in a separate,
derived class, seems likely to be a good idea.

That depends on how you consider the system:
1. chess is pieces moving on a board with history
2. chess is a succession of board state

In the first case, the class approach seems good enough to me.

In the second case, the list of legal move can be a list of command that
modify the board state. This approach allows moves of two units like
pawn at the beginning or rook or transforming a pawn into another piece.
The getListOfLegalMoves() becomes a getListOfLegalStates() eventually
limited to the motion of a specific piece. In this case, pieces are just
a parameter and a good candidate for template specialization other the
different kind of move.

[snip]

Michael

 

[Noah Roberts]

Hi Everyone,

I'm working on developing a chess game and i decided to use c++ for
its object oriented approach. I have a bass class unit and is
inherited to distinct number of units (like king, queen, pawns
etc...), i will have pure virtual functions in the base class for
move(), attack() etc which are applicable to all units and would
override them in the child classes. Function specific to pawn like
recovering of another unit once it reaches the end of the chess board
will be implemented in the child class specific to pawn.

I also plan to use a global 2D (10*10) array of structure used to
represent the chess board along with status of each location (free/
occupied, color).

Is this a good approach? People do say that global variables in
case of oops programming, Is that correct?

Thanks in advance!!!

Chess is one of those problems where you are trying to get every clock
out of your CPU. I think virtual functions are going to have a
significant impact on your ability to reach the deeper ply. If for
every piece on a board you have to make a virtual function call to
generate its moves you are looking at making a shit load of virtual
function calls.

About your board representation, that is a fairly common one that works.

However, that all said...go ahead and try it. Chess AI is a major
learning event that will teach you a great deal about many things. Try
your approach, see why it fails, why it succeeds... I've started over
numerous times myself.

You've chosen a great problem that has a wealth of research to read and
examine that will teach you about algorithms and performance issues.
There is even plenty of room for more advancement though with western
chess that is narrowing (the chances of you coming up with something
genuinely new is pretty slim). Its great fun. Good luck.

 

[Noah Roberts]

About your board representation, that is a fairly common one that works.

One adjustment I would make:

Consider the knight. If a knight is on the edge of the board it has the
opportunity to move 2 spaces off the board. So putting a 2 space buffer
around your board with -1 can save several if branches and bring it down
to just one "if (loc == -1) invalid;". Your knight can never move out
of the array or across the board and you don't have to do a lot of, "if
I'm here don't try these motions."

 

[Ian Collins]

Chess is one of those problems where you are trying to get every clock
out of your CPU. I think virtual functions are going to have a
significant impact on your ability to reach the deeper ply. If for
every piece on a board you have to make a virtual function call to
generate its moves you are looking at making a shit load of virtual
function calls.

Beware of premature optimisation! The extra few cycles may well be
insignificant compared with the function's logic.

 

[Noah Roberts]

Beware of premature optimisation! The extra few cycles may well be
insignificant compared with the function's logic.

Beware of premature pessimization.

Several million or billion virtual function calls adds up to a
significant impact in a function where much of the time is spent
generating moves (the function he wants to virtualize).

Using virtual functions here is a design decision that is not going to
be easily reversed later when he realizes that it in fact has a major
impact on the algorithm.

But like I said, he can try it and then start over when he realizes the
cost is too great.

 

[James Kanze]

Beware of premature optimisation! The extra few cycles may well be
insignificant compared with the function's logic.

More significantly, virtual functions have a functionality. If
you don't use virtual functions, you must use something else.
Depending on the processor, that something else could easily be
even slower.

Until you've actually measured a problem, avoiding virtual
function calls is just stupid. Once you have a problem, you
also need before and after measurements---it's possible that
eliminating the virtual functions makes the code slower.

 

[Noah Roberts]

More significantly, virtual functions have a functionality. If
you don't use virtual functions, you must use something else.
Depending on the processor, that something else could easily be
even slower.

Until you've actually measured a problem, avoiding virtual
function calls is just stupid. Once you have a problem, you
also need before and after measurements---it's possible that
eliminating the virtual functions makes the code slower.

Normally I would agree with you guys, but having some experience with
this problem domain--in this case, I don't. A polymorphic design is not
going to be easy to change. It can pay to take advice from those who
have been there, done that. You don't always need to find everything
out the hard way.