NEED HELP ON A CHESS PROGRAM IN C++!!

Well, you need to represent the game!

You''ll need a representation of the board: how about a 2-d array of cells.

You''ll need a representation of the pieces. Think of a piece as a class and then think of the attributes each piece has (colour, movement type, current location)

You''ll need some way to move piece information from one cell of the array to another when a piece moves from one place on the board to another.

You''ll need to be able to add pieces to the board (at initiallisation and when pawns are promoted) and you will need to be able to delete pieces from the board (when they are taken by the opponent).

You''ll need to be able to draw the board and pieces... but remember that it doesn''t have to be fancy graphics... simple ascii characters may suffice.

Finally you''ll need a way of recording who''s turn it is.

That''s all you really need if you want to ignore AI (i.e., the part of the program that actually ''plays'' chess).

Thanks for the reply! I''ve actually thought of that but other things crop up on my mind, especially how would i know that the King is checked? or to be Openchecked? As well as the attacks and how to pass values from one class to another. Will the board be a class or do I just have to declare all pieces in the main? Thanks for your help and I hope you''ll bear with me and my inquisitive mind!

Some of these problems are trivial when you just break them down. For instance, to see if you are in check, simply iterate through all the opposing pieces: if any of those pieces are attacking the square with your king on, then you're in check. It's probably best to generate a true/false value for 'under attack' for every square each turn, so that you can easily check for checkmate too. As for passing values from one class to another, that's really just basic programming information that you should have picked up on your course. To get answers on that, you'd have to ask more specific questions, and not in this forum.

Edited by - Kylotan on November 12, 2001 8:41:31 PM

I wrote a nice chess game that went through every possible move for your player, the score was the total of the value of your pieces, minus the value of the opponents pieces, then the same thing happens with the opponent, using the resulting arangement of pieces, and the score is subtracted from it''s score, and I found that it can be iterated about 4 times (two moves for each player) before it becomes too slow to even bother. It''s really cool, because it results in the computer sacraficing pieces, when you put a piece in danger, it will put one next to it to protect it, and stuff like that.

There are only two problems: the starting can be very slow, so people usually make the first few moves predefined, second when there are no good moves, the computer does unhuman like things such as move pieces around to random places for absolutely no reason.

wow, just today i was wondering how it should be to plan a nice ai game for a chess, i''ll tell you what i''ve thought. first of all you MUST have that 8x8 matrix indicating which cells are attacked or which aren''t for simple 2playing game, and the basic rules. obviously you must first make a 2player chess which is not an easy thing. thinking deeper, i think there should be a tree indicating the next n moves (the deeper the better plays but slower) and every "board position" must have a score, depending on which pieces you have, your opponent has, and (here comes the ugly part) the position of the pieces on the board, which i really don''t have a clue how to do it. anyway, for the first moves you should have some "basic movements" calculated for making it a little quicker, which should be the most calculating ones.

i don''t know, (i am thinking on position) perhaps defining beginning and try to have the central cells or end and try to move the king, things like that but putting a score to the position of a board i think is the solution, the question is how!

Ok guys, I feel as though I finally have some knowledge to share. I sense that you haven''t ever written any significantly large program from what I have read. I''ve read tons of articles on how to write chess programs, and I know all about all of the different AI methods and all of that "advanced" stuff, so I know what I''m talking about when it comes to writing a chess program with no AI.

Writing a 2-player chess program with no AI is not hard. It takes a little time to get everything working correctly, but it''s not hard, just time consuming. So you have to stick with it.

I''ll start with a sort of checklist of things you will need for a working chess program.

-A way to represent the chess board in the computer''s memory
-A way to make a move on the chess board
-A way to undo a move that you made on the chess board
-A way to check if a move is a legal move or not (you don''t want someone cheating)
-A way to check if the game is over

I think that should about cover a 2-player game with no AI. I''ll try to walk us through each of these things and give a general idea about how to make them.

The Board
For a basic chess program, all you need is a 64-byte array. Something like this will work just fine:

char squares[8][8];

Since you are only making a 2-player chess game with no AI, this will work great and it keeps things nice and simple. If you were going to add AI to the game, I''d go with a straight 64-byte, 1-demensional array. But it''s not really important at this point. Whatever makes sense to you. Just keep things as simple as possible because it can get overwhelming if you''re not careful.

Now you will need to fill your board with pieces. An example of this might be to just use letters for each piece, for example:

squares[0][0] = ''R''; // Rook squares[0][1] = ''N''; // Knight squares[0][2] = ''B''; // Bishop // etc.

And you would fill up the rest of the board like that with the letter that will stand for each piece. For white pieces you could use capital letters, and for black pieces you could use lowercase letters so you can tell the difference.

Making Moves
The way I would suggest making a move is to make a move struct or class, for example:

struct Move { int row_from; int col_from; int row_to; int col_to; char piece_captured; char piece_promoted_to; bool castle; bool en_passant; };

Hope this doesn''t look too confusing. If you aren''t familiar with how a struct works, I''ll give you a little demo. After you have made the struct (with the above code), you would creat a ''Move'' and use it like this:

Move the_move; the_move.row_from = 4; the_move.col_from = 5; the_move.row_to = 5; the_move.col_to = 6; the_move.piece_captured = squares[the_move.row_to][the_move.col_to]; // keep track of the piece we capture the_move.piece_promoted_to = NULL; the_move.castle = false; the_move.en_passant = false; MakeMove(the_move);

We haven''t made the MakeMove() function yet, but let''s just assume it works. The above code would move the piece from square 4,5 to the square 5,6. Our ''Move'' struct has several entries that you might not know what you need to do with, so I''ll explain.

row_from, col_from, row_to, and col_to are pretty straightforward. They are the row and columns that tell us where we are moving from and where we are moving to.

piece_captured is used for when you undo a move, because you have to put the piece back when you undo the move, so you need to know what piece you took when you undo the move.

piece_promoted_to is used for when a pawn gets to the other side of the board. You will need to know which piece to promote the pawn to.

castle is a true/false value that tells us whether this move is a castling move or not.

en_passant is a true/false value that tells us whether this move is a special en passant move (search for it on the web if you don''t know what this is).

Now you''re MakeMove() function might look something like this:

bool MakeMove(Move & the_move) { if(castle) { // handle castling } else if(en_passant) { // handle en passant move } else if(piece_promoted_to != NULL) { // handle promoting the piece } else { squares[the_move.row_to][the_move.col_to] = squares[the_move.row_from][the_move.col_from]; // move the piece from it''s old square to it''s new one squares[the_move.row_from][the_move.col_from] = NULL; // Set the pieces old square to empty } return true; // we will return false if the move was illegal }

The MakeMove() function isn''t complete, but I don''t want to do all of the work for you now and take all of the fun of having to figure this stuff out for yourself.

Well, it''s 3:30AM now so I''m going to go to sleep. If you have questions (which I suspect you will) just reply and I''ll explain more or whatever I need to do.

Or email me.

Hope this helps get things rolling.

Russell

PS - I''ll probably start something like this on my website soon, a chess programming tutorial.

quote:

---

Original post by Timkin
Well, you need to represent the game!

You''ll need a representation of the board: how about a 2-d array of cells.

You''ll need a representation of the pieces. Think of a piece as a class and then think of the attributes each piece has (colour, movement type, current location)

You''ll need some way to move piece information from one cell of the array to another when a piece moves from one place on the board to another.

---

Yes, you need to represent the board, and the pices and so on.
I suggest you represent the board as a one dimension array.

Add two additionally rows around the board, where you just can place pieces on that cannot be removed. That way you can recognize you are not on the board any more simply checking that field for the "not-on-board" value.

so finally you end up with a 12*12 board represented in a 1 Dimension array of 144 entries.

Now a move is simply a ONE value to add to your actual location.
(move = x + 12*y)
and
x = move modulo 12; y = move / 12

(These days memory can wasted, the hardcore coders will even make the board being 16*16, so they can use shifts instead of divisions.)

So on a 16*16 board a pawn moving forward for white is x stays(0), and y is increased by one. -> move = ( 0 + 16*1) = 16.
Check from actual position in the array 16 forward.
Is this a free field? ok, i can go there...

No offense to OmniBrian, but he''s trying to make a 2-player game with no AI. Saving a cpu cycle here and there isn''t a concern at all in making a chess game with no AI.

And no offense to the original poster, but I don''t think he is at the level where all of this optimization and other ways of doing things are going to be very helpful to him. I think the most helpful way of helping him is keep it as simple as possible, because it''s going to get rather complicated for someone who''s never done this kind of thing before especially when you get to checking to make sure moves are legal, checking to make sure pinned pieces can''t move, etc.

To you and me, it might not be that hard of a task, but I remember when I first started trying to learn how to do this chess programming stuff, and it''s very frustrating when you finally think you have everything working and it all goes insane because you forgot one little simple thing. If you start trying to get fancy with trying alternative methods of board representation it just adds more chances for problems and frustrations to get you down and set you back.

Besides, there isn''t really any great advantage to having a 12x12 array or 16x16 array. The only place that this would matter is if you were adding AI to your program and you were overly concerned with making your funciton that generates legal moves ultra fast. Generating moves faster will help your program play better, but that''s not what determines a world-class program from an average program. There are a lot of advanced topics, but the main way of increasing the strength of a chess program comes from ordering your moves correctly before you do an alpha-beta search, thus creating more and more cutoffs and reducing the branching factor from about 36 down to around 3 (with very good move ordering and other little tricks such as NULL move and forward pruning).

Basically my point is that at this point in his development as a chess program author, you''re only going to do more to confuse the poor guy than to help him. Judging from some of his questions he''s not a very advanced programmer yet and he needs a little guidance (which is fine, we''ve all been there). I just think that you''re going to set him back when he try''s to start messing with some alternative way of representing the board when he is obviously struggling with "the basics" at this point.

If speed is what you''re looking for in a move generation function, then your best bet is to either keep things simple and go with a straight square array (a 16x16 board might give you a faster move generation, but I don''t think it would be noticable in actual playing strength of the program). The other alternative to a simple ray-tracing method of move generation is 0x88 move generation, which basically eliminates edge detection. Bitboards are probably not faster than either of these methods when you look at only move generation, but bitboards give you savings in other places, such as detecting which pieces are attacking which squares or if a king is in check, so the overall speed of the program might be faster, but that''s too hard to tell without doing a lot of testing on your own.

quote:

---

Original post by Russell
(Giant post deleted)
PS - I''ll probably start something like this on my website soon, a chess programming tutorial.

---

Russell, let me just step in to encourage you to do so as much as possible. Once you do, please send me the link (over at www.gameai.com. I''d love to point to it..you really did a good job there of setting up the basics!




Ferretman

ferretman@gameai.com
www.gameai.com

From the High Mountains of Colorado

now tell if my idea of the board was ok!

how can i score a position?

You could value every possible move based on the value of the piece. Then do the highest value move.

i agree.
it is not worth losing a pawn to capture the queen, when that pawn was protecting other pieces (YOUR queen, the king, whatever). for a decent AI you''ll have to factor in which pieces are blocking other''s, as well as which pieces are "protecting" something else or preventing one of the opponent''s moves.

--- krez (krezisback@aol.com)

Sorry Krez, I actually deleted my post (between yours and js_530''s) as I felt that it was something akin to what js_530 was trying to suggest: i.e., that the value of a move should be related to the value of a piece. I was simply saying it the other way round: that the value of a piece should be related to the value of its moves, whihc should include the NULL move.

Timkin

timkin,
why would you do something like that? with all the worthless posts laying around (language holy wars, flames based completely on opinion rather than the topic, and whatnot) one of your comments hardly deserves to be deleted. redundancy isn''t such a bad thing

--- krez (krezisback@aol.com)

quote:

---

Original post by Anonymous Poster
I disagree. If you look several moves ahead, then the score would work out to be lower if its possible for your opponent to kill another important piece. In other words, in order to determine the score, you would have to go through all your opponents possible moves and determine the lowest possible score by recursing. Only on the final recursion would it look at the value of the pieces. If you did it like this, it would realise that if it gave up this pawn and took this queen, and it did so-and-so move, then it would be impossible to save your own queen.

---

hmm... you said you disagree, but that was exactly my point! by looking at the possible consequences of a seemingly "good" move, the AI could discover that it might not really BE a good move (the computer would decide not to kill the player''s queen, to save its own queen two turns later). remember, we WANT the AI to be able to play a good game.
it is not practical to have the computer check all possibilities for every turn until the end of the game, as it would take far too long. i think i read somewhere that a human can only think ahead three or so turns in a chess game (although this is a vague memory, and it could be inaccurate). so, if the AI calculated it''s probabilities for the next two or three turns, it should be able to play a decent game against a person.
i have another idea about this AI too. perhaps it could be programmed to look for certain patterns that could lead to a multi-move strategic move. i am not a good enough chess player to give a real-life example (a friend of mine who cares about chess WAY too much beat me in five moves once, with some strategy that he set up and i walked right into; and, he said there was actually a NAME for that series of moves too, although i don''t recall what it was). but, my point is, if the computer notices a certain pattern of pieces on the board it can start the sequence of moves. then, each following turn, it can check if the opponent''s move "blocked" this strategy (by putting a piece in the way, or capturing a key piece, or whatever). if not, it continues with the sequence. this is repeated until the strategy fails or is completed successfully.
these patterns would not necessarily cover the whole board, it could be as simple as the opponent''s bishop being in a certain spot in relation to the computer''s rook and knight; as long as there is room on the board (not too close to the edges, with no pieces blocking the important moves) the "strategy sequence" is valid and the AI can attempt to pull it off.
the patterns could be coded into the program (or in a data file of some sort), or possibly be "learned" (if the AI is really "smart"; i know little to nothing about this though, i am speaking in theoretical terms) after playing many games.
ha, this has probably already been done, or discounted, by those AI people who love chess (was it "deep blue" that beat that grandmaster chess player? i always get it confused with "deep thought" from HGTG!). but, it is fun to talk about it here.
so, anyone think i am completely wrong? or (more hopefully) does anyone have any similar thoughts?
damn, i might have to start programming a chess game now.

--- krez (krezisback@aol.com)

okay, i hope nobody is annoyed by my rambling...
my previous posts were mainly about how the AI could form a decent "attack" strategy against a player, but upon clicking the "reply to topic" button i realized that it should be defensive also.
in addition to checking which of it''s pieces are under attack in the next turn, it should look at the opponent''s pieces for these "attack strategy patterns" i was rambling about in my last post. if it sees that the player is in the correct formation, and seems to be following the pattern, it would attempt to stop it (either by blocking some moves with other pieces, moving the pieces that are in danger, putting the opponent''s queen in danger, whatever).
oh, and it should also try to protect it''s pieces when they are wandering in dangerous territory. if you do not know what i mean (not to insult anyone''s intelligence), it is like so: say the AI has an opportunity to capture the player''s rook with a bishop. the player moves his queen to protect the rook; that is, he positions the queen so that if the rook is captured, he can capture the offending bishop immediately afterwards. the queen is protecting the rook. this doesn''t always work, as the player might be willing to sacrifice the bishop for the rook, but it is generally a good strategy.
any comments?

--- krez (krezisback@aol.com)

To Krez: that might be an average player that can look ahead 3 moves. It''s not uncommon for a Grandmaster to look ahead 10-12 or even more moves, and of course, they aren''t looking at EVERY possible move, they only look at the handful of best moves which makes it much easier.

As far as determining the best move in a given position, read this article on the MinMax search algorithm.

http://www.seanet.com/~brucemo/topics/minmax.htm

It is written by Bruce Moreland who is the author of one of the strongest computer chess programs in the world (although he doesn''t make it publicly available). His program named Ferret beat Deep Fritz (generally recognized as the best program in the world today) in a tournament a while back. Ferret went on to win the tournament.

Anyway, he''s got some good articles there about chess programming, but most of it is about the AI part of the program. Gamedev.net also has an article about chess programming. I can tell several of you don''t really know a lot of the basics about how a chess program works, so I would suggest (if you want to learn) reading some of Bruce''s articles and reading the article abotu chess programming here on gamedev. Here''s another good webpage that has some good info on chess program AI: http://www.galahadnet.com/chess/chessprg/

My advice if you want to write your own chess program is to read up on those articles and search for others, and basically get familiar with the concepts invovled before you start our writing your own chess program.

If you''re into USENET, you can post questions to rec.games.chess.computer and you''ll get many good answers to your questions. Bruce Moreland posts there, as well as Bob Hyatt (author of Crafty, another very strong program) and many other people who are very knowledgable in the field of computer chess programming. I know a lot about computer chess programming, but these guys blow my knowledge out of the water.