An MLP then ? Or a secret special architecture ? I think I will follow your advices and start with Oware, I’ve already studied this game before and I think it’s a better game too!
Good old MLP (ponies 
). Not so secret, but I’d tell you there are 81 squares in UTTT and each square can hold about 30 different states (one-hot encoding). I also exploit the fact that during move only handful of squares are changed.
3 Likes
Interesting, naively I assumed 4 states in every square. After a while I can see 6 possible states. But around 30? Interesting.
I have to return to my naive CNN bot for UTTT …
Edit: After 10 min I can see why adding 5 more states can be useful - so maybe after 1 h I can see 30 states 
Thank you for interesting idea …
I am also searching the 30 haha. So far I have : empty, cross and nought as a base. But if we take the big square we can have, finish or not, finish can be tie, or cross winner or nought winner. For not finishing we can differentiate playable and non playable squares. With a one-hot vector I have in total 3 * (3 + 2) = 15.
It’s only half the count 
Or maybe its totally a different encoding
After thinking it through carefully, I realized i miscounted, recounted and ended up with 42. I am just wondering which ones are the wrong ones, if you list your 30 states I’ll be able to identify the wrong ones and discard them. Thanks in advance.
Individual ranking: #68
School ranking: #1 University of Wrocław
Language: C#
I know the contest is long gone, but it costed me quite a lot, and I’m still busy fixing real-life things, so postmortem is a little bit late.
I aimed top 50, so I am a little disappointed, as I have a feeling that this was possible, but I screw some things organizationally.
Acknowledgments
Thanks for many hours talking and sharing ideas, and great feeling of being a member of the wonderful community.
Special thanks to @MSz, and also people from our Polish Slack Community: @Zylo, @DomiKo, @Nerchio. Thanks to @eulerscheZahl for sharing some bit-magic knowledge - I learned a lot.
Congratulations and many thanks to all participants from our University. The ones that happened to be in the representation are @MSz, @DomiKo, @KeNaj712, @Pawix.
Thanks to CG for organizing the event @TwoSteps.
And last, but definitely not least, congratulations for all “proper” winners, and TheOne[tm] far above them ;].
Game
I am really happy that my first impression was correct, and the game allowed heuristics to be competitive. Even better, there is also a diversity of search-based algorithms at the top, which is wonderful. This is a huge advancement over the Fall Challenge and definitely a step in the right direction!
This does not fully cover the disappointment from the fact that the rules are copied from the existing boardgame. I really felt for a few days like CG cheated with this.
I really like the idea of putting all legal moves as input. Mostly time-wasting for top programs, but a huge help for lower leagues, heuristic approaches, etc. A good thing, so please keep if possible (i.e., not for ‘infinite’ number of moves ^^’) in the next contests.
Visualization was hmm… theoretically nice to look at. But. ‘Normal’ one did not have days(!) nor nutrients, so it was unusable from the start. If not for that, it was good enough, as the ‘debug’ one was actually worse and less readable. Dormant and sun gathered info was OK, but player messages were harder to read; there was no info about the quantities of the trees each size, and: no info about the player moves! That is ridiculous. “Great debug visualization,” but you still have to go back and forth with frames to see what actually happened. Please add an option to just print player moves in visualizations in future games CG.
Algorithm
Synchronized Beam Search. I started with some Flat Monte Carlo to test the engine. But at an early stage I was convinced that efficiency all the way and opponent is not so important, so I focused on beam, and later didn’t have time to implement some opponent prediction or something smarter.
I spent quite a lot of time encoding the engine with a bit magic, which was a great experience, but as it was something rather new to me - also time-consuming. And I spent some time on visualization - which helped me a lot.
What did not work for me was beam search, where I allow in the same layer states with different days - it breaks the evaluation. I had to synchronize this: inserting waiting states for a new layer, and counting states ready to change day - if all are ready, then apply ‘next day’ to them.
What I really put the accent on and I’m proud of is move pruning. I did not have hashtables, so I put some effort into reducing the branching factor during the move generation.
Completes at the beginning or never. Grows in proper size order but additionally without permutations in the same size. Seed only when free. In the first beam search day it can go before any grow, in deeper search goes only as last action (wait was illegal if seed was legal).
Seed is pruned by the target (used for seeding from size 3 first search day, any size tree later). So when generating legal actions, I try to generate only one action seeding to a certain hex - that prunes a lot.
Apart from this, I added later some priority-based stage-based pruning like avoiding shadows early and avoid poor soil later.
Evaluation
This was really simple. I calculated optimal tree completes for both players for day 23. For all the other days, it was just calculating gathered sun in the future (my suns - opponent suns) with the current state of the board plus current score times 3. Discounted times 0.99 each day in the future. And that’s all.
I had many more concrete ideas ready to code (or even started), but without time to actually apply them.
General Proposition
I want to seize the opportunity and write a few words about something I have in mind, and discussed already with a few people on several occasions.
Please add additional league @TwoSteps!
Leagues are the best invention of CG in years. They shift the challenge from PvP to PvE, encouraging learning and knowledge sharing. They add a sense of clear goal, and accomplishment. They make rankings more stable. During the contests, they create additional thrill in the moments of the openings.
But the number of users participating in contests increased like twofold at least, and the number of leagues is the same. Which is horrible both with a computational point of view, a logical one, and the user experience.
So please consider adding some league (at least one!), probably at the bottom, as Legend is known to be the top and it will be a mess to change this. But adding some ‘Copper’ that will work as current bronze (first league with full rules), but will be below bronze might help a lot and at least reduce the issues we currently have with this, generally great, system.
14 Likes