12 ms·
Is abstraction overrated in programming? Chess, interviews and OOP
- JoeAltmaier 9y agoReminds me of an old contest - the 8 Queens problem, posed by Byte Magazine in the '80s as a programming contest. 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.
- ifdefdebug 9y agodont think because its easy for you, it must be easy for everybody else. that thought held me back for quite a while until i recognized it was bogus.
- perl4ever 9y agoI entered a programming contest once, where the task was to take some input and construct an optimal solution to a geometric problem. I got irritated at the rules not being clear and well thought out, and I wasn't smart enough to work out a good implementation of the real-world algorithm they were hoping contestants would come up with. So I wrote code to provide pretty much the stupidest (most trivial) possible solution that fulfilled the specific constraints for a valid output that were stated. Because entrants were scored on a combination of speed, code size, and quality, my entry came in a close second, because it was by far the smallest and fastest. I kicked myself for not trying harder to optimize the quality even a little bit above "braindead".
- payne92 9y agoOh Dear Lord. Programming IS abstraction. In fact, that's pretty much ALL programming is: using, defining, and implementing abstractions.
- rhizome 9y agoThere's a difference between overrated and worthless.
- Veedrac 9y agoA definition which doesn't differentiate is a definition which provides no information. If your terminology is broad enough to encompass everything, it's also too broad to tell you anything.
- qznc 9y agoDefining a function is already a mechanism of abstraction. You take a snippet of code and give it a name. Usually you generalize by adding parameters. Maybe you can even make it generic (C++ templates, Java Generics, Haskell typeclasses, etc). Removing the abstraction of a function means to inline the code. You could do that manually (copy&paste). I wrote more on this here: http://beza1e1.tuxen.de/precise_abstractions.html http://beza1e1.tuxen.de/precise_abstractions.html Abstracting is not everything there is to programming, but modern code consists nearly completely of abstractions.
- coldcode 9y agoUnderstanding the problem > any abstraction you pick without understanding the problem first. In this case chess was a terrible choice for an interview. In chess the biggest issue is tree size. If you don't start there then no abstraction will ever save you.
- ZirconiumX 9y agoI'm going to disagree with you here. In chess the problem is not about reducing the tree size: you can get a "tree" by picking random moves. The problem is about reducing the tree size intelligently. My chess program - Dorpsgek - has an 800 byte board structure (though I recently reduced that to about 400). It uses techniques that the computer chess community considered to be impractical. But still it works, and it works because the space that I use per board contains very useful information, such as attacks to a given square. The advantage that bitboards give are not space by any meaningful quantity - for an alpha-beta search of depth d with a branching factor of b you will allocate at most d boards - or even 1 board - at any given node, not b^d boards. The advantages that bitboards give are speed and information density. And to anybody who thinks that a bitboard approach is not sufficiently generic for different board sizes, wrap the bitboard using an arbitrary size bit set and the problem is essentially solved.
- jstimpfle 9y agoI have no idea what abstraction actually is. It seems to me it's never abstraction unless it leads to complicated designs for the simplest problems. I've been accused of hating abstraction because I wrote in C instead and programmed out my own concepts -- instead of just using a ready-made framework with ill-fitting ones (Qt in that case). 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.
- mabbo 9y agoAbstraction, to me, is not about reducing lines of code but reducing cognitive load by hiding complexity. I don't need to know what kind of list, or how the list is implemented, I just need to know it's a list of some sort and has the usual list interface. For example, I recently needed to randomly reorder a collection of objects, weighting some of them more heavily than others such that 'heavier' objects are more likely to come first. My first implementation was a mess, and was hard to test. So I created an abstract data structure that allowed inserts with weights and polls for a random value, applying the weighting. My business logic could use that abstract thing presuming it worked. The tricky part was hidden, and the code was cleaner. In the case of the article, the abstraction the interviewer wants doesn't actually make the code clearer. It's just looking for checking off check boxes that the candidate wrote the word 'class' and jumped through the hoops the way the interviewer expected.
- Veedrac 9y agoIMO, the key issue is to differentiate between abstractions in language-space and abstractions in problem-space. Turning a chess board into an object is language-space, since it affects vocabulary; writing a function to count the pawns is problem-space, since it defines a step towards the problem one wants to solve. Nobody programs without problem-space abstractions any more; this is effectively what you get with functions and libraries. When someone uses a prebuilt tangent function, that's working in problem-space. Language-space abstractions don't pull the same weight. If they did, Haskell programmers would be so much higher productivity than C programmers that the latter would be simply competed out of the market. Instead we see marginal benefits against marginal costs, and the gamut of C, C++, Go, Haskell, Python, Javascript, etc. are, if not equally good, at least sufficiently similar that there is genuine debate. If in doubt, abstract the problem. If you do an abstraction and don't have less work to do afterwards, maybe you've abstracted the wrong thing.
- xiphias 9y agoAs an example of a good abstraction regarding chess, a deep learning algorithm that wasn't hand tuned specifically to chess just beat the best computer chess player that had a hand tuned algorithm (in which case the neural network representation of the board performed better than bit representation)
- tel 9y agoThe Bitboard is very abstract. The interface it instantiates will likely not let leak it’s concise internal representation and will discuss the operations on the game state at a domain level. This is abstraction. 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.
- qznc 9y agoOO design is often about the tradeoff between over-engineering and over-specialization. The rules of chess can usually be assumed to not changed, which is different to most programming tasks. If you would design for Chess 2.0 and you expect some game designers to change the rules every week (thinking up new kinds of pieces, changing the rules for existing pieces, changing the board layout, etc), would you still use Bitboard? Maybe it would be better to focus on the "nouns" the game designers use and keep optimizations like BitBoard in mind for later?
- tel 9y agoThe point of abstraction is to not be tied to Bitboard--or any concrete representation whatsoever. Chess 2.0 changing its rules is exactly what can be protected against.
- qznc 9y agoYes in theory. In practice, if code uses a Queen object, you put costly indirections in front of the Bitboard and thus already lost performance.
- tel 9y agoYou assume a Queen object and also some compiler details. These might be in practice relevant some of the time but (a) how often, really? And (b) are those forced decisions or decisions of convenience and momentum? Fwiw, as soon as you say “object” I’m betting you’re taking on expensive, unnecessary OO mental modeling.
- jancsika 9y agoThe class-based solution provides more information about the developer's approach than the single struct for the BitBoard. 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?
- johnfn 9y agoThe OP has translated the interviewers question of "design a readable and maintainable abstraction for a chessboard" into "design the most space-optimized chessboard possible", then wonders why the interviewer doesn't like his solution.
- smallnamespace 9y agoOr maybe the OP understood that everyone who has ever implemented a chessboard are also building chess engines where memory efficiency and speed actually matter a lot. It's the interviewers who are ignorant here, they took a real problem and translated it badly into a toy problem. Then they failed to realize what they did.
- inopinatus 9y agoGP is correct. The Quora answer has a false dilemma that you've just perpetuated here, viz. that an OO program cannot use a compact representation. But there are standard patterns for using a compact representation of data for domain-model objects. The article's author isn't just unaware of them, they've written a petulant, arrogant article demonstrating their own lack of experience and adaptability.
- loup-vaillant 9y agoI'm interested. Care to elaborate how an OO approach could yield a compact representation in this particular case?
- rrobukef 9y agoA facade wrapping the representation would sufficiently transform the paradigm?
- lozenge 9y agoThey could be building an online social game site, or implementing a UI but using an existing AI. In which case the OO version will be easier to code, understand, render, and render history in chess notation. The only thing his methods is good for is implementing an AI and serialization.
- moomin 9y agoI’m a bit concerned with the bitboard representation. What happens when a pawn takes another piece? Edit: The above is what I would say if someone presented this approach in an interview.
- cdevs 9y agoI'd like to see the rest of this implemented. What does this global functions look like? Are they swamped with if statements "I hope not" or are you storing some game logic in structs to replace polymorphism. I don't disagree with with the compact pawn struct as a starting point but to further prove your point I would love to see the rest / pseudo code.
- fastcum 9y agostockfish is an open source chess engine that uses BitBoards https://github.com/official-stockfish/Stockfish/ https://github.com/official-stockfish/Stockfish/
- qznc 9y agoLet's say black pawn takes the white queen: Unset the bit representing this black pawn, set the bit where the black pawn is now, set the white queen long to zero. One load and two write operations to memory. The bit fiddling is probably neglible in terms of time on a modern CPU.
- cglouch 9y agoin case anyone was curious how a bitboard chess engine works, I wrote one from scratch in python and included a writeup describing my general approach (mostly focused on the move generation aspect): https://github.com/cglouch/snakefish 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!)
- mratzloff 9y agoThat was really interesting. Thanks for sharing!
- c22 9y agoI don't know why he wants to waste so much space with twelve unsigned longs when he can do it in eight (one for each piece and two more masks for color).
- cma 9y agoWhy waste space representing illegal positions?
- c22 9y agoFor that matter, why store the chess board at all when you can just implement checkers?
- Const-me 9y agoI don’t know why would you both want to waste so much space? A cell is either empty, or contains one of the 12 figures. To store 13 values, you need 4 bits per cell i.e. 256 bits for the complete board. That’s 4 unsigned longs.
- c22 9y agoColor is still binary and there are at most 32 pieces on the board, so why not 3 bits per cell and a 32 bit lookup for color? Only 224 bits!
- JoshuaDavid 9y agoIf you're going to go that far, you might as well use 64 bits to say whether each square contains a piece. There are a maximum of 32 pieces, and for each (potentially) occupied square there are 12 possibilities for what might be there (not counting "nothing" as a possibility in a square since that's already covered by the 64 bits indicating whether each square is occupied), which can be represented in 4 bits per square. So that's 64 bits to say which squares have pieces, plus 32 * 4 = 128 bits to say what is in each occupied square, for a total of 192 bits to store the chessboard. You can take it even further, too. For the 32 possibly occupied spaces, you can encode what is in them as a 32 digit base 12 integer, then convert to binary, which is guaranteed to fit in 115 bits. So you can get away with 115 + 64 = 179 bits.
- hota_mazi 9y agoIt seems nuts to me that anyone would expect the Queen class to extend Bishop just because they happen to move diagonally. A Queen "IS NOT A" Bishop. 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).
- qznc 9y agoYes. A similar way to argue is Liskov's substitution principle [0]. It is easy to come up with properties that always hold for bishops, but not for queens. For example, bishops never move from black to white fields or vice versa. [0] https://en.wikipedia.org/wiki/Liskov_substitution_principle https://en.wikipedia.org/wiki/Liskov_substitution_principle
- jgalt212 9y agocomposition over inheritance https://en.wikipedia.org/wiki/Composition_over_inheritance https://en.wikipedia.org/wiki/Composition_over_inheritance
- hota_mazi 9y agoNo, my observation has nothing to do with composition vs/ inheritance. It's about defining what a class IS vs/ what a class HAS.
- mikekchar 9y agoIt's hard to ask this question without sounding snarky, but I hope you will understand that I'm seriously curious to hear what you think. > No, my observation has nothing to do with composition vs/ inheritance. > It's about defining what a class IS vs/ what a class HAS. What do you feel is the difference between these two sentences? In other words, why is inheritance vs composition not the same as what a class is vs what a class has?
- hota_mazi 9y ago
- petters 9y agoWhy do all the boards need to be kept in memory during the search?
- qznc 9y agoNot really necessary, but the primary goal is to make the search fast. Storing the boards elsewhere would probably be slower.
- lozenge 9y agoHaving read a python implementation of bitboards in the thread, I believe it's for search pruning. If you search many of the boards after three moves, then there will be some duplicates. Preferably each board should only be evaluated (for which player it favours) once and that can be done by storing them in a hash table or similar structure, which requires storing the board.
- wellpast 9y agoI can relate to the pain of going through an interview knowing that the interviewer is expecting a specific approach/answer (an OO answer!) that my hard-won experience has already long ruled out. And morals and/or my sense of identity — and/or a fear that the Gods are watching — refuses to allow me to play the interviewer’s game (at my own practical loss).
- agarden 9y agoI don't quite understand. If I were interviewing the OP and asked this chess question, then got his answer presented much like it was on Quora ("Well, the thing to understand about representing a chess board is that if you want to build a usable chess engine, the size of chess board representation is a critical constraint..."), I would be impressed. Hire that guy. He understands that the important thing is to figure out the solution constraints. On the flip side, if the interviewer learns something from you in an interview and that means he doesn't want to hire you, aren't you glad to have escaped that work environment? Assuming, of course, that the interviewer is representative of the people you would be doing actual work with.
- wellpast 9y agoI agree w/ you. So in that sense it’s not truly at my loss—that part I was being (somewhat) rhetorical about. However it has definitely been the case where I’ve contended with some Senior Engineer who has found the light in OO programming, inheritance, Template Method, etc, etc and no amount of dialectic will change his mind. This programmer often doesn’t see the severe impedance that his OO code, his type hierarchies, etc are causing to agile delivery of the new and newer software. How do you show an OO-religionist...the light, so to speak? These quesitions are not easy to get into a lab and give him the hard numbers. Just an example here: Matrix algebra is easiest done with first-class matrix abstractions. So my compeer puts everything into some other abstraction. And I say, look, look how much easier it is to do our work when our data is modeled differently? And he says “that’s not easier” — okay, you are objectively right, but your peer doesn’t “see it” or refuses to see it, or what, I don’t know— but this is almost de facto industry situation—you can’t prove that your ergonomics are better because your peer doesn’t even speak in proofs anyway. Now I could go find another job but my equity is actually worth something here (it really is), so I put up with it. But it’s frustrating nevertheless-and having a better abstraction only costs my coworker to learn something. It’s not going to make my equity any less valuable—might make it more valuable, if anything.
- Chriky 9y agoIs this for real? The solution he proposes is specific to Chess! 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
- inopinatus 9y agoThe guy is openly arguing with an interviewer after taking a question too literally. I suspect my interview impressions would've included "candidate may be on the spectrum". However, this entire thesis is founded on a false dilemma, because you can write an OO domain model with a compact representation.
- fjdfhdjldj 9y agowhy the onus is not on the interviewer? Why is he bringing up chess if he just wants OO answers? Aren't there better problems to pose more suited for testing OO knowledge? Bitboard is a standard way of writing chess engines. I think most would agree that a good programmer is one that seeks the best solution, not one that follows dogmatically his preconceived ideas.
- christophilus 9y agoYeah. Based on the HN comments, I went into this article expecting it to be an uninformed tirade. I came away from the article thinking, "I'd hire that guy immediately." The interviewers are definitely using the wrong problem if they're trying to test knowledge of OOP.
- inopinatus 9y agoBecause you can write an OO domain model using a bitboard representation. It's an opportunity to demonstrate advanced OO knowledge, which this Quora answer most definitely fails at.
- wellpast 9y agoThe CPU does not care about your abstractions. Abstractions are entirely wrt the human dealing with them. A good abstraction is only “good” with respect to some context/purpose—there is no such thing as a universally/generally good abstraction. And often a “great” abstraction will hurt your performance — so then is it so great? 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.
- qznc 9y agoImho an abstraction by itself can be incomplete or unsuitable [0]. If it is neither, it is a good abstraction. I concede that suitability is often hard to quantify. What you describe with algebras, I would label the "precision" [1] of an abstraction. Precise abstractions/algebras require a good specification though and that is often missing in the business domain. [0] http://beza1e1.tuxen.de/leaky_abstractions.html http://beza1e1.tuxen.de/leaky_abstractions.html [1] http://beza1e1.tuxen.de/precise_abstractions.html http://beza1e1.tuxen.de/precise_abstractions.html
- valuearb 9y ago“But first of all, the OO inheritance here is irrelevant. The queen is the only piece which actually “inherits” properties from other pieces! We don't need an object model to simply reuse some functions to calculate legal moves given a position. Just a few global functions.” 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.
- fjdfhdjldj 9y agobut then why use OO? what does OO offer that this method does not? In fact one could argue that this method offers better decoupling since it separates the rendering from the game Data.
- valuearb 9y agoYou use OO because your interviewer wants an example that demonstrates you understand it. Secondly, OO is more easily extensible. If the company wants the game to support other size boards, bit wise storage has to be ripped out. 90% of the work in 90% of the jobs is writing clear, easily maintainable and extensible code, not maximizing performance. Frankly, if I interview someone who answers a question like OP, i pass thinking their code will be a premature optimization nightmares.
- christophilus 9y agoExcept, this is not premature optimization. Chess programs are a domain the author is familiar with. He goes out of his way to explain why-- based on his experience-- chess code should be written with space-optimization in mind. Secondly, if you want to support non-standard boards, his solution requires a small tweak (depending on the language): long -> bigint and some parameter to denote board size.
- valuearb 9y ago
- simonhamp 9y agoDon’t design the abstraction; derive the abstraction from your design if/as it naturally becomes apparent. That way you’ll end up with something that works much sooner, instead of getting caught up in designing layers of abstraction.
- fastcum 9y agofor the ones interested here is a great resource list about bitboards in chess https://chessprogramming.wikispaces.com/Bitboards https://chessprogramming.wikispaces.com/Bitboards
- ZirconiumX 9y agoMy opinion is that this post reaches the same conclusion as I would, but I disagree with the logic behind it. 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.
- _yawn 9y agoThe whole point of abstract data types is to separate implementation from interface in order to allow a change in representation. 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.