Valkyria

A computer go bot by Magnus Persson. See Viking for info on older versions preceding Valkyria.

Valkyria

Valkyria is a computer go program using Monte Carlo Tree Search (MCTS). It is written Object Pascal (Delphi 5) and what I think make it special is that the playout code uses a rich representation, which makes it very slow. Furthermore the playouts are done using some very large handwritten decisiontrees. This is possible because the rich boardrepresentation makes it easy to write code for the playout. But be warned, I do not recommend this method!

The search algoritm used to be classic UCT but it has become more a simple best first search (probably very similar to that used by Mogo). It rely heavily on All Moves As First (AMAF) which allows it to completely ignore irrelevant moves and search very narrow and deep.

20 Aug 06: Bug fix: The simulations used a komi of 0.5. New feature: Parts of he search tree is reused for the next movegen. In forced sequences almost the whole move tree can be reused.
29 Aug 06: A lot of new code: Valkyria_UCT has been updated with some basic move selction heuristics which improved the strength a lot. I also added detection and deletion of symmetric moves, so that it searches deeper early in game. Also the search tree now is saved to files for early opening positions which can be reused in later games. The GTP client is threaded which allows Valkyria to Ponder when the opponent is thinking. With these changes Valkyria_UCT has gained about 300 rating points on the ComputerGoServer.
11 Sep 06: A simple system for making an opening book has been added. The main goal is to increase the variety in the early opening and secondary to avoid really bad moves. I have started to add tactical knowledge to the simulation code.
24 Sep 06: I finally implemented a rudimentary ladder reader which will be tested as Valkyria_UCT5 on CGOS. I also realized that my laptop was overheating when the CPU used 100%, which made it drop down 1/3 in speed. I have now inproved airflow and reduced amount of pondering done, so that temperature may stay reasonable.
26 Sep 06: After a little more than 100 games on CGOS, Valkyria is now competing with MoGo on the top of the list. I have trouble giving Valkyria 2 stones handicap on 9x9.It also beat me once with 5 stones on 13x13.
2 Okt 06: Finally Zobristhashing for SuperKo-detection is implemented. I reintroduced some more selective search in Valkyria_UTC6 which might have increased the strength. Valkyria can now connect to KGS and seem to do well against Kyu-players. It has won almost all games on 7x7.
25 Okt 06: Valkyria has now played over 1000 games on the new KGS server. The rating has changed so one cannot directly compare the ratings from the old KGS. I now write that Valkyria is 8 kyu, but I will probably change this soon if it keeps beating players stronger than that.I think it wins many games because of a surprise effect.Many players lose the first game but win the second.
29 May 07: Finally I did some new work for Valkyria again. I have implemented progressive widening similar to what Crazystone do, and some crude move ordering. I also fixed some bugs and improved ladder managment. Against humans (myself) I feel this version is stronger, but beating the top programs on CGOS is still hard.
2007 - 2008: There was a lot of finetuning of the playouts and tests of parameters for the search algorithm. The search code is rewritten so that it can run several threads with playouts for multicore processors. The search code becomes much more similar to the latest versions of Mogo using AMAF to make the search really selective.
6 Aug 08: Valkyria came 3rd in the 9x9 computer go event at the European Go Championship in Sweden. This was a very tough competition and interestingly all programs were run on similar machines. The 19x19 competition simply revealed that there was a major problem with ladders which made Valkyria lose quickly several times.
17 Aug 08: Valkyria came 1st in the 9x9 August Formal division winning 11 games out of 12! And this time using my old 1.4GHz Pentium M laptop. I have been fine tuning the playouts and turned off some unnecessary features in the search algorithm. Playing against it myself on 9x9 is now hard.
14 Sep 08: Valkyria won 3 out of 8 games in the 19x19 September Formal division. Some simple changes for 19x19 go specifically has improved play a lot. This version is now ranked 6kyu on KGS

4 April 10: Valkyria now runs on a i7-860. It participated in the 9x9 KGS Tournament and came 3rd, after beating the Winner Zen 2 times but losing to other programs. http://www.gokgs.com/tournEntrants.jsp?sort=s&id=501
. I need to implement a lockfree threaded version to make it even stronger. Right now the old threaded code just locks up right away.
12 April 10: I found the threading bug! The 2-core version is about 100 Elo stronger on CGOS 9x9 and I just started testing the 4-core version. Scaling to more threads than 4 (using hyperthreading) seems to be poor. Which means I need to to write a lockfree version without synchronization.
4 Aug 10: Won the 9x9 European Computer Go Championship and came second in the 19x19 tournament after Manyfaces! Also on CGOS 9x9 Valkyria has been on the top for some time.
30 Sep 13: I stopped developing Valkyria. But I play tournaments on OGS as Valkyria9 and on LittleGolem as Valkyria 9 Bot with very good results ( Go 9x9 Championship).