Chess programming, Scala, JVM: How costly is dynamic dispatch?

My aim is to write a basic chess playing AI. It doesn't need to be incredible, but I want it to play with some degree of competence against people with some level of familiarity with the game.

I have a trait called Piece which has abstract methods canMakeMove(m: Move, b: Board) and allMovesFrom(p: Position, b: Board). These methods are important to the program logic for obvious reasons, and are implemented by the concrete classes King, Queen, Pawn, Rook, Bishop, and Knight. Thus in other places, say for example in the code that determines whether or not a particular board has a King in check, these methods are called on values whose type is the abstract type Piece, (piece canMakeMove (..., ...)) so the actual method called is determined at runtime via dynamic dispatch.

I'm wondering if this is too costly for the purposes of a Chess AI program which is going to have to execute this code many times. After looking around online and reading some more about chess programming I've found that the most common representation of a chess board is not like my Vector[Vector[Option[Piece]] but an int matrix ('bit board') that likely uses a switch statement on the values in the board to accomplish the effect that I'm currently relying on dynamic dispatch to achieve. Will this prevent my AI from reaching viable performance level?

Solution

I will suggest in this answer that you are subject to a common pitfall in programming. There is one very important wisdom that I learned from my colleagues, and it has proven its worth to me time and time again:

Only solve problems when they occur, and not any sooner.

Keep in mind that there have been chess programs and chess computers around for a long, long time. There were even chess programs on the C64, and there were those tiny travel chess computers that were embedded in the chess board, so you could carry them around easily.

Those systems had far less resources than your present day computer by several orders of magnitude. If you had a similar algorithm as the one that was running on those old systems, and that algorithm was implemented in Scala, with dynamic dispatch, generous vectors instead of bit arrays et cetera, they would still be faster than they were on the older hardware from the past days.

Still, writing even a moderate search heuristic for the chess problem is a colossal task for a single developer. When faced with a colossal task, one intuitively tends to look for the first bit of the problem that one feels competent in solving, in hopes that this will then naturally lead to the next little problem that you can solve, and so on, eventually leading to a full solution to the colossal problem. Divide and conquer.

However, my personal experience tells me that this is not a good way to tackle bigger programming problems. Usually, if you follow this path, you end up with a really, really optimized representation of the chess board, consuming only very little memory, and optimized for runtime as much as possible.

And then you're stuck. You have put all your energy into this, you're really proud of your great chessboard class, and somehow it's really dissatisfying that you feel no step closer to actually have a working chess AI.

That's where the rule that I mentioned in the beginning comes in handy. In short: Don't optimize. Yet. You can still optimize later, if it's necessary.

Instead, do the following:

Make a class or trait that represents a chessboard.
Leave it empty in the beginning - no methods or members.
Do the same with the types representing pieces, board positions, moves etc.
Then, when you start implementing the chess AI, fill in those types with methods. But only add the methods that you really need, and only when you need them, and not any single method more than that.
Prefer to use traits in the beginning, as you can later on produce more optimized versions of a trait, if necessary.

In that way, try to get as soon as you can to the first version of your chess AI that does something interesting. It's up to you to define what "interesting" means in this context.

It's okay if the first version of the chess AI is crappy, and loses every game because it makes really bad decisions. It should just have that one single thing: It should do something that you find at least remotely interesting.

Then, identify the top problem that you have with your chess AI. Think about how to solve it, come up with a plan that solves only that one problem, in the simplest way that you can possibly imagine, even if your programmer instincts tell you to do something more complex. Resist the urge to delve into complexity fast, because the most complex code that you write will eventually turn out to be your biggest problem, and also the most inflexible part of your code base.

Short, simple, almost stupid steps towards a solution. Prototype a lot, create simple versions in a short time, and only optimize when needed.

As for the optimization - that's really not a problem. For example, let's say that in the beginning you thought it's a good idea to define a board position like this:

case class Position(x:Int, y:Int)

Later on, you figure that it would have been a better choice to just use a tuple of ints to represent a board position. Simply substitute your previous definition with:

type Position = (Int, Int)

There you go. Do that change, compile the code, and the compile errors will show you all the places in the code that you need to adapt. It's not going to take very long to refactor this.

Even later down the line, you decide that since there are only 64 possible positions on the board, you can easily represent the position with a number in the range from 0 to 64 - reserving the number 64 for "off-board". Again, that's an easy change:

type Position = Byte

Save, compile, fix the compile errors. Should not take longer than 15 minutes.

With this example, I want to illustrate that you shouldn't be afraid of optimizing later, waiting to solve problems only when they actually occur. This will always require some refactoring, but the effort is usually not really worth mentioning. I tend to think of this as "massaging the code".

Of course we know that junior programmers sometimes tend to write "spaghetti code" that is very hard to refactor later. Maybe that's why there is a certain fear of late optimization that practically every developer knows, and the urge to optimize early.

The only real antidote against such "spaghetti code" is to go through this painful process several times. After a while, you will develop a very good intuition on how to write code that can be optimized and refactored easily. This will match all the common programming wisdoms, like separation of concerns, short methods, encapsulation and so on. At this point, I would recommend the book "Clean Code" as an excellent guideline.

Some more tips:

See your program as a bridge. You stand on one side of the bridge, starting off with nothing. On the far end, there is your vision - a decent chess AI. Between the ends, there is a gap. Your program will be the bridge. Don't start by putting all your energy into optimizing the very first brick that you put in your bridge. A bridge with just one perfect brick won't hold. Build a prototype bridge first - crappy, but it connects the two ends. When you have that, it's easier to enhance the crappy bridge step by step.
Abstract all the functionality into traits and classes. Be wary of code repetitions - when you find a bug or need to do a refactoring, repetitious code can be a neck breaker.
Don't be afraid to write code that doesn't look smart, as long as the code is simple and solves the problem. Bonus points for code that reads well and looks almost like an intuitive description of the algorithm.
Keep your methods short. One to six lines.
Make sure that your code doesn't nest too deeply - everyone with a bit of Scala experience should be able to understand what your code is doing.
It can be a good thing to spend some time in order to find good names for your concepts. Maybe there are even some standards of naming certain parts of a chess AI. It's good to do a bit of research first.
While you are researching, see if there are some Scala/Java libraries available that you can use, for important parts of your problem. You can still replace the libraries with your own implementations later, but in the beginning, using the knowledge of other people can give you a jump start into creating your first, prototype version "bridge". Everything that will help you close the "gap" quickly is good.
Don't think of your code as something eternal, perfect, unchangeable. Maybe you have the ambition to write the best representation of a chess board in Scala ever. Don't do that. Eternal, perfect code cannot be refactored or changed easily. Code that can be refactored easily is really good code. Refactoring code is 50% of what a programmer does.
Jump into automated testing. For Scala, using the scalatest library can be a good choice. Use a tool like SBT that will run all the automated tests on every build. If you have certain assumptions about the classes you write, hardcode those assumptions into automated tests. It will feel a little stupid and redundant at first. But the first time that one of your automated tests show you the cause of a bug that would otherwise have been very hard to find, all the time to write those automated tests will have paid out.
An advanced topic about automated testing is code coverage. You can use a tool that will generate a coverage report, how much of your code is covered by automated tests. From my own experience, I would recommend jacoco4sbt.
And finally, the mandatory citation: "Optimization is the root of all evil." - There is a lot of wisdom in this one.

Good luck, and a whole lot of fun!