| Age | Commit message (Collapse) | Author |
|---|
|
* use elo
* optionally train on only diagonal
* train-inference nonlinearity alignment
|
|
|
|
|
|
A little subtle, but in non-self-play games sharing tt entries is incorrect. We must therefore key additionally on the evaulation function itself.
|
|
Previously we would spend all of the training epochs on making the network a better predictor of the *initial* TD-leaf values that we computed before the start of the first epoch. There's definitely something stale about this, given that the TD-leaf training targets involved the net evaluation at PVs. I'm not overly confident that this makes sense, but as a kind of compromise between fully on-line TD-leaf and the fully stale version we had before, we now recompute the TD-leaf values in each epoch with the fine-tuned net instead of the epoch 0 net.
Perhaps we were just lucky, but this seems to train a strong network under the default setting.
More experimentation is required.
|
|
|
|
nn_train.py
|
|
The goal in this change was to overcome the rock-paper-scissors phenomenon that was happening in capability space by having on a single candidate learn to beat the most recent version of itself. In some sense this lead to rotating around in capability space instead of chasing monotonic improvements.
I hope that flipping to a system in which many (N=5) candidates play each other and learn from their own set of diverse games in this pool, combined with --replay-iters, will lead to a given network having to have a much more comprehensive understanding of the space of tactics. I haven't yet had time to train this thorougly, will run those experiments on my desktop computer.
|
|
strength; also train for longer
The idea is that the current model is M_theta(board, ply) = "score for player 0", but we can instead create a different model M'_theta(board) = "score for player 0 assuming that it's player 0's move" and for a certain pair of functions sigma, normalise, recover M_theta(board, ply) = sigma(ply) M'_theta(normalise(board, ply)).
This pair of functions is sigma(ply) = +/- 1 (parity), and normalise being a conditional interchange of pieces on the board depending on the parity of the ply. The only things stopping this from being completely straightforward is that nn_train.py evaluates M'_theta itself so we need to pass sigma(ply) to the training loop.
6x6 is still untrained.
|
|
In a head-to-head this is +187 elo against the previous weights, although it trained more.
|
|
checking, re-using the input computed for the NN
|
|
|
|
scaling well to this size
|
|
|
|
After quite a bit of experimentation it would appear that a far better way to train on self-play data in this setup is to randomise not the moves but the opening. The new selfplay and match binaries have lost the epsilon parameter and now play a random opening of some length before switching to pure, deterministic engine inference. This also resulted in a cleanup of nn_train.py.
As an added bonus, in this configuration it makes sense to harvest training data from both sides in self-play and consequently the two sides are given distinct game ids (this was almost surely an oversight in the original version of TD(lambda) that i had). I also noticed that rand32 was not using the top 32bits of xorshitf*.
*Under default settings nn_train.py produces a 5x5 weight set that doesn't lose a single game to any other cttei that i cared to look at, when measured using `racetrack` (which has a diverse balanced opening book).
|
|
TD-lambda and TD-leaf are separated by the observation that minimax with a parameterised leaf heuristic is differentiable* in the parameters. "All" that had to be done was to extract the "principal variation": which one position survived all of the pruning to become the reported value.
This was a bit fiddly and uncovered a subtle bug (again) in negamax.c: we were not being complete in our overriding of the TT entry and by omitting key it was possible that later searches would find incorrect values.
The more interesting question to me was: how do we introduce enough variety while not corrupting the PV chain? I settled on having selfplay have one of the players be epsilon-random but the other greedy (minimax) and simply report only the greedy portion PV chain. This appears to work well enough in practice and doesn't introduce nonsense training data for the net (we don't force its actions to be nonsensical). I also deciced, perhaps in a departure from tradition, that we had good supervised labels for PVs that happened to be winning states, so the training overrides the targets in that case. Finally rolled back some of the ambition in nn_train.py default arguments.
*almost always
|
|
I've noticed high variability in training efficacy, part of that i think is due to the fact that the dataset per iteration is not really that large. Sure, it has many rows, but it's fundamentally given by the same engine playing itself with some entropy injection. To remedy this i've expanded the input data for any given iteration to contain --replay-iters many previous datasets as input too. Alongside that decreased the epsilon decay rate for slower "cooling", and included much more of the early game in the training set (min ply 8 -> 4).
|
|
NOTE: 6x6 weights are as-yet untrained
On the performance side:
* switch from linked-list chaining hash table to direct mapping
* cache check_win by hash
* persist transposition tables across plies (this was a big deal and difficult to puzzle out)
* add align directives to the network floats
* prepare_nn_input gained a small LUT to avoid branching (i suppose you might call this 1D embedding)
* apply mtune=native for the native builds
On the correctness side:
* Zobrist has now includes the ply parity
* the network now predicts something in [-1, 1] using tanh (approximated by polynomials)
* the training object is now MSE because we're learning a value estimate
* use .clangd instead of compile_commands.json
On the training side:
* completely forgo human-derived data set
* implement td(lambda), self-play, tournaments
|
|
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.
|
|
- 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
|
|
Same network architecture, same training principle. Predictably this is
too slow.
Also statically allocate state in driver programmes.
|
|
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).
|
|
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.
|
|
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.
|
|
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.
|
|
|
|
|
|
|
|
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.
|
|
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.
|
|
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.
|
|
|
|
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.
|
|
|
|
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.
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
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.
|
|
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.
|
|
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.
|
|
``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.
|
|
|
|
|
|
|
|
|
|
|
