HN user
https://glinscott.github.io
Thanks! Yes, some of the animations were created from this onshape model, which I rigged for motion: https://cad.onshape.com/documents/ebc9190f428cf30153c06148/w....
For other animations I put together a style guide and worked together with Fable to build them.
Author here. The beam engine created power from steam, and was a key part of the early Industrial Revolution. The article is a deep dive into the engine: how it works, the history behind it, and the engineering tradeoffs the builders faced. There are quite a few interactive figures that I hope make the concepts easier to see.
This is the second article in a series discussing modern compression techniques. The first one covered Huffman + LZ. This one covers optimal entropy coders (FSE and Arithmetic), and some additional tricks to get closer to the state of the art.
The full compressor and decompressor are just over 1500 lines of pretty compact C++: https://github.com/glinscott/linzip2/blob/master/main.cc.
It's been seven years since the first article! Hopefully not so long before the third (and probably final one).
Btw, some great books on Steam locomotives/engines:
https://www.amazon.com/gp/product/B07NQ9JG2M - American steam locomotives 1880–1960. The author of drove locomotives, and was the transportation curator at the Smithsonian Museum. He wrote it over 30 years, and you can tell the amount of care and detail he put into with the details and history.
https://www.amazon.com/gp/product/B003UYU1PC - How Steam Engines Really Work, provides a modern perspective on the important systems and concepts for steam engines.
https://www.amazon.com/gp/product/B072BFJB3Z - The Perfectionists: How Precision Engineers Created the Modern World. Talks about how precision engineering was critical to the invention and wider use of steam engines.
That's great. There is also this effort in New Zealand: https://mackwelloco.com/, focusing on "Modern Steam" techniques, with a small engine, targeting areas without easy access to diesel.
A good overview of modern steam techniques is here: http://advanced-steam.org/5at/principles-of-modern-steam/, where they focus on dramatically more efficient and clean burning engines. A fascinating rabbit hole to go down :).
Steam engines are fascinating pieces of technology. The page for the trust itself is full of interesting engineering details: https://www.a1steam.com/.
Their next project is to build Britain's most powerful steam locomotive, things are making good progress! Some high level details here: https://www.a1steam.com/prince-of-wales/about-prince-of-wale..., with a bunch more detailed updates on the build here: https://www.a1steam.com/prince-of-wales/about-prince-of-wale.... Started in 2014!
If anyone wants to experiment with training these nets, it's a great way to get exposed to a nice mix of chess and machine learning.
There are two trainers currently, the original one, which runs on CPU: https://github.com/nodchip/Stockfish, and a pytorch one which runs on GPU: https://github.com/glinscott/nnue-pytorch.
The SF Discord is where all of the discussion/development is happening: https://discord.gg/KGfhSJd.
Right now there is a lot of experimentation to try adjusting the network architecture. The current leading approach is a much larger net which takes in attack information per square (eg. is this piece attacked by more pieces than it's defended by?). That network is a little slower, but the additional information seems to be enough to be stronger than the current architecture.
Btw, the original Shogi developers really did something amazing. The nodchip trainer is all custom code, and trains extremely strong nets. There are all sorts of subtle tricks embedded in there as well that led to stronger nets. Not to mention, getting the quantization (float32 -> int16/int8) working gracefully is a huge challenge.
The great thing about these community driven efforts is that it is indeed feasible to reproduce these super expensive efforts. I'm a bystander now, as new maintainers have taken over, and they are doing a fantastic job pushing things forward.
This is also how Stockfish got to be the #1 engine. By being open source, and having the testing framework (https://tests.stockfishchess.org) use donated computer time from volunteers, it was able to make fast, continuous progress. It flipped what was previously a disadvantage (if you are open source, everyone can copy your ideas), into an advantage - as you can't easily set up a fishtest like system with an engine that isn't already developed in public.
Markdeep is fantastic. I wrote a fairly long article [1] with a lot of code samples, and it was so nice to not worry about formatting. The styling is elegant without having to try :).
MCTS is not a traditional depth first minimax framework. Key concepts like alpha-beta don’t apply. Although it is proven to converge to minimax in the limit, the game trees are so large this is not relevant. You could use the network in a minimax searcher, but it’s so much slower than a conventional evaluation function it’s unlikely to be competitive.
James put together a really nice summary of the ideas and the projects!
It was almost a year ago that lc0 was launched, since then the community (led by Alexander Lyashuk, author of the current engine) has taken it to a totally different level. Follow along at http://lczero.org!
Gcp has also done an amazing job with Leela Zero, with a very active community on the Go side. http://zero.sjeng.org
Of course, DeepMind really did something amazing with AlphaZero. It’s hard to overstate how dominant minimax search has been in chess. For another approach (MCTS/NN) to even be competitive with 50+ years of research is amazing. And all that without any human knowledge!
Still, Stockfish keeps on improving - Stockfish 10 is significantly stronger than the version AlphaZero played in the paper (no fault of DeepMind; SF just improves quickly). We need a public exhibition match to setttle the score, ideally with some GM commentary :). To complete the links you can watch Stockfish improve here: http://tests.stockfishchess.org.
If you are interested in compression at all, be sure to take a trip through Charles Bloom's blog [1]. It's an incredible read, he covers everything from the basics all the way through state of the art algorithms.
A great example is this post [2], where he talks about how to correctly implement a Huffman encoder/decoder. It's a lot tricker than it is made to sound in most books. For example, most Huffman codes that are used in practice are length limited, to allow the decoder to use smaller lookup tables. There are a bunch of surprisingly interesting tricks to get that to work well from the encoding side (which symbols do you choose to be smaller than they would be otherwise?).
[1] http://cbloomrants.blogspot.com/ [2] http://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffma...
We are going to start tabula rasa. The supervised learning is meant to prove that there are no major bugs in the framework/learning process.
Should be fun to watch it learn chess theory :).
Check out https://github.com/glinscott/leela-chess. We are getting close to kicking off the distributed version now that we have validated it's possible to get a strong network through supervised training.
A nice win against Gnuchess (a very weak opponent, but nonetheless :) - https://github.com/glinscott/leela-chess/issues/47#issuecomm...
We are using data from both human grandmaster games and self-play games of a recent Stockfish version. Both have resulted in networks that play reasonable openings, but we had some issues with the value head not understanding good positions. We think we have a line on why this is happening (too few weights in the final stage of the network), but this is exactly the purpose of the supervised learning debugging phase :).
There is a public distributed effort happening for Go right now: http://zero.sjeng.org/. They've been doing a fantastic job, and just recently fixed a big training bug that has resulted in a large strength increase.
I ported over from GCP's Go implementation to chess: https://github.com/glinscott/leela-chess. The distributed part isn't ready to go yet, we are still working the bugs out using supervised training, but will be launching soon!
There are a ton scattered around :).
Here is the announcement of fishtest on the talkchess forum: http://talkchess.com/forum/viewtopic.php?t=47885&highlight=s...
Initial discussion of the introduction of SPRT into fishtest, which led to a dramatic increase in our ability to measure improvements in self-play, in a statistically sound manner: https://groups.google.com/forum/?fromgroups=#!searchin/fishc...
SPRT background here: https://en.wikipedia.org/wiki/Sequential_probability_ratio_t...
Basically, we use a two-phase test to maximize testing resources. First a short time control test (15s/game), using more lenient SPRT termination criteria, then, a long time control (60s/game) test using more stringent criteria. That combined with setting the SPRT bounds to allow us to measure 2-3 ELO improvements has allowed the progress of Stockfish to be almost only improvements. Previously when developing an engine, you'd make 10 changes, and if you were lucky, 2 or 3 would be good enough to make up for the other bad or neutral ones.
If you look at the graphs on http://www.sp-cc.de/, you can see that it just keeps getting better, one small improvement at a time.
Congratulations to Stockfish! The community is amazing, and the patches keep on flowing. The sheer number of ideas is pretty incredible. If you are interested in contributing, head over to http://tests.stockfishchess.org/tests. You can submit a test, and it will be run by the virtual cluster of user donated machines.
It's been over four years since I put fishtest up, and in that time, there have been over 20,000 tests submitted. The really cool thing is that this distributed testing framework is only possible with an open source engine. So instead of being a disadvantage (everyone can read your ideas), it turns into an advantage!
MCTS has done very poorly on chess compared to alpha-beta. Chess has a high number of forcing moves in capture sequences, and it's been very difficult to evaluate positions that are not settled. Traditionally an algorithm called a quiescence search is used, but it relies on doing an evaluation at each node of the search, which would be prohibitive with the latency for a network evaluation.
One of the things that amazed me the most about AlphaGo Zero was that they didn't do any tricks to minimize the latency of the network evaluation!
Still, it's certainly worth a try, I'd be extremely interested to see what style of chess a self-trained MCTS chess version would have :).
Very cool to see Stockfish up here :). One of the cool parts is that the testing framework is fully open as well, at http://tests.stockfishchess.org/tests. It's been pretty amazing to watch the progress of SF since it was put on github by Marco and Joona. http://spcc.beepworld.de/ has some nice graphs. Those graphs are in ELO scale as well, so a linear line is getting exponentially stronger.
Currently for example, there 87 machines, contributing 341 cores of computing power for testing patches. That's pretty awesome for completely volunteer driven community!
I wouldn't say the GBA was too forgiving about mistakes. You had very limited resources, and sometimes needed some tricks to get things running acceptably. I do remember a few things like a divide by zero in a game that ended up jumping off into the middle of RAM and by luck, the game just happened to continue. But the examples from the article seem to be on purpose.
2) Code in VRAM was sometimes faster than executing code from the ROM, due to waitstates. This was used on the Nintendo DS as well. There was a lot of VRAM, and it was 0-waitstate, while your instruction cache was tiny.
3) STM to DMA registers was an optimization that was used fairly commonly, at least in homebrew games
5) This is definitely anti-emulator code :)
Nearly all the evaluation terms in Stockfish have been extensively tuned. Joona Kiiski used the SPSA[1] algorithm on a lot of them. Others have been hand-tuned using tens of thousands of games per attempt on fishtest [2]. Fishtest actually just recently got support for running SPSA tuning as well.
There is also a strong bias towards simplification, so if an evaluation feature is not proven to be an improvement it will be removed. Over the last few Stockfish versions, the # of lines has actually decreased in each version.
[1] http://en.wikipedia.org/wiki/Simultaneous_perturbation_stoch... [2] http://tests.stockfishchess.org/tests
As noted on the Garbochess JS page, I didn't estimate the strength of the JS version. It would be much weaker than Garbochess 2.20 on the same hardware. Having a node.js uci adapter would be fun to test this.
It will be very difficult to make Javascript competitive with Stockfish, even across 1000 computers. Still, a very cool project!