[jon.kiparsky]

Quote

This is bad why?

It's not necessarily bad. It's just a fact of the design. OOP can create a lot of clarity, done right, and this approach is, in itself anything but clear. The question is one of design: what does the designer want?

I'd like to be able to ask the rook who it can attack. That's just the way I work. I don't say it's better, it's just the way I like to do things.

[BobRodes]

OldWolf, your CASE SELECT is an example of what I was talking about in the other thread about cohesion. You're putting the move logic in the board, figuring out what piece is trying to move, and then applying that piece's move logic to determine if the move is valid. If the piece knows what its move logic is, you only have to tell it to move and let it decide whether it's allowed to or not.

My feeling is that it is more efficient to have the piece keep track of its move logic, and the board keep track of what pieces are where and render them in the UI. This cuts down on decision logic.

Chess heuristics aren't all that massive if you have the computer make random moves. My comments are based on this idea, on the part of a chess game that has to do with rendering the pieces and determining whether a move is legal or not. Whether it's a GOOD move or not is a different thing. People who have spent 30 years working on streamlining the process of going through potential moves and evaluating potential positions have 30 years more experience at it than I do.

This post has been edited by BobRodes: 27 July 2012 - 02:20 PM

[jared.deckard]

Placing the move logic into separate piece classes also makes it easier to collaborate and maintain.

dic-chess SVN: http://code.google.com/p/dic-chess/

[OldWolf]

Absolutely. I've recently finished the move to using classes for each type of piece. I went that route because I am working towards a specific method of tracking threat to ensure piece movement is legal with respect to the King. More difficult than I had originally anticipated. I'm currently debating wether or not I want the pieces to know their location, or have the board track it. In the end, as long as I can pass the information onto the presentation format it won't matter. I'm simply trying to find a good mix between efficiency and functionality.

I haven't run into much trouble maintaining the movement logic, since the lot of them took less than a hundred lines to code. Even the Pawn was easier than I thought it would be (though I haven't added en passant yet).

Move logic was a fasciniating part of the program to develop, though, and probably the only part that hasn't really changed.

How about that for a topic? Pick a piece and give us your best/most creative way to validate that the move was legal. Assume the piece knows it's own location on the board (either passed to it or stored within its own scope).

[Sheph]

I'd have the interface for a Piece contain getAvailableMoveList() (based on its current location), and return a list of coordinates that are available. For a knight, its as simple as variations of +2, +1 for x and y, and such with an additional check for empty space. Then when the player tells it to move, it can instantly accept or deny by searching its list.

Pawns and kings would be more difficult because they need to know things like, is it the first turn, did that guy just move there?, did i perform a castle yet? would I be in checkmate? Just tons of things to consider before designing a generic interface. If the Board was an object it had a reference too, I might also consider having Board maintain the turn # (either stored or be able to be derived) and certain factors, like whether or not the King has made a castle yet or not, whether he has been in check, etc.

[baavgai]

There does seem to be a misperception as to how OOP works. The ability to hide implementation details means that those details are functionally irrelevent.

So, to extend the storage idea, here's some code:

struct Piece {
	enum PieceType { None, Pawn, Knight, Bishop, Rook, Queen, King, Invalid };
	enum PieceSide { White, Black };

	Piece();
	Piece(unsigned char);
	Piece(PieceType, PieceSide);
	PieceType getType() const;
	PieceSide getSide() const;
	unsigned char getValue() const;
private:
	unsigned char value;
};

struct BoardPos {
	int row, col;
	BoardPos();
	BoardPos(int row, int col);
	bool isValid() const;
};

class Board {
public:
	static const int ROWS=8, COLS=8;
	Board();
	void reset();
	int getTurn() const;
	bool isAvailable(const BoardPos &) const;
	Piece get(const BoardPos &) const;
	void set(const BoardPos &, Piece);
	bool move(const BoardPos &posFrom, const BoardPos &posTo);
	std::vector<BoardPos> getAvailableMoves(const BoardPos &) const;
private:
	int turn;
	static const int DATA_SIZE = 32;
	char data[DATA_SIZE];
};

You'd have to squint to see the odd storage mechanism proposed earlier. Indeed, the details aren't obvious. That's really the joy of encapsulation.

Piece::Piece() : value(Piece::Invalid) { }
Piece::Piece(unsigned char v) : value(v&0xf) { }
Piece::Piece(PieceType type, PieceSide side)  : value(type | (side==Piece::Black?0x8:0)) { }
Piece::PieceType Piece::getType() const { return PieceType(value&0x7); }
Piece::PieceSide Piece::getSide() const { return PieceSide(value&0x8 ? Piece::Black : Piece::White); }
unsigned char Piece::getValue() const { return value; }

static bool getBoardLocation(const BoardPos &p, int &index, bool &highNibble) {
	if (p.isValid()) {
		index = p.row*Board::COLS+p.col;
		highNibble = (index % 2)==0;
		index /= 2;
		return true;
	}
	return false;
}

Board::Board() { for(int i=0; i<DATA_SIZE; i++) { data[i] = 0; } }

Piece Board::get(const BoardPos &pos) const {
	int index;
	bool highNibble;

	if(getBoardLocation(pos, index, highNibble)) {
		unsigned char value = data[index];
		if (highNibble) { value >>= 4; }
		return Piece(value);
	}
	return Piece(Piece::Invalid);
}

void Board::set(const BoardPos &pos, Piece piece) {
	int index;
	bool highNibble;

	if(getBoardLocation(pos, index, highNibble)) {
		unsigned char hi, lo;
		if (highNibble) {
			hi = piece.getValue();
			hi <<= 4;
			lo = data[index];
		} else {
			hi = data[index];
			lo = piece.getValue();
		}
		data[index] = (hi & 0xf0) | (lo & 0x0f);
	}
}

As noted, the heart of the matter is a getAvailableMoves function. Should piece have that method? It could. But then piece would require knowledge of board. However, board could just as easily handle the method. There is no right or wrong way. Design wise, I prefer objects know as little about other objects as possible.

[jon.kiparsky]

Quote

The ability to hide implementation details means that those details are functionally irrelevent.

Yes, this is absolutely the point of OOP: to hide the implementation details so I don't have to care about them. If I never see your representation of the board, because you hide it behind a friendly interface, then all of a sudden the lack of clarity in the actual representation isn't my problem - it's yours, 'cause I'm not maintaining it. So now, far from creating an ugly mess, you've used OOP to hide a very nice but very mistake-prone representation behind a friendly facade - best of both worlds. Now we have a neat representation under the hood, but we don't have to think about twiddling bits when we want to be thinking about chess.

[jon.kiparsky]

baavgai, on 28 July 2012 - 05:44 PM, said:

As noted, the heart of the matter is a getAvailableMoves function. Should piece have that method? It could. But then piece would require knowledge of board. However, board could just as easily handle the method. There is no right or wrong way. Design wise, I prefer objects know as little about other objects as possible.

I'd have no objection to a getAvailableMoves function that was simply a pass-through to the board. I'd like to be able to ask the rook what it can do, but I see no reason why Rook should know that - it should simply know who to ask.

[Sheph]

Each piece needs to have a corresponding method implementation that will give a list of possible moves. If it wasn't object oriented programming, we'd have a function: getKnightMovesFrom(BoardPos pos). One function for each piece. In OOP, you can just have each piece class implement the function. I don't see why it belongs in Board, unless you'd prefer to write them all as functional methods and maintain balance between the two styles as baavgai was talking about earlier.

Would you rather,

getAvailableMoves(board[3][6]);

or

board[3][6].getAvailableMoves()

essentially it is the same, though the first way would have to have to define some extra control flow, unless you can come up with some genius equation where 4 bits can be turned into a list of moves using mathematics.

[BobRodes]

OldWolf, on 27 July 2012 - 05:28 PM, said:

Absolutely. I've recently finished the move to using classes for each type of piece. I went that route because I am working towards a specific method of tracking threat to ensure piece movement is legal with respect to the King. More difficult than I had originally anticipated. I'm currently debating wether or not I want the pieces to know their location, or have the board track it. In the end, as long as I can pass the information onto the presentation format it won't matter. I'm simply trying to find a good mix between efficiency and functionality.

I haven't run into much trouble maintaining the movement logic, since the lot of them took less than a hundred lines to code. Even the Pawn was easier than I thought it would be (though I haven't added en passant yet).

Move logic was a fasciniating part of the program to develop, though, and probably the only part that hasn't really changed.

How about that for a topic? Pick a piece and give us your best/most creative way to validate that the move was legal. Assume the piece knows it's own location on the board (either passed to it or stored within its own scope).

En passant has elements to it that aren't present in the rest of the logic, because it requires that a particular pawn move be made prior to the move to be legal.

Location state has to be maintained somewhere, and move logic requires knowledge of the location of other pieces. Therefore, it doesn't make sense to maintain location state at the piece level, because each piece would have to maintain the state of each other piece redundantly. To me, the proper assignment of stuff is board maintains location, piece contains move validation logic. User interacts with board to move, not piece. Board passes move to appropriate piece, piece returns whether the move is valid, board updates locations appropriately.

I'll take a stab at knight move logic, since it is the simplest. This assumes a position x0, y0 and a target square x1, y1 that is a real square and does not contain a friendly piece. (I'll assume 5 minute game rules for the time being, wherein a king left en pris is subject to capture with loss of game.) The move is valid if abs(x0-x1) + abs(y0-y1) = 3, and neither value = 0.

That was fun, so I'll have a look at bishop. Again, I'll assume that the target square does not contain a friendly piece. (It makes sense for the board logic to check to see if there's a friendly piece on the target square: if so, the move is illegal and we don't have to do any more validation work.)

With the same assumptions as I stated for the knight, a bishop move is valid if abs(x0-x1) = abs(y0-y1) and there are no pieces on intervening squares. If the first condition is met, loop through the intervening squares to the target square. Abort if one is occupied.

Ok, so a rook is valid if x0=x1 xor y0=y1. A queen is valid if either the bishop or the rook validation criteria are met. In either case, apply the logic to determine whether there's an intervening piece.



I'd be interested to see your class structure as it stands.

This post has been edited by BobRodes: 31 July 2012 - 09:15 AM

[jon.kiparsky]

Quote

En passant has elements to it that aren't present in the rest of the logic, because it requires that a particular pawn move be made prior to the move to be legal.

Probably the easiest way to handle that would be to set a flag in the pawn, rather than searching the game history to evaluate pawn moves. The flag might be a reference to the pawn that can be captured e.p., or a boolean, or whatever's convenient.

We should keep in mind that we might like to think downstream in evaluating moves (though properly speaking, this can be and should be independent of the Game part, it's still going to have to represent the same information in order to get it right). You'd like to be able to pass the state around: to evaluate position P, we want to look at P_M1, P_M2, etc... baavgai's position notation is nice for the raw board positions but how light can we make the object as a whole, with everything it needs to remember?

Castling logic, to me, seems to be inherently buggered, but my feeling is that each King should have a flag for whether it can or cannot castle on Kside or Qside. This would be unset when K or appropriate rook moves, and set and unset depending on whether intervening squares are in check or occupied, or of course if the K is under check. This seems to me more sensible than checking all of these facts each time you're evaluating a King move.

@Bob - I suspect this is what you meant - correct?

This post has been edited by jon.kiparsky: 31 July 2012 - 08:00 AM

[baavgai]

I'll admit, I'm still thinking about this one.

I figured I'd flag it on the move. e.g.

class BoardMove {
public:
	enum Status { Invalid, Default, Capture, EnPassant, Castle, Promotion };
	BoardMove();
	BoardMove(BoardPos posFrom, BoardPos posTo, Status status = Default);
	Status getStatus() const;
	BoardPos getFrom() const;
	BoardPos getTo() const;

The Board, or Game, would sport:

std::vector<BoardMove> priorMoves;

This solves a few issues. It allows you to know which turn it is, who's turn it is, if en passant is flagged on the last move, if castling is an option. It also offers the tantalizing option of not storing the board at all, just the moves that lead up to the state. Though I don't think I'll go there.

Honestly, the biggest challenge I'm finding is check. Rather, pruning out moves related to a discovered check. Mate should be implicit, though, if no moves are available... unless, stalemate. Damn.

Also, in my mind, I'm trying to leverage prior work. If you have to generate and analyze moves into the future, you don't want to loose that data when you choose a path. So, available moves actually become available boards, perhaps with it's own already generated list of available boards. It could be the wrong direction, it's proving a distracting challenge.

[jon.kiparsky]

I'm really tempted to try to start working a parallel path in scheme or lisp. It would be really fun to compare the sorts of thinking that go on. No time for that now, though... maybe after the West Coast trip.

[jon.kiparsky]

baavgai, on 31 July 2012 - 10:28 AM, said:

This solves a few issues. It allows you to know which turn it is, who's turn it is, if en passant is flagged on the last move, if castling is an option. It also offers the tantalizing option of not storing the board at all, just the moves that lead up to the state. Though I don't think I'll go there.

This is actually how Sheph and I report back a Game in the tournament project - a list of Moves.
It works great for the purpose, which is to be able to review and analyze the game play, but I'm not sure if it's the best way to track the state in an ongoing game.
For a functional approach, it might be exactly what you want.

[Skydiver]

I'm now wishing that I had not given away my copy of Turbo Gameworks over 22 years ago. It actually covered chess and a few other games. Although written at time where PC's didn't have huge memory spaces available to them and clocks were still measure in the low MHz ranges, some of it's approaches to save space and time maybe "quaint", but I think that the concepts still apply.

Time to troll eBay or Amazon, I guess.