16

I am trying to design a Chess Game using OOPs concepts that has a UI element to it. My idea is to show the number of squares / cells a piece can travel to when selected. Basically I want to show the paths / directions in which the it can travel / attack in a different color.

Some thing like the following

(enter image description here)

So I have designed an abstract Piece class, which among others, has a Map object that keeps track of all the cells to which it can travel direction-wise, something like this Map<Direction, LinkedList<Cell>>

Now, say a Piece of the Queen's own team comes in its way of attack in the FORWARD direction and puts itself on the cell that's located at chessBoard[6][4]

What best way can I notify the Queen or any other piece watching that particular cell of the event so that each piece can call its own update method and redraw its path of attack?

I was thinking of going with the Observer pattern where every cell will be a subject and only the pieces watching them will be observers. So in any case anything happens in any of the cells watched by a particular set of pieces, only those pieces will be notified.

But then I am not sure if this is a good approach as I have to have at max 32 listeners for every cell. Not sure if it will be scalable at all.

Are there any better ways to do it?

Thanks for taking the time to read.

Auro
  • 291
  • 2
  • 5
  • Even if you did go ahead with the design you describe, it will only allow the queen to remove 6,4 from the locations it can move. You would then need to decide how to remove 7,4 and 8,4 also. Once you get that far along you will probably decide this scheme is not making your job any easier. – Aaron Dec 09 '19 at 22:23

3 Answers3

43

Having a "Map object that keeps track of all the cells to which it can travel" looks to me like an example of premature optimization.

Instead of remembering all those cells for each piece "just in case it could become slow", why not give a piece a method with the board as parameter, which returns the related List<Cell> (or Map<Direction, LinkedList<Cell>>) by calculating it when the method is called? This way, no notifications or observer pattern or "32 listeners" are needed any more. It may be debatable if it should really be a method of the piece, or a method of the board. However, if you put this method into the board instead of the piece, pieces will not have to know anything about the board, so this avoids a cyclic dependency between boards and pieces.

If it turns out later that this method is called quite often for the same, unchanged board so it becomes a performance bottleneck (which I doubt), you can still cache its results using memoization. That would lead to a solution where a Map<Direction, LinkedList<Cell>> per piece is required, but without the necessity of actively observing other board changes.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • 7
    +1 for keeping this simple. Another advantage is, that if using clean code, it can make the game rules pretty obvious from looking at the implementation of the method. Can you guess which piece's rules are implemented here: `public canMoveTo(x,y) { return (this.straightLineTo(x,y) || this.diagonalLineTo(x,y)) && this.distanceTo(x,y) == 1); }` – Helena Dec 08 '19 at 10:31
  • 4
    My partner and I won an AI chess tournament using the "pass the piece the board, and it's location" method to generate the pieces posible move list. The only use we had for the observer pattern was the one built into the UI itself. We could play chess at the console without any observers at all. What won it for us was doing a crazy amount of testing. – candied_orange Dec 08 '19 at 13:00
  • 2
    Our board was an array of references to piece objects (or an empty space object). To support castling and en passant the board also has to hold a little state info beyond current piece location. – candied_orange Dec 08 '19 at 13:19
  • 2
    If you want to write an optimizing chess engine where performance matters, using objects strikes me as completely untenable. So the optimization wouldn't even help since you'd have to rearchitecture the whole thing anyhow. At least I can't imagine any modern chess engine to not use bitmaps of some kind for storing the board representation.You can store the whole board state in about 100 bytes that way. – Voo Dec 09 '19 at 12:30
  • @Voo: from what is written in the question I would expect this board representation to be used in the front end / UI of a chess game. A backend (like a chess playing AI) may use a completely different representation for board and pieces. – Doc Brown Dec 09 '19 at 14:09
  • @Doc Could be, but my main point is "the given representation is already that inefficient that optimizations for it just don't matter". – Voo Dec 09 '19 at 14:13
  • 2
    @Voo using objects is hardly untenable. We used objects and generated moves faster than anyone else. How? We used construction of objects as a way to set immutable state that configured the methods. Just as functional as a closure. We had one pawn class. We only ever constructed two pawn objects (black and white). We copied references to those pawns into the board. Do this with all your pieces and you know exactly how much memory you're allocating when you build a board because it's just references. If the empty space piece responds with an empty list you can blindly loop the board for moves. – candied_orange Dec 09 '19 at 17:39
  • @candied What ELO rating did your engine achieve when playing against state of the art engines? I'm not saying you can't program a chess engine with objects (hell I wrote one in Prolog years ago), I'm saying if you want to write a high-level optimized engine getting rid of the object overhead just makes sense. All those indirections, awkward copying, bad cache utilization. complicated incremental updates if you want to reuse objects,. But I haven't tried to write a high performance engine with this approach, so I might be wrong - it just doesn't seem to offer many advantages. – Voo Dec 09 '19 at 17:54
  • low level hand optimized code will always have it's place. But high level just in time 'that what the virtual machine is for' optimizations are making it harder and harder to beat. It's rarely the language or paradigm that does you in. Over and over it's your data structure. – candied_orange Dec 09 '19 at 18:06
  • Friends, this discussion is drifting more and more away from the OPs question - the chatroom would be way more appropriate for this. – Doc Brown Dec 09 '19 at 18:11
  • 1
    @Helena That looks like a queen with broken legs to me. :D – Mateen Ulhaq Dec 09 '19 at 18:28
  • @candied_orange This is not about "hand optimized" code. This is about optimizing memory accesses and cache utilization, which is a much higher level concept - and something the JVM absolutely cannot do for you. You can do many of these things in Java, but it's rather cumbersome. Oracle has been working for years on getting value types into HotSpot (Project Valhalla), exactly because of the optimization benefits while keeping code readable. See e.g. John Rose's summary [here](http://cr.openjdk.java.net/~jrose/values/value-type-hygiene.html). – Voo Dec 10 '19 at 12:29
22

My suggestion is to make things as simple as possible. The more information you give to an object, the more complex it becomes, and the harder it is to keep track of it.

Let's break your program down into layers. What is there?

  • The pieces. They only know what kind of piece they are, and what color they are (black or white)
  • The board. It knows only about the pieces and how they're arranged.
  • The game state. The game state knows about the board, and also about extraneous information such as captured pieces.
  • The UI. The UI knows about the game state. It also knows about any graphics information like sprites.

The Pieces. A piece is... just a piece. It has a color, and a type (rook, king, queen, etc), but that's it. It can answer:

  • What am I? (Rook, King, Queen, etc)
  • Which side do I belong? (Black, White)

The Board. A board is just a 2D array where cells either do, or don't, have pieces. It can answer:

  • Where are the pieces?
  • Where are the empty squares?

In addition, based on the current state of the board, we can ask it to calculate:

  • What squares can be attacked by the piece at a particular location?
  • Is a particular piece in danger?
  • Is the King in Check?
  • Is a proposed move legal?

Example: Take the move B3 to A4.

  • If there's no piece on B3, it's illegal.
  • If the piece can't move diagonally, it's illegal.
  • If A4 is occupied by a piece of the same color, it's illegal.
  • If the King is in Check and the move doesn't protect the King, it's illegal. And so on.

The game state. The game state keeps track of what's happened so far in the game, along with the current state of the board. This includes:

  • What the board looks like now
  • History of moves (Like "Queen takes B4")
  • Who has captured what pieces
  • Whose turn is it?

The UI. Tbe UI is responsible for drawing the game state and the board. We can ask it:

  • How do things look? (What sprites or graphics primitives are used to draw a piece or the board?)
  • Where should I draw stuff?
  • When should I draw stuff?

The UI should be the only one that handles events. Pieces don't handle events. The game state doesn't handle events. Nor does the board handle events. When an event happens, the UI:

  • Checks if whatever happened was legal
  • Updates the game state if the thing was legal
  • Draws the updated board (and any associated update animations)

How do I do things, like highlight possible moves? When a user mouses over the board, the UI

  • Figures out which square it is
  • Gets the board from the game state
  • Asks the board what squares can be attacked by that piece.

This final question can be implemented in the form of a member function of the board that takes a position as input, and returns a list (or array) of positions that can be legally attacked.

Why use this approach? Every field, every property, every member that you add to class adds state. Every bit of state is something you have to manage, keep track of, and update as necessary. The code becomes a mess, and making changes is hard because one small change suddenly requires you to modify a dozen different classes.

Calculating a list of legal moves based on a 2D array of pieces is a lot cheaper than continually updating a Map<Direction, LinkedList<Cell>> for every piece. It'll be less code, too.

By breaking apart the program into layers, and giving each layer a single responsibility - to control the layer under it - we can write a program that is clean, efficent, and modular.

guntbert
  • 109
  • 3
Alecto Irene Perez
  • 513
  • 2
  • 6
  • 1
    You are building your design based on what things *know*. Note that you mostly express your design in terms of questions things can answer. That is **not OOP**. In OOP, things have *behavior*, i.e. things do stuff instead of just knowing stuff. Knowing stuff is also **not a responsibility**. – Robert Bräutigam Dec 08 '19 at 12:56
  • 8
    @RobertBräutigam: `Knowing stuff is also not a responsibility` - I disagree with this statement, in fact, the primary responsibility of an object is to ensure that that its state (i.e. what it knows) is always valid. A chess piece has no intrinsic behavior besides its properties. What moves are legal depends on the state of the board and even on the variant of chess you are playing, and trying to stuff this "behavior" into the piece actually leads to a more complicated design. – casablanca Dec 08 '19 at 20:01
  • 3
    Dividing up state is an important part in any program; the "what X knows" is an exercise to decide state location and reduce unnecessary dependencies. Having a class be responsible for a certain piece of state and enforce/query invariables is a form of encapsulation, which is a big part of OOP. – Rimilel Dec 08 '19 at 23:46
  • 3
    @RobertBräutigam OOP is about putting both State **and** Behavior in the class where it belongs. Since a pieces movement concerns both the pieces and the board, that information could go in either of those classes. The choice then depends on where you most expect it. Since a Piece probably shouldn't know about a board, but a board knows about pieces (and where they're placed) I find it a lot less surprising to let the board be responsible about knowing how each piece can change it's position on that board. – Imus Dec 09 '19 at 08:11
  • @casablanca "A chess piece has no intrinsic behavior..." - You seem to imply that is somehow universally true. It isn't. That is just one design approach you (and the answer above) took, but it certainly isn't the only one, and most importantly it conflicts with the central theme of OOP of having state *and* behavior in an object. Having *only* a state is called a "structure" and is part of a different paradigm. – Robert Bräutigam Dec 09 '19 at 18:33
  • 1
    @RobertBräutigam: I don't necessarily see a conflict here, the behavior just happens to be trivial in this case (tell me what kind of piece you are). You could certainly have `Piece` compute its own moves, but this introduces a new dependency on `Board` (more coupling). On the other hand, `Board` already knows about `Piece`s so putting this behavior there doesn't introduce additional baggage. This is also in alignment with pretty much every set of design principles including SOLID, GRASP and DDD. – casablanca Dec 10 '19 at 02:49
3

The other answers already responded how you could do what you asked for. I want only to point out here that neither OOP nor design patterns (yes, they are quite different things) should be used just for the sake of using them.

They are tools and, as such, they should be chosen according to the purpose you want to reach, not the other way around.

I can't grasp from your question if you need to make a chess program and has chosen to do it with OOP, or if you want to learn OOP and then choose Chess as a conduit for learning it.

If it's the latter, as I suspect, my suggestion is that you start with a lower bar, though.

Board games are as nice a way to learn OOP as many other, and better than most I've seen being used. However, I'd suggest you star with a simpler game, say tic-tac-toe, and then move up the ladder of complexity (maybe checkers, minesweeper, backgammon etc) until you reach chess and even more complex games.

If your goal is to learn OOP, the approach I'm suggesting would lead you to learn a lot of more concepts and practices than just how to do Chess over OOP.

Rodrigo Oliveira Perez
  • 39
  • 2