Innocent code is guilty

[LB]

This innocent code (or the real, unsimplified version of it, anyway) is guilty for making me stay up to 2AM debugging a crash.

This simplified code compiles and runs without crashing or invoking undefined behavior, but can you guess the output without compiling and running it yourself? I may have made it a little obvious, but it was completely unexpected in my case.

#include <iostream>
#include <memory>
#include <tuple>
#include <map>

struct Position { int x, y; };
bool operator<(Position const &a, Position const &b)
{
	return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}
std::ostream &operator<<(std::ostream &os, Position const &p)
{
	return os << '(' << p.x << ", " << p.y << ')';
}

struct Board
{
	class Piece
	{
		Position p;
		friend struct ::Board;
	public:
		Position const &pos = p; //could just as well be a function
		Piece(Position const &p)
		: p(p)
		{
		}
	};

	void swap(Position const &source, Position const &target)
	{
		std::cout << "Swapping " << source << " to " << target << std::endl;
		pieces[target].swap(pieces[source]);
		pieces[target]->p = target;
		pieces[source]->p = source;
		std::cout << "Swapped  " << source << " to " << target << std::endl;
	}
	
	void add(Position const &p)
	{
		pieces[p] = std::unique_ptr<Piece>(new Piece(p));
	}
	Piece *at(Position const &p)
	{
		return pieces[p].get();
	}

private:
	std::map<Position, std::unique_ptr<Piece>> pieces;
};

int main()
{
	Board b;
	b.add({1, 1});
	b.add({1, 2});
	b.add({2, 1});
	b.add({2, 2});
	
	std::cout << "First swap:" << std::endl;
	b.swap({1, 1}, {1, 2});
	std::cout << std::endl
	          << "Second swap:" << std::endl;
	b.swap(b.at({2, 1})->pos, {2, 2});
}

When you think you know what the output is, click here to see if you're right: http://ideone.com/xwuawG

Was the output what you expected? Do you know what the problem is? Can you guess how I fixed it?

[firedraco]

My first thought was that swap didn't actually swap anything, but looking at it I believe it actually does.

Besides swapping, all you are printing is source and target (the constant parameter versions), so obviously you would get the same lines in a row.

[Disch]

I see 2 problems.


1) You have duplicate data.

There are two positions associated with each Piece. One position is a member of the Piece class. The other is the key in the map for the board. If those fall out of sync you will run into all sorts of problems.

This:

b.swap(b.at({2, 1})->pos, {2, 2});

causes them to fall out of sync, because now the Piece thinks it is at position 2,2... when really, the board has it at position 2,1 in its map.


The only sensible solution here that I can think of is to remove the duplicate data. I would remove Piece's position here and let the board own its position.


2) This is extremely suspect:

bool operator<(Position const &a, Position const &b)
{
	return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}

How exactly do you expect this to work? I don't think it works the way you expect it to.

EDIT: unless there's some mysterious tuple comparison rules that I'm unaware of. Admittedly I'm not super familiar with how C++ tuples work.

[MiiNiPaa]

In first case you are passing references to temporary objects and in second one first argument is a reference to an actual parameter which changes inside function.

If argument cannot be changed because of const reference it still can be changed through some other reference/pointer. I learned it hard way.

unless there's some mysterious tuple comparison rules that I'm unaware of

For n ranged from 1 to number of arguments: if nth arguments is not equal return lhs<n> < rhs<n> else increase n.

[Disch]

Aha. That's nifty @ MiiNiPaa

[LB]

@Disch I'd like to know how a piece may be aware of its position then? This has been bugging me too but I don't know how to fix it.

Though you're slightly off - the code does properly swap the pieces and their internal positions are correct, it's just the output that is wrong.

MiiNiPaa hit the nail on the head. We both learned it the hard way. And yes, #2 is a common idiom in C++11 now, it works perfectly fine.

[Disch]

Ah... right... because Board::swap is updating the internal positions. I missed that.

I'd like to know how a piece may be aware of its position then? THis has been bugging me too.

Does it need to be? The position is worthless without a Board... and the pieces don't seem to have access to the Board (unless you just omitted that for this example). Regardless, any logic that needs the position could have it passed in as a parameter.

Two-way relationships like this are tricky. I try really hard to avoid them.

[LB]

In ChessPlusPlus, the pieces are aware of the board they are on (and they have to be). They have to know their position to calculate their moves (they could be affected by their position, the position of other pieces, the shape and size of the board, etc). I can't pass that information as parameters to the functions because some pieces have a state that changes depending on what happens to them.

[MiiNiPaa]

I agree with Disch. Pieces should probably only know and tell how they can move and subscribe to different Strategies which will add or remove some move possibilities (like 2 sqares move or castling). Board should make restriction on moves (no moving through pieces, no moves when the king is checked unless said move eliminates check, etc) and manage pieces position.

[LB]

That severely limits the modularity then -I've got imaginary pieces that would just be impossible with that, and no new ones that would be possible. I do still have a lot of refactoring to do though, so maybe I can figure something out.

[MiiNiPaa]

Whichever solution you come wuth still cannot represent some pieces somebody will come with: can your representation hold two pieces in the same square?

I believe that with move class which describes possible moves and extendable piece class with virtual getMoves() method, almost all move designation could be handled.

[LB]

Moves aren't as simple as 'these are places a piece can go to' unfortunately - some movements can be blocked by other pieces, other movements are excluded from this restriction, some movements can only happen in certain conditions, etc. Not only that, there's also cases where pieces can be captured from a different position than the one they occupy (e.g. en passant).

For a long time I have been considering a variety of solutions to this problem. The current solution I have works but as Disch points out, it's not very tight - it's easy to have the self-aware position and the actual position go out of sync, and that would result in strange behavior and possibly even crashes.

One thing at a time though - right now I am debugging why black pawns can't capture diagonally down right.

[o1vk4iN6]

This thread is guilty !

[LB]

By that logic, it must be proven innocent. Let's throw the server in a fire: if it burns and this thread is left, it's not guilty. If it burns and this thread is not left, then it is guilty. We can make a class SalemServerTrial to do this automatically whenever we're suspicious of a thread.

Back on topic, I'm still taking into consideration suggestions for a better design ;)

[o1vk4iN6]

Well there's already a lot that's been suggested..

Moves aren't as simple as 'these are places a piece can go to' unfortunately

You can add rules to the moves:

In order to be able to move here, position a, b and c need to be empty.

or

In order to be able to move here, enemy unit must be here (for the pawn)... etc etc..

At least that way you won't need to pass the board to the pawn, though I don't really see a reason why you can't.

[giblit]

Is there someone going around reporting every post on this forum or something? There should be a limit or something..

[LB]

Reporting posts that aren't in violation of forum rules is harmless besides making our beloved twicker work too hard.

[jwkNwA7f]

How does it make him work? Does he check to see if it really needs to be deleted, and it not, he allows it to be seen?