by toAnswerIt on 1/1/18, 7:14 PM with 146 comments
by JoeAltmaier on 1/1/18, 7:31 PM
All the solutions presented started by declaring an 8X8 board, with a 1 or 0 in each cell to represent a queen. Then there was some two-dimensional iteration over the board, testing if any queen was on the same row, column or diagonal as any other.
I'd dismissed that solution as inefficient from the start. Since only one queen can be in each column, I represented the board as an 8-element array with each element containing the row number of the queen in that column.
My 2nd insight was, only one queen can be in each row, so the elements of the board array were simply the numbers 1..8. The search consisted of permuting the digits, then testing for diagonals e.g. test pairs to verify abs(difference) != abs(i1-i2). That is, their row numbers were not the same as the difference between their column indexes.
Finally, when permuting, you could test the elements as you went and trim the permutation tree drastically if you found a failure. No sense permuting the right-most elements of the array if there's already a diagonal conflict in the digits placed so far.
The whole thing ran in trivial time. The contest winners ran in hours or days (this was all in BASIC on <1Mhz processors back then). Made me wish I'd actually entered the contest. But I didn't bother, I guessed many people would have found the same solution.
by hota_mazi on 1/1/18, 10:15 PM
If anything, specify traits that define the movement of the pieces and have each piece extend that trait (with the Queen extending both CAN_MOVE_DIAGONALLY and CAN_MOVE_LATERALLY).
by johnfn on 1/1/18, 9:18 PM
by Chriky on 1/1/18, 10:31 PM
I mean, does this guy really think the company cares about efficiently representing chess game states??
Obviously, obviously, OBVIOUSLY, the Chess aspects of this question are irrelevant. What they are trying to find out if how well you will work on their actual codebase, which is presumably not comprised of global functions operating on bitfields
by simonhamp on 1/2/18, 1:17 AM
That way you’ll end up with something that works much sooner, instead of getting caught up in designing layers of abstraction.
by jstimpfle on 1/1/18, 8:48 PM
A much better term than abstraction to me is "semantic compression" (got that from Casey Muratori of Handmade Hero). This basically means factoring out common bits with the goal to express the solution with the least amount of repetition (while of course taking care not to factor out parts which are only coincidentally common. I figure that's the "semantic" part).
To do semantic compression you need abstraction, but not pointless abstraction -- just the right amount.
by coldcode on 1/1/18, 8:36 PM
by wellpast on 1/1/18, 10:21 PM
by cglouch on 1/1/18, 9:32 PM
https://github.com/cglouch/snakefish
(I cheated a little by not implementing castling / en-passant since it's a pain, and my engine is still really slow, but hey it works!)
by tel on 1/1/18, 8:56 PM
So this is a failure of OO abstraction. Why? OO abstraction is really complex and makes many forced moves that provide little value here. Inheritance and a focus on “nouns” makes idiomatic code highly specialized to certain domain models. Unfortunately, these are rarely useful.
by wellpast on 1/1/18, 10:32 PM
But setting aside performance concerns, when we speak of a “good” abstraction we are usually (or should be) saying this is good for some purpose—good for readability, for example.
But even better—or of utmost importance in the real world-is this: is the abstraction under question “good for business”? And that is entirely asking this: does the abstraction allow for rapidly acting on business ideas, creativity, needs, etc.
However, I believe that once the context is fixed/agreed upon, that there is an objective answer to which of this or that abstraction is better. However experience in the practical world of today’s software development painfully has shown me that the “better” abstractions are harder to come by...and when “found”, don’t tend to stick. This is because most practitioners don’t have the ability to produce powerful algebraic systems (which is what “good” abstractions are—“alegebras” over a business domain) because practitioners are generally not mathematicians, even have a philistine dislike/disdain for powerful systems if they have a whiff of mathematical-like power to them at all.
In this sense one could argue for an abstraction being “good” with respect to the social context in which they are operated in (i.e., if your team members don’t understand how to correctly wield an abstraction, is that abstraction good?) However I don’t like these kinds of arguments bc a lesser system is still capped in its power even if all its users understand it.
There are limits in what you can do with, say, Euclidean Geometry, even if it is much simpler to understand than other Gemotries. An often retort to this is No it isn’t. But that usually comes form perspectives with limited imagination. That said, many businesses are fine and thrive with limited imaginations.
by ZirconiumX on 1/2/18, 2:02 AM
In a modern, state of the art chess program that uses alpha-beta with a branching factor b and depth d, you will have at most d boards allocated, or even 1 board allocated. Neither of those figures approach b^d. That makes board size largely irrelevant, except for the amount of memory copying needed, which for a d-board approach would be b^d copies (a single board approach would only mutate that board).
EDIT: One major issue I just noticed with the article is that the two differing implementations are not apples-to-apples equivalent. One uses bitboards, based around manipulation of bits, and another one is akin to representing the board with an array.
by valuearb on 1/1/18, 11:55 PM
Don’t all pieces have a location? Aren’t all pieces movable? Might we want to display pieces? Do we want to journal them to files to save game state, or their moves to streams to play remotely?
All of these things can be done procedurally, but they also fit nicely into an OO design.
by payne92 on 1/1/18, 8:20 PM
Programming IS abstraction.
In fact, that's pretty much ALL programming is: using, defining, and implementing abstractions.
by _yawn on 1/2/18, 2:46 AM
The point is to allow programming things like the AI algorithm without caring at all about if the board is represented with a hash map, nested arrays, or a bitboard. In all cases, all the AI cares about is move generation, not internal representation.
Abstraction does not hinder ideas like the bitboard, it enables them. Both the interviewer and the interviewee are missing the point.
by c22 on 1/1/18, 10:08 PM
by jancsika on 1/1/18, 9:16 PM
For example, where would the equivalent of "findMoves" be declared in the latter case? Is the bitmath abstracted out into a set of helpers, or is it done in one big function?
by petters on 1/1/18, 10:19 PM
by moomin on 1/1/18, 9:28 PM
Edit: The above is what I would say if someone presented this approach in an interview.
by fastcum on 1/2/18, 1:52 AM