| Age | Commit message (Collapse) | Author |
|---|
|
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.
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
For now we'll stay with directly recomputing it at each non-terminal
node
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
