~tslil/ctak

switch to returning an array of actions instead of a linked list

- 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
might as well enable size 6

Same network architecture, same training principle. Predictably this is
too slow.

Also statically allocate state in driver programmes.
f3b67ebd — tslil clingman 1 year, 2 months ago
Change transposition table lookup policy

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).
switch to explicit game state & important bug fix & clang format

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.
new neural network arch (faster + better) & minor changes + fixes

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.
48665b2a — tslil clingman 2 years ago
--fast-math seems saves some time

That i can tell at a glance, the largest relevant change this
introduces is flush-to-zero for floats. Some testing is required to
ensure that the CNN isn't too sensitive to this. Preferable to that
option is to simply train it without relying on subnormal floats in
the first place.
c2ffe028 — tslil clingman 2 years ago
Went for more standard unicode symbols
2fc1a9a0 — tslil clingman 2 years ago
Corrected win screen in geminict
c7687f51 — tslil clingman 2 years ago
Enforce quoted ptn string for geminict
309ee7aa — tslil clingman 2 years ago
Welcome geminict!

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.
b4a42bc0 — tslil clingman 2 years ago
More towel wringing: re-implemented check_road_colour

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.
993d3d82 — tslil clingman 2 years ago
Trying to make things faster

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.
d8dae1d7 — tslil clingman 3 years ago
Merge branch 'master' of git.sr.ht:~tslil/ctak
2bc34e80 — tslil clingman 3 years ago
Fix copyright notice in files, and small preemptive optimisation

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.
84850904 — tslil clingman 3 years ago
Corrected generation of training data for 6s
9ea869f8 — tslil clingman 3 years ago
Don't generate header for training data + tweaks

For some reason it would seem that moving flats to a lower value and
increasing the proximity between caps and top flats improves
acquisition. Still not great, but every bit counts.
b9abf8f8 — tslil clingman 3 years ago
Change the training data generation a little

Although it pains me to say it, ``label smoothing'' appears to be
actually work. I'm also currently experimenting with training simply
against _all_ games, instead of only bot matches. Once the training
finishes i'll pit cttei against itself with old and new weights,
hopefully there'll be a noticeable improvement.
f17fb3bd — tslil clingman 3 years ago
Rename ct_k -> ct, IANAL but ...
efde8ff4 — tslil clingman 3 years ago
Small typo in generated output for weights
4f8848a6 — tslil clingman 3 years ago
Correct line clearing behaviour, EXIT_FAILURE <~ -1
Next