An implementation of Tak and a computer opponent in C https://git.l-3.space/ctak/atom?h=main 2026-08-28T18:37:41Z 2026-08-28T18:37:41Z tslil tslil@posteo.de 2026-05-05T21:06:02Z urn:sha1:c415ed2a0bbab890fc1fdd2179c8f1405940c15a we needed to be saving the alpha before the search loop in which we modified it. At this point, though i can't remember, i expect that this is the cause of whatever "instability" the comment was talking about that would have prevented us from using >= in the TT lookup. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2023-01-29T19:49:04Z urn:sha1:f0139acd1d648dd1db93ee3d3b75546fb7b24c77 - attempts to keep the same move ordering as the list method - saves ~170msec on a depth 7 search for a given board configuration - there is room to improve the pre-allocation size estimates, these bounds are not obviously tight and it may or may not be faster to have tighter bounds or even some form of estimation 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2023-01-21T18:30:45Z urn:sha1:0e81096d5ecb6027814e7aae10b461e774f96407 Same network architecture, same training principle. Predictably this is too slow. Also statically allocate state in driver programmes. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2023-01-19T21:40:24Z urn:sha1:cb2b78ced27fc7996ed11c3450f69138d7d1b61f Given the approximate nature of the evaluations and truncated tree searches, the result of negamax will always be sensitive to the particulars of the depth bounding and the conditions for referring to precomputed values. The tradeoff here is a slight performance penalty (~200ms at depth 6 on my old Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz), but a greatly increased opponent strength as compared to `>=`, and the old convolutional network (flawed as the implementation was). 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2023-01-15T20:31:00Z urn:sha1:0223a9bec5535fced1a7698b55fd42155d9b0446 Previously the code base assumed that there was a single, global game state which was the implicit target of all actions taken. Looking ahead at architectural improvements, this has now been (almost entirely) made explicit and functions take tak_state_p where necessary (and also where unnecessary). Two important fixes to actions.c were made: - Previously when generating the possible stack moves, stack height overflows (> 15) were not taken into account and this resulted in the tree search corrupting the board state. Now action search does not list all legal actions, rather the subset of these encodeable by the implementation. - The check for crushing on a stack move was incorrect (too strict), and this resulted in many legitimate moves being igonored. Finally, in other changes, weights have also been improved by training all games instead of some subset for chosen players, and clang-format was run on the codebase. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2023-01-15T15:03:37Z urn:sha1:ee216c008a188a9436fedb85c70ee5d1719733b1 Gone is the convolutional neural network, for it turns out not only is it more difficult to train, but all of the extra information about board layers didn't make much of a difference at this size. So cnn1986 has been replaced by nn1986, a standard, two-layer, dense nn configured as a binary classifier and (mis)used in that capacity. Note: total number of parameters is unchanged. HARK: this new nn exposes a bug somewhere in ctak. Run ctlm with self-play to see the completely borked board state at the end. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-10-05T22:22:23Z urn:sha1:cf175fc346f1b208766b1f55d3673a7b208f322a This is a special interface to negamax_cnn1986 which is designed to generate output for use in a CGI tak interface to be used over gemini. Also in this commit is a reformating of the various source files to use the traditional tab width of 8 spaces. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-07-02T16:00:00Z urn:sha1:640d404b3cf3324aca4424fc3da4806d4562d0e4 Previously check_win would call check_road_colour once for each road colour, and check_road_colour would call a depth-first search (DFS) for each of the two axes. This meant that we were doing (up to) *four* depth-first searches for each call of check_win. I have replaced both axial DFS with the world's worst TM implementation of a connected component generation algorithm backed by the least guaranteed disjoint set data structure. Essentially doing anything about union find correctly is slower than just ... not doing it. Although we lose the asymptotic complexity, in practice we're doing this millions of times per turn, for a fixed board size and that's what matters. All in all, it appears that i've managed to shave about 69ns off check_win, per call -- nice! This amounts to 50ms or so saved at depth 5 per engine move, in one of my test games. Unfortunately nearly 99% of the time is still taken by evaluating the convolutional neural network. It's slow. 2026-08-28T18:37:41Z tslil tslil@posteo.de 2021-06-01T19:20:48Z urn:sha1:0deb42134cb7f0ed6ec809c3de1052ab2dfe2235 I tried the following, but they all made things worse: - moving away from the singly-linked (tail tracking) list for actions by: + using an array zipper for a deque + using an array to poorly hold a floating deque - caching the results of generating move lists in the transposition table and then + copying the resulting list/zip/deque instead of generating it + applying the move-to-front without copying, but this made the search order worse. Presumably in this case shallower nodes were messing up the search tree with garbage moves? I think some of this is not supposed to happen, but i have just the right combination of poor evaluation function and naively ordered and cheap move generation that i'm in a local minimum here. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-03-28T04:19:05Z urn:sha1:2dbb9fa9b69e49d49cebb1c17559f6fe67600a4d Eventually there'll be a more complicated data generation step than the one we're presently using, so having it in-lined in the loop is wasteful. Ideally also this would be update per ply and we could avoid recalculating it entirely for every query -- though it's probably ``fast enough'' for now. Also, caching is WIP.