My blog describing it is pretty sparse, sorry about that. Happy to answer any questions that folks have about the architecture.
Not that it was necessary, but I got really into building this out as a single process that could handle many (10k+/sec) moves for thousands of concurrent clients. I learned a whole lot! And I found golang to be a really good fit for this, since you mostly want to give tons and tons of threads concurrent access to a little bit of shared memory.
panic 1 hours ago [-]
If you don’t mind explaining, I’m curious how you test something like this before it goes live. It seems like it would be hard to simulate all the things that could happen at scale.
weiliddat 3 hours ago [-]
> The frontend optimistically applies all moves you make immediately. It then builds up a dependency graph of the moves you’ve made, and backs them out if it receives a conflicting update before the server acks your move.
The dependency graph is between pieces you’re interacting with? Meaning if you move a queen and are trying to capture a pawn, and there’s potentially a rook that can capture your queen, those 3 are involved in that calculation, and if you moved your queen but the rook also captures your queen at the same time one of them wins? How do you determine that?
eieio 2 hours ago [-]
Ah yes good question! Here's some context for you. First off, the way moves work:
(edit: I realized I didn't answer your question. If we receive a captured for a piece we're optimistically tracking that always takes precedence, since once a piece is captured it can't move anymore!)
* clients send a token with each move
* they either receive a cancel or accept for each token, depending on if the move is valid. If they receive an accept, it comes with the sequence number of the move (everything has a seqnum) and the ID of the piece they captured, if applicable
* clients receive batches of captures and moves. if a move captured a piece, it's guaranteed that that capture shows up in the same batch as the move
So when you make a move we:
* Write down all impacted squares for the move (2 most of the time, 4 if you castle)
* Write down its move token
* If you moved a piece that is already tracked optimistically from a prior not-yet-acked-or-canceled move, we note that dependency as well
We maintain this state separate from our ground truth from the server and overlay it on top.
When we receive a new move, we compare it with our optimistic state. If the move occupies the same square as a piece that we've optimistically moved, we ask "is it possible that we inadvertently captured this piece?" That requires that the piece is of the opposite color and that we made a move that could have captured a piece (for example, if you moved a pawn up that is not a valid capturing move).
If there's a conflict - if you moved a piece to a square that is now occupied by a piece of the same color, for example - we back out your optimistically applied move. We then look for any moves that depended on it - moves that touch the same squares or share the same move token (because you optimistically moved a piece twice before receiving a response).
So concretely, imagine you have this state:
_ _ _ _
K B _ R
You move the bishop out of the way, and then you castle
_ _ B _
_ R K _
Then a piece of the same color moves to where your bishop was! We notice that, revert the bishop move, notice that it used the same square as your castle, and revert that too.
There's some more bookkeeping here. For example, we also have to track the IDs of the pieces that you moved (if you move a bishop and then we receive another move for the same bishop, that move takes precedence).
Returning the captured piece ID from the server ack is essential, because we potentially simulate after-the-fact captures (you move a bishop to a square, a rook of the opposite color moves to that square, we decide you probably captured that rook and don't revert your move). We track that and when we receive our ack, compare that state with the ID of the piece we actually captured.
I think that's most of it? It was a real headache but very satisfying once I got it working.
weiliddat 3 hours ago [-]
> I use a single writer thread, tons of reader threads, and coordinate access to the board with a mutex
On this I found Go to be at the right balance of not having to worry about memory management yet having decent concurrency management primitives and decent performance (memory use is especially impressive). Also did a multiplayer single server Go app with pseudo realtime updates (long polling waiting for updates on related objects).
eieio 2 hours ago [-]
Yes exactly!
My goal with the board architecture was "just be fast enough that I'm limited by serialization and syscalls for sending back to clients" and go made that really easy to do; I spend a few hundred nanos holding the write lock and ~15k nanos holding the read lock (but obviously I can do that from many readers at once) and that was enough for me.
I definitely have some qualms with it, but after this experience it's hard to imagine using something else for a backend with this shape.
mdaniel 12 minutes ago [-]
> You can move between boards.
Evidently move between boards but not capture between boards :-( It's extra weird because it's not that the movement isn't projected (e.g. queen blue lines all point correctly across board boundaries just the lines always stop at every piece on the other board, regardless of color)
So, I guess as an exercise in scale, well done! As one million chess boards, caveat gamator
nomilk 2 hours ago [-]
Someone barricaded their king with about 40 rooks, I hopped in with a knight, and they immediately captured me (with their king), then plugged the gap with another rook so I couldn't do it again. That was amusing lol.
darepublic 31 minutes ago [-]
I was only able to move the black pieces. And I was able to move black consecutively on the same board. So I didn't fully understand. Are the rules being enforced or is it just updates.
I enjoyed the sc2 UI when selecting pieces
tantalor 28 minutes ago [-]
I saw a black piece moving around very quickly. Is there a secret way to move without clicking twice?
pmontra 2 hours ago [-]
It works well on my Android phone with Firefox. Well done.
Neat, though I expected every individual board to have "turns" - I didn't expect that I could just pick a random board, liberate the black queen, and have her clean up every single white piece on the board without my "opponent" getting to do anything in return.
eieio 3 hours ago [-]
oh huh, I'm not sure why this one made it to the front page and not the link to my site!
Anyway, yeah, I guess I could have gone with turns here but I thought that building a more realtime MMO thing where pieces could cross boards would be a little more interesting and novel. I also didn't feel like a version of this that was turn based would ever complete.
certainly a queen can go wipe out a whole board, but the game tries to place you next to other active players when you join, which hopefully promotes some interesting counterplay to that. And I think playing chess in realtime like this against someone is pretty fun. But I understand why it might not be for everyone!
chunkles 1 hours ago [-]
Individuals here on hacker news tend to gravitate towards blog posts about games rather than links to actual games, generally. Not a hard fast rule, but it's what I've observed over the years.
JusticeJuice 2 hours ago [-]
I'd love to know what individual piece has moved the furthest from it's starting point.
tantalor 4 hours ago [-]
Agreed. It doesn't make sense. The game here is not to play chess, it is to find a board that has no other player and wipe them out as fast as possible.
krupan 3 hours ago [-]
Or it's just to have fun and create stuff. Already someone made board full of rooks and called it Rooklyn, and another person made a board full of queens and called it Queens
@eieio please open source the Go code, would be fun to poke at.
eieio 3 hours ago [-]
I'll certainly open source the code! I just want the flexibility to change my rate limiting logic in the short term to counteract abuse. Happy to answer questions though!
kinduff 1 hours ago [-]
I love this story so much.
NooneAtAll3 3 hours ago [-]
I made a Promoted-32 queen
I won
NooneAtAll3 3 hours ago [-]
herding around ~25 queens was also fun
building fortresses (since enemy can't cross board border by capture) is also. fun.
NooneAtAll3 2 hours ago [-]
theoretically there's a design for "indestructible" fortress
(rhoburb, you are a genius)
1) fill corner board with pieces
2) cover the border (from inside) with pawns
3) cover the promotion square on the border with the king
king can't exit the board, pawns can't walk backward to leave space, filler doesn't allow these 2 to make way
---
the real holy grail that will never be achieved I fear
My blog describing it is pretty sparse, sorry about that. Happy to answer any questions that folks have about the architecture.
Not that it was necessary, but I got really into building this out as a single process that could handle many (10k+/sec) moves for thousands of concurrent clients. I learned a whole lot! And I found golang to be a really good fit for this, since you mostly want to give tons and tons of threads concurrent access to a little bit of shared memory.
The dependency graph is between pieces you’re interacting with? Meaning if you move a queen and are trying to capture a pawn, and there’s potentially a rook that can capture your queen, those 3 are involved in that calculation, and if you moved your queen but the rook also captures your queen at the same time one of them wins? How do you determine that?
(edit: I realized I didn't answer your question. If we receive a captured for a piece we're optimistically tracking that always takes precedence, since once a piece is captured it can't move anymore!)
So when you make a move we: We maintain this state separate from our ground truth from the server and overlay it on top.When we receive a new move, we compare it with our optimistic state. If the move occupies the same square as a piece that we've optimistically moved, we ask "is it possible that we inadvertently captured this piece?" That requires that the piece is of the opposite color and that we made a move that could have captured a piece (for example, if you moved a pawn up that is not a valid capturing move).
If there's a conflict - if you moved a piece to a square that is now occupied by a piece of the same color, for example - we back out your optimistically applied move. We then look for any moves that depended on it - moves that touch the same squares or share the same move token (because you optimistically moved a piece twice before receiving a response).
So concretely, imagine you have this state:
You move the bishop out of the way, and then you castle Then a piece of the same color moves to where your bishop was! We notice that, revert the bishop move, notice that it used the same square as your castle, and revert that too.There's some more bookkeeping here. For example, we also have to track the IDs of the pieces that you moved (if you move a bishop and then we receive another move for the same bishop, that move takes precedence).
Returning the captured piece ID from the server ack is essential, because we potentially simulate after-the-fact captures (you move a bishop to a square, a rook of the opposite color moves to that square, we decide you probably captured that rook and don't revert your move). We track that and when we receive our ack, compare that state with the ID of the piece we actually captured.
I think that's most of it? It was a real headache but very satisfying once I got it working.
On this I found Go to be at the right balance of not having to worry about memory management yet having decent concurrency management primitives and decent performance (memory use is especially impressive). Also did a multiplayer single server Go app with pseudo realtime updates (long polling waiting for updates on related objects).
My goal with the board architecture was "just be fast enough that I'm limited by serialization and syscalls for sending back to clients" and go made that really easy to do; I spend a few hundred nanos holding the write lock and ~15k nanos holding the read lock (but obviously I can do that from many readers at once) and that was enough for me.
I definitely have some qualms with it, but after this experience it's hard to imagine using something else for a backend with this shape.
Evidently move between boards but not capture between boards :-( It's extra weird because it's not that the movement isn't projected (e.g. queen blue lines all point correctly across board boundaries just the lines always stop at every piece on the other board, regardless of color)
So, I guess as an exercise in scale, well done! As one million chess boards, caveat gamator
I enjoyed the sc2 UI when selecting pieces
Neat, though I expected every individual board to have "turns" - I didn't expect that I could just pick a random board, liberate the black queen, and have her clean up every single white piece on the board without my "opponent" getting to do anything in return.
Anyway, yeah, I guess I could have gone with turns here but I thought that building a more realtime MMO thing where pieces could cross boards would be a little more interesting and novel. I also didn't feel like a version of this that was turn based would ever complete.
certainly a queen can go wipe out a whole board, but the game tries to place you next to other active players when you join, which hopefully promotes some interesting counterplay to that. And I think playing chess in realtime like this against someone is pretty fun. But I understand why it might not be for everyone!
get the most kills, make a cool shape
or take a piece veeeeery far away from home
I wonder if something similar will happen here.
@eieio please open source the Go code, would be fun to poke at.
I won
building fortresses (since enemy can't cross board border by capture) is also. fun.
1) fill corner board with pieces 2) cover the border (from inside) with pawns 3) cover the promotion square on the border with the king
king can't exit the board, pawns can't walk backward to leave space, filler doesn't allow these 2 to make way
---
the real holy grail that will never be achieved I fear