An implementation of Tak and a computer opponent in C https://git.l-3.space/cgit/ctak/atom?h=lazy_queue 2026-08-28T18:37:41Z 2026-08-28T18:37:41Z tslil tslil@posteo.de 2021-07-03T20:17:27Z urn:sha1:7e58eadab1678d794344a0b14c7872296f585f96 presently it's not correct 2026-08-28T18:37:41Z tslil tslil@posteo.de 2021-07-02T16:00:00Z urn:sha1:07c5dded49d5943f54cca0c75a7a93a30ee2f323 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. 2026-08-28T18:37:41Z tslil tslil@posteo.de 2021-02-05T21:49:14Z urn:sha1:ce09b6d94ac3dbf426e959b14fd7731001a003d1 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-02-03T00:23:54Z urn:sha1:40c6b1dafab4de169bac8a799e7953e85061218e 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-02-02T02:46:24Z urn:sha1:11956b2e940f5e1839efab187d898092e819a766 If TEI is implemented, then i could make use of Morten's racetrack (https://github.com/MortenLohne/racetrack) and develop a quantitative measure of the bot's performance. This is the current priority. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-02-01T04:33:39Z urn:sha1:328c8d1e3094a942d6a2edd933c9cc4ab09daab1 It turns out that while i was training on a 0/1 classification problem, i was using 2*eval - 1. Training using this function instead, and on bot-dominated game choices (chosen_player in extract.sh) seems to have given a better evaluation function. At the least, Morten's swindle doesn't work anymore. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-01-31T20:33:30Z urn:sha1:399d90f1b94717aa0ca5abb1dc43bdb6f4160d13 Input polling without line-buffering is done using ncurses, so the buildroot configuration had to change accordingly to include that library. The Makefile changed to accommodate stand-alone building of ct1986 and to include -lcurses where appropriate. There were also some typos about copying ct1986 and ctaklm to the correct directories. 2026-08-28T18:37:41Z tslil clingman tslil@posteo.de 2021-01-30T21:47:48Z urn:sha1:84ad2e3c12cb505e3c5e3dd29d05edb529b82174 ``Common wisdom'' dictates that placements are often better than stack moves, so we bias the generated move list in this fashion. Seems to be a little faster.