tag:blogger.com,1999:blog-84907632024-03-13T21:46:53.767+01:00Failing The Turing TestOn Laziness, Impatience and HubrisArnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comBlogger382125tag:blogger.com,1999:blog-8490763.post-49868979795817698622019-02-03T09:19:00.003+01:002022-01-05T10:48:08.474+01:00Performance-Tuning Conway's Game of Life on ScratchBy pre-calculating state-transitions for clusters of cells, my little <a href="https://scratch.mit.edu/projects/96326891/">Game of Life Scratch project</a> now runs a 43,200 resp. 172,800 cell grid (in color) at 50-150 FPS, making it one of the fastest GoL implementations there.
<br />
<center>
<iframe allowfullscreen="" allowtransparency="true" frameborder="0" height="460" scrolling="no" src="//scratch.mit.edu/projects/embed/96326891/?autostart=false" width="500"></iframe></center>
<br />
Click into grid to create a life form at that spot. Press:<br />
- '1' to '4' to select a built-in life form for creation<br />
- 'i' to import + select custom life form, '5' to re-select it<br />
- 't' to toggle grid size (43,200 cells vs. 172,800 cells)<br />
- space to stop/continue<br />
- 'm' to select music track<br />
- 'c' to clear grid<br />
- 'r' for random grid<br />
- 'f' to show/hide frames-per-second rate<br />
- 's' to show/hide speed control and frame-skipping controlArnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-4710557927368561862018-10-04T00:49:00.000+02:002018-10-04T00:49:07.396+02:00Chess Engine Programming<iframe src="//www.slideshare.net/slideshow/embed_code/key/IFhlTnH7CKY55U" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/ArnoHuetter/chess-engine-programming" title="Chess Engine Programming" target="_blank">Chess Engine Programming</a> </strong> from <strong><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></strong> </div>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-21920019694065297212018-08-23T18:41:00.005+02:002018-10-13T00:13:56.159+02:00Building a Chess Engine with Colored BlocksSome time ago I was looking for a new Scratch project idea, which would help kids to learn coding, and be challenging and fun at the same time. For children interested in solving puzzles and in math. "Chess", I thought, "it has got to be chess".<br />
<br />
In general, <a href="https://scratch.mit.edu/">MIT's Scratch platform</a> is probably the least suited programming and runtime environment to implement a chess engine. It was designed for other purposes - for simple games and animations, programmed by kids. The language's capabilities are limited on purpose, esp. regarding structured programming, there are no local variables, no collections other than lists of strings, no bitwise operations (hence no <a href="https://chessprogramming.wikispaces.com/Bitboards">bitboards</a>), function parameters cannot change, and Scratch is very slow and even has some performance throttling built in (so that kids wouldn't have to worry about frame timing). But that hasn't stopped people from writing pen-based 3D games in Scratch. And for the chess engine case, that just meant it was bit more difficult, and that no implementation would ever reach the playing strength of chess games on other platforms. So perfect, it was just the challenge I was looking for.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-BMyRKy_eAA0/W4F-6FjJTlI/AAAAAAAAA-s/x-6fVZbwR58H_7ahHQycug0LIBiGPWrRgCLcBGAs/s1600/ChessCode.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="505" data-original-width="625" height="322" src="https://1.bp.blogspot.com/-BMyRKy_eAA0/W4F-6FjJTlI/AAAAAAAAA-s/x-6fVZbwR58H_7ahHQycug0LIBiGPWrRgCLcBGAs/s400/ChessCode.png" width="400" /></a></div>
<br />
My approach was to try different ideas, and only when I was stuck, I investigated about underlying chess programming theory in certain areas. So I came up with move ordering (based on iterative deepening), square piece tables, mobility evaluation and attack tables myself - I just fine-tuned the crude original implementations later, after reading on <a href="https://chessprogramming.wikispaces.com/">https://chessprogramming.wikispaces.com</a> and other places. Other things like alpha/beta-pruning or quiescence search I picked up from there directly.<br />
<br />
<div style="text-align: center;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://twitter.com/ArnoHu/status/909644913922514944"><img border="0" data-original-height="360" data-original-width="480" src="https://1.bp.blogspot.com/-L08a0V0jK1w/W38OA2w-pvI/AAAAAAAAA-g/hFjZt6Wa1horeB_5fEyLpvrMiqjmEKkqwCLcBGAs/s1600/kr.jpg" /></a></div>
Kochy-Richter checkmate detected by GoK - <a href="https://twitter.com/ArnoHu/status/909644913922514944">view video</a></div>
<br />
<h4>
<span class="bb-big">The First Week - CoderDojo Linz Chess</span></h4>
The <a href="https://scratch.mit.edu/projects/148769358/">"Game of Kings" project</a> started as a tutorial for the <a href="https://coderdojo-linz.github.io/trainingsanleitungen/scratch/scratch-chess.html">CoderDojo Linz Kids Programming Club</a>. I had implemented some other Scratch games before, which were all accompanied by step-by-step tutorials for children to re-create the programs on their own. It was Sunday evening, CoderDojo takes place Fridays, so I had four nights for coding and one for writing the tutorial. This is how that went:<br />
<br />
<span class="bb-big"><b>Day #1</b></span><br />
At first I worked on the graphical user interface. I found some nice open-usage chess graphics, and drew the pieces via <a href="https://wiki.scratch.mit.edu/wiki/Pen">Scratch Pen functions</a>, applying the <a href="https://wiki.scratch.mit.edu/wiki/Stamp_%28block%29">Stamp operation</a>. Sprites were only used for animating piece-movement. I preferred a simplistic 2D bird’s eye view to complex 3D graphics or similar. And user input should be intuitive and require just two clicks: first click the piece to move, then click the target field. When tinkering about how to represent board data in memory, I ended up with a <a href="https://wiki.scratch.mit.edu/wiki/List">Scratch List</a> with 64 entries, one for each board field. The list contains <a href="https://goo.gl/rmMWJj">Centipawn values</a> for each type of piece - negative ones for white, positive ones for black. E.g. the black queen’s value is “900”, rook is “500”, bishop “330”, knight “310”, pawn “100”, and finally a king is “20000” (capturing a king surpasses everything else combined). By adding up all the piece values on the board, one ends up with a material evaluation of the current board.<br />
<br />
<span class="bb-big"><b>Day #2</b></span><br />
Day #2 was dedicated to ramping up a chess engine prototype. I was aware that this would require a <a href="https://goo.gl/uXZJZ9">Move Generator</a> and a <a href="https://goo.gl/jS2wCu">Board Evaluation Function</a>, joined together by a <a href="https://goo.gl/49BQ95">MiniMax algorithm</a> - a <a href="https://en.wikipedia.org/wiki/Recursion_%28computer_science%29">recursive approach</a>, with one recursion for each subsequent move, spanning up a tree of moves. On each tree leaf, that is after the final move, the resulting board would be evaluated. I guessed the program could look ahead three moves (“<a href="https://goo.gl/GoHSyA">Ply 3</a>”) and put a hardcoded limit there. Luckily recursions are possible in Scratch via <a href="https://wiki.scratch.mit.edu/wiki/%28%29_%28Custom_block%29">Custom Blocks</a>, but local state cannot be kept, as local variables don’t exist, and block parameter values cannot be changed. So, I applied lists for emulating a <a href="https://en.wikipedia.org/wiki/Call_stack">call stack</a>. Every local variable has its own list. Some other Scratch chess engines have a dedicated block for each Ply, but I didn’t want to introduce duplicate code (by now we are at a move depth of 12 including Quiescence).<br />
<br />
I also implemented a move generator, initially for pawns and knights, and had the engine make its first moves. The move generator filled a move list for every search depth level with all possible moves at that point. Those moves were then applied one-by-one, MiniMax was invoked again for the next depth, and after returning the move was reverted to bring the board back to its original state. A move was represented by a 4-digit number, referring to the source and target fields. E.g. Nb8a6 would be “0217” – a move from field 02 to field 17 on the board.<br />
<br />
<span class="bb-big"><b>Day #3</b></span><br />
Next I completed the move generator for all other pieces. And I read about <a href="https://chessprogramming.wikispaces.com/Alpha-Beta">Alpha/Beta Pruning</a> on the <a href="https://goo.gl/bPFi3j">Chess Programming WIKI</a>, which was an eye-opener. Alpha/beta pruning allows to discard all moves early in MiniMax which won’t make sense anyway - something that the human mind does intuitively. Alpha and beta are assured lower and upper bounds for the board evaluation, which are passed up and down the recursive MiniMax calls and checked on each move. We can then ignore anything worse than alpha, because we will not make a move that’s not better than the best we have found so far. And we can ignore anything better than beta, because the opponent has another move option that places him into a better position than the current one. This lead to a major speedup.<br />
<br />
I then also implemented positional consideration to the board evaluation function as well by using <a href="https://chessprogramming.wikispaces.com/Piece-Square%2BTables">Piece Square Tables</a> (the tables for pawns and kings even distinguish between midgame and endgame). This made pieces on certain fields more valuable than on others. Check and checkmate testing was added too, simply by invoking the MiniMax, either for one move of the same side (check), or two consecutive moves in normal order (checkmate), and then probing for king captures. And I coded support for castling. The engine was able to play a correct game, apart pawn promotion, and also en-passant, which was added some weeks later.<br />
<br />
<span class="bb-big"><b>Day #4</b></span><br />
The final coding evening was dedicated to pawn promotion, code cleanup, and to verifying that the user input was valid. Pawn promotion was a quick and dirty implementation and stayed like this for months. This resulted in several lost games against <a href="https://scratch.mit.edu/projects/86498104/">Samueldora’s Bonsai</a> later, until I handled promotion in a generic way, just like any other move, so it would have full evaluation coverage.<br />
<br />
<span class="bb-big"><b>Day #5</b></span><br />
The day before the CoderDojo event, I wrote <a href="https://coderdojo-linz.github.io/trainingsanleitungen/scratch/scratch-chess.html">the programming tutorial</a>. Recreating all code would have been too much effort for the CoderDojo Scratchers, so I limited that task to the MiniMax and Evaluate blocks. I have not found the time to translate the tutorial to English yet, so for now <a href="https://goo.gl/2iErTa">here is the Google-translator version</a> (unfortunately it translates “Move” to “Train”). It includes a screenshot of the engine code back then, which you may want to compare in complexity to the current version. I then published the project under the name "Game of Kings".<br />
<br />
<h4>
<span class="bb-big">Extensions and Tuning</span></h4>
At this point the chess engine was working fine, delivering a Ply3 game at around 25 seconds think time. It was kind of fun, but slow with mediocre playing skills. I had not invested any time in performance tuning yet, which would be the key to look ahead more moves, hence increase playing strength. All other Scratch engines were at Ply3 or Ply4 too. My goal was to get to Ply6, as well as improving the evaluation function. And it took me several months to accomplish this. Here is what I did:<br />
<br />
<span class="bb-big">(1) <a href="https://goo.gl/AT4JAS">Opening Book</a></span><br />
I cranked out a quick Opening Book implementation, just as a proof of concept, with something like 10 common openings. Luckily user <a href="https://scratch.mit.edu/users/Grijfland/">Grijfland</a> picked up there and put a lot of work into what finally became GoK’s complete opening book. Thanks a lot for that! You can notice the opening book is applied at the beginning of a game, when there is nearly no think time spent.<br />
<br />
<span class="bb-big">(2) Additional Evaluation Considerations</span><br />
Over time I added support for evaluating double/isolated pawns, double bishops, early queen movement, castling and king protection, and similar to the evaluation function, as well as special support for king/queen and king/rook endgame scenarios. Some of those calculations are costly and are not done at the MiniMax leaf, but earlier up the tree.<br />
<br />
<span class="bb-big">(3) <a href="https://goo.gl/FXUrFg">Incremental Evaluation</a></span><br />
Evaluating the whole board at each MiniMax tree leaf is expensive too. Instead, GoK now evaluates the whole board only once at the beginning, and then just adds/subtracts the material and positional changes connected with each subsequent move.<br />
<br />
<span class="bb-big">(4) <a href="https://goo.gl/uDvk8n">Move Ordering</a></span><br />
By ordering the move lists from best move to worst move, alpha/beta pruning can be much more efficient. The alpha/beta funnel will be smaller early on, allowing to cutoff more moves outside the funnel immediately. GoK first applies known hash-moves that have led to pruning on the same board before (this does not even require move generation), then promotions, then good captures (according to <a href="https://goo.gl/E7CMdX">Most Valuable Victim - Least Valuable Aggressor Evaluation</a>, or short MVV/LVA), then so called <a href="https://goo.gl/bJ7DPF">KillerMoves</a> (which led to pruning on different but similar boards before), and then the rest of moves according to their expected positional effect. Additionally, on Ply1, there is <a href="https://goo.gl/uJPWvd">Iterative Deepening</a> (see below). With move ordering, GoK currently only has to traverse 5 out of 35 generated moves in average. And when transposition tables are applied (see below), that number is even smaller (AKA <a href="https://goo.gl/YGwYRa">“Branching Factor”</a>). Imagine GoK on Ply6, having to evaluate 35 moves on each MiniMax call. Those are 35^6 = 1,838,265,625 boards to be evaluated. But if we can skip 30 out of 35 moves each time, we end up with only 5^6 = 15,626 boards.<br />
<br />
<span class="bb-big">(5) <a href="https://goo.gl/mHBSJT">Transposition Tables</a></span><br />
Every board ever evaluated in the current MiniMax run is stored in a so-called Transposition Table (whose underlying implementation is a <a href="https://en.wikipedia.org/wiki/Hash_table">Hashtable</a>). Table entries consist of board <a href="https://en.wikipedia.org/wiki/Hash_function">hash</a> (key), and board evaluation (either exact, or upper/lower-bound, depending whether there was an Alpha/Beta cutoff) plus the best follow-up move (value). If we ever encounter a board we have seen again, we can then re-use what we have calculated before. Board hashes are created using <a href="https://goo.gl/V4aiSg">Zobrist Hashing</a>. Bitwise operations like <a href="https://en.wikipedia.org/wiki/Exclusive_or">XOR</a> are not supported by Scratch, so fast calculating of hashes, and incrementally adding / removing hash values was a challenge too. In Scratch terms, every entry member requires a list. Those lists are pre-allocated with 256k slots.<br />
<br />
<span class="bb-big">(6) Move Generator Lookup Tables</span><br />
The original move generator was pretty naïve and had hardcoded instructions for calculating where each piece could move. Now all those calculations are done in advance before starting the game - for every piece, on every field. The result is stored in lists and can be looked up much more quickly.<br />
<br />
<span class="bb-big">(7) <a href="https://goo.gl/qCpCRZ">Attack Tables</a></span><br />
Each time we calculate the next round of moves, we also calculate which fields are currently attacked (and - albeit currently disabled, as it is only used for SEE - by which kind of pieces). This ensures that a king will not enter a checked field, and is the data basis for static exchange evaluation (SEE). To prevent runtime overhead, we do that lazily on quiescent moves, namely then when a king could capture a piece.<br />
<br />
<span class="bb-big">(8) <a href="https://goo.gl/1WossQ">Quiescence Moves</a></span><br />
After a certain search depth has been reached, MiniMax calculates and returns the current board evaluation. But this arbitrary border can lead to horizon effects. For example, consider the final move is a queen capturing a pawn. But what if that queen can be counter-captured, but that information is beyond the current Ply horizon? We could end up sacrificing a queen for a pawn. To prevent this, GoK adds a few extra MiniMax rounds where it only inspects captures, once the maximum Ply depth has been reached. GoK can go up to 15 Ply levels; on the Scratch 2.0 runtime it usually between Ply6 and Ply10, with additional Quiescence moves.<br />
<br />
<span class="bb-big">(9) <a href="https://goo.gl/86ZXRN">Mobility</a></span><br />
GoKs also considers how many target fields each piece can reach on the final two Plys. Extra mobility is rewarded accordingly in move evaluation. There are lookup tables for each piece, which map target field count to evaluation value.<br />
<br />
<span class="bb-big">(10) <a href="https://goo.gl/PjFvaU">Iterative Deepening</a></span><br />
It might seem counter-intuitive, but running several MiniMax invocations, each with a larger Ply limit, can improve think time. This is possible due to transposition table caching and move ordering. By applying cached hash moves first - moves that led to a cutoff on a previous run - we might not have to calculate any other moves at all - that is if they trigger a cutoff again. And for Ply1 we keep stats of their evaulations from the run before, and apply them for ordering Py1 moves during the next deepening step.<br />
<br />
<span class="bb-big">(11) King Safety, Pawn Storms and Open Ranks</span><br />
During midgame the king should be protected by pawns. Only during endgame it can play a more active role. Also, a group of approaching pawns can become dangerous, and so can an open rank which might quickly be occupied by the opponent's rook. GoK calculates all of that during board evaluation, and it was the 2nd most important improvement in regard to playing strength (right after increased search depth and quiescent move). I implemented this based on the <a href="https://goo.gl/F5cu4k">Deloctu chess engine</a>'s approach - thanks to Mo Terink! Great to see what kind of cool stuff our interns are building in their spare time!<br />
<br />
<span class="bb-big">(12) <a href="https://goo.gl/3eyFge">Static Exchange Evaluation</a> (or short “SEE”, implemented but currently disabled)</span><br />
Static Exchange Evaluation examines the consequence of a series of exchanges on a single square after a given move and calculates the likely evaluation material to be lost or gained. Based on attack tables (see above), I implemented SEE and replaced MVV/LVA in move ordering, but the results were not sufficient, so SEE is currently deactivated. I read later that the primary application of SEE is in other areas, not in move ordering, partly because of its overhead.<br />
<br />
While the main focus was on performance tuning, I also added some other features, e.g. providing three difficulty levels (higher level = more search depth, plus on level “Difficult” think time is measured and search depth is adjusted after each move), underpromotion, support for playing black, undoing moves, PGN/FEN import/export, and lichess.org integration for automatic game analysis.<br />
<br />
Game of Kings has won the last two Scratch chess tournaments, and reached several draws against the AI chess engine Leela Chess Zero. BTW, runinng GoK on a fast Scratch engine like Sulfurous increases playing strength significantly: <a href="https://sulfurous.aau.at/html/app.html?id=148769358">https://sulfurous.aau.at/html/app.html?id=148769358</a>.<br />
<br />
Later I also cranked out an <a href="https://scratch.mit.edu/projects/209130998/">online two player version of GoK</a>
by using cloud variables. Any Scratcher logged in to the website can
take part, and the community can watch the ongoing game. In case
there is one player missing, the GoK engine steps in. It might even play
against itself. Feel free to give it a try, I'd be happy to hear your
feedback in the project's comment section.Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-5118443246668714422017-12-21T08:45:00.003+01:002017-12-21T08:45:43.171+01:00Database Performance Tuning - 20,000 Readers Reached<blockquote class="twitter-tweet" data-lang="de"><p lang="en" dir="ltr">Thank you to 20,000 readers of my <a href="https://twitter.com/hashtag/Database?src=hash&ref_src=twsrc%5Etfw">#Database</a> <a href="https://twitter.com/hashtag/performance?src=hash&ref_src=twsrc%5Etfw">#performance</a> tuning tips. I hope you found it helpful! <a href="https://twitter.com/Dynatrace?ref_src=twsrc%5Etfw">@Dynatrace</a> <a href="https://twitter.com/hashtag/SQL?src=hash&ref_src=twsrc%5Etfw">#SQL</a> <a href="https://twitter.com/hashtag/SQLServer?src=hash&ref_src=twsrc%5Etfw">#SQLServer</a> <a href="https://t.co/C2zcCkXhGo">https://t.co/C2zcCkXhGo</a></p>— Arno Huetter (@ArnoHu) <a href="https://twitter.com/ArnoHu/status/940488494132137985?ref_src=twsrc%5Etfw">12. Dezember 2017</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-2207189985605831792017-12-21T08:43:00.000+01:002017-12-21T08:43:13.574+01:00Scratch Chess Kochy-Richter Checkmate<blockquote class="twitter-tweet" data-lang="de"><p lang="en" dir="ltr">Chess enthusiasts on <a href="https://twitter.com/hashtag/Scratch?src=hash&ref_src=twsrc%5Etfw">#Scratch</a> found out <a href="https://twitter.com/CoderDojoLinz?ref_src=twsrc%5Etfw">@CoderDojoLinz</a> Chess (<a href="https://t.co/b5p2dMflhr">https://t.co/b5p2dMflhr</a>) discovers Kochy-Richter checkmate (Q sacrifice). <a href="https://t.co/hkPSQgNe6e">pic.twitter.com/hkPSQgNe6e</a></p>— Arno Huetter (@ArnoHu) <a href="https://twitter.com/ArnoHu/status/909644913922514944?ref_src=twsrc%5Etfw">18. September 2017</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-72127472866256789792017-03-09T07:53:00.001+01:002019-10-09T20:33:59.012+02:00Scratch Chess<a href="https://scratch.mit.edu/projects/148769358/">My personal project "Chess"</a>... no, not the <a href="https://en.wikipedia.org/wiki/IBM_Personal_Computer">IBM 1980/81</a> one! :-)
<br />
<br />
<center>
<iframe allowfullscreen="" allowtransparency="true" frameborder="0" height="460" scrolling="no" src="//scratch.mit.edu/projects/embed/148769358/?autostart=false" width="485"></iframe></center>
<br />
I implemented this ply4 minimax / alpha-beta pruning / move ordering <a href="https://scratch.mit.edu/projects/148769358/">chess game using Scratch</a>, MIT's programming environment for children. Now one could consider Scratch not really a suited platform for such an untertaking, given its built-in performance throttle, and the fact it does not support local variables, return values or changing parameter values (quite a constraint for recursions). But it was exactly that challenge that kept me trying. Also I noticed that while there were some really good chess engines in Scratch, but they missed an easy-to-use UI. And vice versa.<br />
<br />
I didn't know too much about chess programming, so the resources at <a href="https://chessprogramming.wikispaces.com/">https://chessprogramming.wikispaces.com/</a> turned out really helpful
The outcome was well-received by the chess community on Scratch. And I gained enough experience to work on a .NET port next. I think ply8 should be possible there on commodity hardware.<br />
<br />
I also provided a <a href="https://coderdojo-linz.github.io/trainingsanleitungen/scratch/scratch-chess.html">Scratch Chess tutorial (in German)</a> for the <a href="https://coderdojo-linz.github.io/">CoderDojo Linz programming club</a>.Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-89120101807315246852017-01-29T14:58:00.001+01:002017-01-29T14:58:09.580+01:00Scratch Highscore ListRe-usable <a href="https://scratch.mit.edu/projects/139406675/">sprite for storing a highscore list in a scratch cloud variable</a>.Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-27927120217936129882016-12-01T22:09:00.005+01:002019-02-09T12:28:47.998+01:00The Most Famous Programmers of All TimeLegendary programmers who contributed hugely to and had a lasting influence on the software development profession, as well as an extraordinary personal background:<br />
<br />
<ul>
<li><b>Ada Lovelace</b>, for the first algorithm on a Turing machine (Bernoulli numbers), which included conditional branches, loops and subroutines, and for recognizing such a machine is capable of more than solving numerical problems.</li>
<li><b>Donald Knuth</b>, for a work of beauty on TAOCP and TeX.</li>
<li><b>Dennis Ritchie </b>and <b>Ken Thompson</b>, for Unix and C, laying the groundwork for today's server operating systems.</li>
<li><b>Bill Gates</b>, for his contribution to the microcomputer software revolution, combining technical brilliance (Altair Basic) with business instinct (dealing with IBM) at a very young age.</li>
<li><b>John Carmack</b>, for revolutionizing game programming several times.</li>
<li><b>Linus Torvalds</b>, for bestowing Linux and git upon the world.</li>
</ul>
<br />
Read about their story in my slide deck below:<br />
<br />
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="485" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/82SYpmdzzaB5zk" style="border-width: 1px; border: 1px solid #ccc; margin-bottom: 5px; max-width: 100%;" width="595"> </iframe></div>
<div style="margin-bottom: 5px;">
<div style="text-align: center;">
<strong> <a href="https://www.slideshare.net/ArnoHuetter/rockstar-programmers" target="_blank" title="Programming Legends">Programming Legends</a> </strong> from <strong><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></strong> </div>
</div>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-68498507202734932592016-08-22T03:31:00.001+02:002016-08-22T03:52:26.404+02:00Engineering Culture at Spotify<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="344" src="https://www.youtube.com/embed/Mpsn3WaI_4k" width="459"></iframe></div>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-41705235162765761902016-08-21T14:49:00.000+02:002016-08-21T14:49:14.472+02:00Make Better Software MagazineFree Fog Creek PDF on software engineering, hiring developers and technical leadership: <a href="https://blog.fogcreek.com/make-better-software-magazine/">Make Better Software Magazine</a>.
<div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-wVm8NjNQnEM/V7mi9DDGT6I/AAAAAAAAA1U/vgDtxMjhW-IvHhESIp7A4twdV9-arlj2wCPcB/s1600/better.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://2.bp.blogspot.com/-wVm8NjNQnEM/V7mi9DDGT6I/AAAAAAAAA1U/vgDtxMjhW-IvHhESIp7A4twdV9-arlj2wCPcB/s320/better.jpg" width="320" height="167" /></a></div>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-11376928308829711322016-08-06T02:31:00.003+02:002019-02-09T12:34:35.763+01:00The History of Computing (in German, 1991)<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="714" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/pBXEGWbgfU4Cya" style="border-width: 1px; border: 1px solid #ccc; margin-bottom: 5px; max-width: 100%;" width="668"> </iframe> <br />
<div style="margin-bottom: 5px;">
<b> <a href="https://www.slideshare.net/ArnoHuetter/geschichte-des-computers" target="_blank" title="Geschichte des Computers">Geschichte des Computers</a> </b> from <b><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></b> </div>
</div>
<br />
Part two, written 24 years later:<br />
<br />
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="355" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/nFccvCg2Tecs8f" style="border-width: 1px; border: 1px solid #CCC; margin-bottom: 5px; max-width: 100%;" width="425"> </iframe> </div>
<div style="margin-bottom: 5px;">
<div style="text-align: center;">
<b> <a href="https://www.slideshare.net/ArnoHuetter/pc-history" target="_blank" title="The Making of the PC">The Making of the PC</a> </b> from <b><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></b> </div>
</div>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-60601989117738350182016-08-02T16:24:00.003+02:002016-08-02T16:25:12.405+02:00Servant Leadership<blockquote>I’ve always thought that the hardest and most valuable thing in work is to get a group of smart people to work together toward a common goal.</blockquote>
Great <a href="https://medium.com/servant-leadership/be-a-manager-3b0e39d87179">article on Servant Leadership</a> by Rich Armstrong.Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-6485917737321849422016-07-22T16:04:00.000+02:002016-07-22T16:04:05.642+02:00The Java Tools and Technologies Landscape Report 2016Very insightful, it's the <a href="https://zeroturnaround.com/rebellabs/java-tools-and-technologies-landscape-2016/">Java Tools and Technologies Landscape Report 2016</a>.
<div class="separator" style="clear: both; text-align: center;"><a href="https://zeroturnaround.com/wp-content/uploads/2016/07/TnT-2016-header-image.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://zeroturnaround.com/wp-content/uploads/2016/07/TnT-2016-header-image.jpg" width="320" height="214" /></a></div>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-65479102607805473412016-04-22T23:49:00.001+02:002016-04-22T23:49:08.438+02:00Database Performance Tuning<center>
<iframe src="//www.slideshare.net/slideshow/embed_code/key/naiS0S5zS0mmQC" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/ArnoHuetter/database-performance-tuning" title="Database Performance Tuning" target="_blank">Database Performance Tuning</a> </strong> from <strong><a href="//www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></strong> </div>
</center>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-90218587038640175672016-02-14T11:22:00.002+01:002019-10-09T20:34:53.368+02:00PacMan in ScratchMy latest <a href="http://coderdojo-linz.github.io/">CoderDojo Linz</a> contribution: <a href="https://scratch.mit.edu/projects/97137611/">Scratch PacMan</a>
<br />
<br />
<center>
<iframe allowfullscreen="" allowtransparency="true" frameborder="0" height="460" scrolling="no" src="//scratch.mit.edu/projects/embed/97137611/?autostart=false" width="485"></iframe></center>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-56120035653650925992016-02-02T22:23:00.001+01:002016-02-02T22:23:36.939+01:00Gandalf, our Mainframe Legacy Systems DeveloperYup, that pretty much sums up most enterprise projects I know...<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="270" src="https://www.youtube.com/embed/i9oU7rfb-do" width="480"></iframe>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-35800223478776590942016-01-17T00:44:00.001+01:002016-03-16T09:21:31.499+01:00The Developer Axe<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-ZZrR57qYyMY/VprWm2OJzII/AAAAAAAAAzE/zomjsKWEsf0/s1600/axe.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="180" src="http://2.bp.blogspot.com/-ZZrR57qYyMY/VprWm2OJzII/AAAAAAAAAzE/zomjsKWEsf0/s320/axe.jpg" width="320" /></a></div>
<br />
1997 was the time of Java 1.1, which was still hyped for applets. Another buzz was VRML runnning in browsers. Back then I was working on a 3D chat project. I had learned the Java basics at university and at work, and cranked out a chat server / applet combination that would talk via TCP sockets using a homegrown serialization protocol. Lacking an async socket API I used one server thread per client connection that would read messages and broadcast them to other clients. I was aware of the concurrency issues to be considered, so I sync'ed accordingly on serverside data structures.<br />
<br />
My local tests worked fine, and I uploaded my little chat system to a server, where it started attracting a decent amount of users over the next months. After a while I noticed they started complaining. Under a certain network load they had issues not being able to send/receive messages at times, until the whole server might stop responding. I remember being disappointed - I had been happy with the project's initial outcome, but the users were not. <b>My developer axe had not been sharp enough.</b><br />
<br />
Some System.out-debugging showed that the broadcast mechanism stopped and blocked connection threads when sending messages over slow or stuck connections. Which basically meant if one receiver turned out to be slow, it could block senders as well. Socket timeouts did not change anything (it would have been a duct tape fix anyway) - sending on some connections would simply block. I had a conceptual problem. For the meantime I added a cron job that would restart the server each day. Not nice.<br />
<br />
I concluded I needed to decouple receiving and sending, and to introduce serverside sending threads as well. I planned for queues between receiving and sending threads (so even more connection threads, not very scalable, but all I could do at that point - "luckily" the number of concurrent users never exceeded 100). This would prevent one screwed connection to affect any other connections.<br />
<br />
But how to implement that, when all the Java 1.1 collection classes had to offer were Vector and Hashtable (no BlockingQueue), and I couldn't find any Semaphore class either?<br />
<br />
It took me a while to dig out <b>how <a href="https://docs.oracle.com/javase/tutorial/essential/concurrency/guardmeth.html">Object.wait() and Object.notify()</a> could be applied here</b>. No programming course had covered it, and the JavaDoc on that was slightly mystical too (remember, Google was still a small startup back then). I finally came up with this solution:<br />
<br />
<pre>public class SenderThread extends Thread {
private Object lock;
private MyLinkedList pendingEvents;
private Connection conn;
private boolean stopped;
public SenderThread(Connection _conn) {
conn = _conn;
lock = new Object()
pendingEvents = new MyLinkedList();
stopped = false;
}
public void run() {
while (!stopped) {
synchronized(lock) {
if (pendingEvents.isEmpty()) {
try {
lock.wait();
}
catch (InterruptedException e) {
}
}
}
if (!stopped && !pendingEvents.isEmpty()) {
Object obj = (Object)pendingEvents.popFront();
conn.send(obj);
}
}
}
public void send(Object obj) {
pendingEvents.pushBack(obj);
synchronized(lock) {
lock.notify();
}
}
public void terminate() {
stopped = true;
synchronized(lock) {
lock.notify();
}
}
}</pre>
<br />
That worked, and the chat server was running like this until some years ago, when the Java plugin studdenly required applets to be signed, and certain browsers stopped supporting Java altogether. The binaries and the source can still be downloaded <a href="http://visualchat.weirdoz.org/VisualChat.zip">here</a> and <a href="http://visualchat.weirdoz.org/visualchat_source.zip">here</a> (one funny detail, it originally wouldn't compile on later Java compilers, because I had used variables named "enum", which was not a reserved keyword back in Java 1.1).<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://visualchat.weirdoz.org/screen.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="http://visualchat.weirdoz.org/screen.gif" height="288" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The chat in its heyday on Windows XP (500,000 users signed up overall)</td></tr>
</tbody></table>
<br />
Private side-projects like this are a great playing ground. And they are important for developers. Such projects allow to experiment, make mistakes and learn from them at low risk. <b>Not everything is in the textbook or taught in classroom, and at work one often is constrained to a certain technical area.</b><br />
<br />
I am conducting a lot of developer interviews today, and notice the difference in skillset between those who just do what is required at work or school (and not more), and <b>those who are curious beyond the tasks at hand, and code in their spare time as well.</b><br />
<br />
When developers <b>link to their development blogs, stackoverflow profiles or github pages from the CV</b>, I can get a glimpse at those endeavours. By choosing what to work on within private projects they sharpen their developer axe, and are well prepared for tomorrow's challenges.<br />
<br />
Similar articles:<br />
<br />
<ul>
<li><a href="http://arnosoftwaredev.blogspot.com/2013/10/mutexes-vs-semaphores.html">Mutexes Vs. Semaphores</a></li>
</ul>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-23992577815508626362015-12-26T03:44:00.003+01:002015-12-26T03:44:53.925+01:00Leading Software Development Teams<center>
<iframe src="//www.slideshare.net/slideshow/embed_code/key/2VsoGzcu10URsR" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/ArnoHuetter/leading-software-development-teams" title="Leading Software Development Teams" target="_blank">Leading Software Development Teams</a> </strong> from <strong><a href="//www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></strong> </div>
</center>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-22751496691439547172015-12-14T19:18:00.002+01:002015-12-14T19:19:15.918+01:00Windows Debugging with WinDbg<center>
<iframe allowfullscreen="" frameborder="0" height="485" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/NrgTZGz02ZE35p" style="border-width: 1px; border: 1px solid #CCC; margin-bottom: 5px; max-width: 100%;" width="595"> </iframe> <br />
<div style="margin-bottom: 5px;">
<b> <a href="https://www.slideshare.net/ArnoHuetter/windows-debugging-with-windbg" target="_blank" title="Windows Debugging with WinDbg">Windows Debugging with WinDbg</a> </b> from <b><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></b> </div>
</center>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-53691558514269057242015-10-19T22:35:00.000+02:002015-10-19T22:44:08.195+02:00Dragon Game with ScratchMy sons and me worked on this little Scratch game for the next <a href="http://coderdojo-linz.github.io/">CoderDojo Linz</a> (<a href="https://scratch.mit.edu/projects/81928816">Scratch project page</a>).
<br />
<br />
<center>
<iframe allowfullscreen="" allowtransparency="true" frameborder="0" height="402" src="//scratch.mit.edu/projects/embed/81928816/?autostart=false" width="485"></iframe></center>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-14136027772234839172015-09-10T22:58:00.000+02:002015-09-10T22:58:03.303+02:00MindCuber at CoderDojo Linz<div id="fb-root"></div><script>(function(d, s, id) { var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/en_US/sdk.js#xfbml=1&version=v2.3"; fjs.parentNode.insertBefore(js, fjs);}(document, 'script', 'facebook-jssdk'));</script><div class="fb-video" data-allowfullscreen="1" data-href="/coderdojolinz/videos/vb.1064314536931725/1125656620797516/?type=1"><div class="fb-xfbml-parse-ignore"><blockquote cite="https://www.facebook.com/coderdojolinz/videos/1125656620797516/"><a href="https://www.facebook.com/coderdojolinz/videos/1125656620797516/">Mindcuber - Lego Mindstorms@CoderDojo Linz</a><p>Der CoderDojo Mentor Arno Hütter hat mit seinen beiden Jungs Alex und Tommy einen Lego Mindstorms Roboter zum Lösen von Zauberwürfeln gebaut. Beim nächsten Dojo wird Arno zeigen, wie man mit Mindstorms solche Roboter baut. Möchtet ihr auch mal beim CoderDojo dabei sein? Hier geht es zur Anmeldung: http://coderdojo-linz.github.io/termine.html</p>Posted by <a href="https://www.facebook.com/coderdojolinz">CoderDojo Linz</a> on Sunday, August 30, 2015</blockquote></div></div>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-57666872503475129722015-08-21T07:24:00.001+02:002015-10-19T22:44:32.473+02:00Scratch BreakoutMy latest <a href="http://coderdojo-linz.github.io/">CoderDojo Linz</a> contribution (<a href="https://scratch.mit.edu/projects/72990950/">Scrach project page</a>)...
<br />
<br />
<center>
<iframe allowfullscreen="" allowtransparency="true" frameborder="0" height="402" src="//scratch.mit.edu/projects/embed/72990950/?autostart=false" width="485"></iframe></center>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-44304244895599954772015-08-21T07:21:00.000+02:002015-11-22T09:47:43.256+01:00Software Disasters<div style="text-align: center;">
<iframe src="//www.slideshare.net/slideshow/embed_code/key/BgJSeJBgEoRBpV" width="425" height="355" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe>
</div>
<div style="text-align: center;">
<strong> <a href="http://www.slideshare.net/ArnoHuetter/software-disasters" target="_blank" title="Software Disasters">Software Disasters</a> </strong> from <strong><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></strong>
</div>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-61448485861565582902015-06-01T06:25:00.001+02:002019-02-09T13:41:03.725+01:00Computer History Timeline<div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-1WehUr8vk48/VWvgNeTBHKI/AAAAAAAAAxg/dlkk6Wc4F20/s1600/computer_history_timeline.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-1WehUr8vk48/VWvgNeTBHKI/AAAAAAAAAxg/dlkk6Wc4F20/s400/computer_history_timeline.png" /></a></div>Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.comtag:blogger.com,1999:blog-8490763.post-62771043279508392962015-05-31T00:14:00.000+02:002019-02-09T12:34:25.450+01:00The Making of the PC<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="355" marginheight="0" marginwidth="0" scrolling="no" src="//www.slideshare.net/slideshow/embed_code/key/nFccvCg2Tecs8f" style="border-width: 1px; border: 1px solid #CCC; margin-bottom: 5px; max-width: 100%;" width="425"> </iframe> </div>
<div style="margin-bottom: 5px;">
<div style="text-align: center;">
<strong> <a href="https://www.slideshare.net/ArnoHuetter/pc-history" target="_blank" title="The Making of the PC">The Making of the PC</a> </strong> from <strong><a href="https://www.slideshare.net/ArnoHuetter" target="_blank">Arno Huetter</a></strong> </div>
</div>
Arnohttp://www.blogger.com/profile/10541039623935410561noreply@blogger.com