bug-gnubg
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-gnubg] GNU Backgammon overview/background


From: Joseph Heled
Subject: Re: [Bug-gnubg] GNU Backgammon overview/background
Date: Mon, 17 Nov 2003 11:31:55 +1300
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031007



Øystein Johansen wrote:
is correctly. I'm really sorry... Here's my new attemt)

Long story.......

TD learning was the first thing. I'm not sure what version number this net had, but lets call this contact net 0.0.

contact net 0.0 wasn't the best player in the world, and the things didn't become anything better by the fact that it played together with a bad race net. Let's call the first race net 0.0. Together I estimate they would have a ~1600 fibs rating.

Right. 0.0 was trained using TD, and was around 1630 if I remember
correctly. All nets after that were trained using supervised training.


One of the probles was that the nets didn't match each other either. It refused to break contact when it was up in the race. And sometimes it also refused to hold contact when it was down in the race. The race net also refused to bear in chequers in race in some games, this was due to the rece net gave a better GWC than the bearoff database. Nearly funny to watch these games.

Joseph started his experiments. One on the first things he tried, was to split the contact neural net to a contact net and a PBG(?) net for
BPG (Bar Prime backGame)

backgames and priming games. This split didn't work very well. Joseph had a hard time training these nets (Still using TD ?), and they where terrible out of sync with each other and caused the same problem as described in the paragraph above, except that the PBG net and contact net was more out sync than the race and contact net, so it was causing more trouble than it gained strenght. (Correct me if I'm wrong, Joseph.)

Joseph also found that some neural net inputs didn't contribute to the learning, so he removed some inputs, and adjusted some others.

So, Joseph rejected the PBG net, and started supervised training instead. The theory was simple enough: If a position has a cubeless equity at 0-ply X ppg, and the same position has a cubeless equity of Y ppg at 1-ply, then if abs(X-Y) > a threshold value, then it's reason to belive that the 0.0 contact net does not understand this position well, and this position and (position type) need more training. (The threshold valuse was set to 0.1, I think). Net 0.0 was set to play against it self, and for each position it reached, it calculated the 0-ply equity and 1-ply equity (both cubeless of course, cube alorithms even wasn't implemented yet). If the criteria of abs(X-Y)>threshold applied, then the position was stored in a database. Just the position, nothing else. After some number of games, the database had lots of positions, where the net needed more training and the self play was stopped. Joseph may know how many positions there are in this position database.

This would have been a good way to do it, but I was much more simple
minded at the time. At first I added positions I manually observed GNUbg had problems with. Then I added random positions from self play. All
positions were rolled out at 0 ply, 576 tries.


Now, for each position in the database, it was performed a cubeless rollout, to estimate the 'real' ('real' = at least better) probabilities and equity of the position. The rollouts was done with the same 0.0 net. The rollout results was added to the database of positions. In this way Joseph developed a database of positions and rollout results for each position.

So, this databased was used for training the next version of the neural net. Normal backpropagation for each position in the database, with the rollout result as the desired result. Running on through each position in the position database and updating the weights with backpropagation based on the rollout results, is called an epoch. Several epochs are run over the database, starting with high alpha values (alpha is the learning rate which is a foctor of hoe much the weights should be adjusted), and decreasing as the weight values converges. The order of the positions where also randomized for each epoch. The resulting neural net was called 0.10, IIRC.

This net improved the strength of the program a lot, but still the race net sucked. To avoid Joseph made a OSR based race evaluator, written i c++ (you can still see the "race-c++" branch in the cvs, but this branch was never merged into the main branch, but it was added to the fibs2html tool), and used this with mgnutest. Joseph also developed a small neural net for pruning moves for deeper evluations. This net had only 5 hidden nodes, and was therefore very fast. The fast 5 hidden node net for pruning combined with 2-ply search and the OSR race evaluator, reached reached a FIBS rating of about 1850-1900.

Still something had to be done to the race net. I remember we discussed how to solve this problem. I remember several schemes discussed. I thought about a neural net with the chequer positions for one player as the input, and the distribution of number rolls to get off as the output, and someone alse had other ideas, and while we discussed this problem at the list, Joseph suddenly released a new race network! I remember I was partly shocked! Wow! With this new race net he used 14 input nodes for borne off checkers. One input for each checker checker off. I remember I asked why, and he replied something like: "I don't know, but it works!". This network that he had breaded was trained based on OSR evaluations, And it was released with the contact net 0.10 and together they where called 0.10 (I'm taking this from my memory now, so the numbering may be wrong)

I remember people suggesting various approaches based on the assumption that a neural net is not suitable for handling the race. (Perhaps from observing Snowie performance). I always thought that since race is much much simpler than contact, a net should handle it much much better as well. Given the right inputs and training, it does well. As to the "One input for each checker off", it is a simple extension of the "linearity breaking" for checkers, where each point is encoded as 4 inputs (for 1,2,3, and more). This is probably one of Tesauro greatest contributions.


The first GamesGrid players GGraccoon and GGbeaver was based on these two networks, the contact 0.10 net and the race 0.10 net. (David added the reduced search algorithm which was used by GGbeaver, and this change was implemented in the gnubg project. Actually there was a reduced search algorithm before David's as well, but David's algorithm was better and faster.)

In february 2001, Joseph makes some new changes to the evaluation algorithm and and a new set of weights is released. He calls this net of weights 0.15 in fibs2html, and the same weights are called 0.11 in gnubg. I'm not sure of the differences of this net and the 0.10 net. Joseph knows the details. A better cache system was added to the evaluations, and a neural net speed up trick was also implemented)

Late 2001 (November/December) Joseph splits the contact network into a crashed net and the ordinary net. I'm not sure how he trained these net's but I assume he used supervised training from the position database. This net was mergg into the GNU Backgammon project in January 2002. This was the really great update! It was amazing to watch mgnutest play in fibs with this net. I really playd a master game. I showed that it was able to find moves with long term plans, and I would already at that stage say that it would outplay JellyFish in most positions and play equal Snowie 3.2 or better in most positions. (It would of course outplay Snowie in bear in situations, but we all know that Snowie suched at bearing in). The new neural net trio formed was numbered 0.12. I'm not sure about the training method, but I assume it was based on the database of positions and rollouts. (Maybe the rollouts was rerun or something... Joseph knows.)

The strange thing with the 0.12 nets, was that even though it was a class for crashed position on it's own, specially trained on crashed positions, it really played crashed positions badly? The gain was really the contact net and not the crashed net! It's possible that the contact net got better, since it now didn't have to learn about crashed positions. Some of the brain capacity was freed to learn the contact positions better. The out-of-sync problem between the crashed and contact net and it wasn't a big problem either, since a game very seldom goes from contact to crashed and then back to contact again. Joseph runned some analysis of the occurence of each position class from mgnutest fibs playing, and he reported that 79% of all evaluations where contact evaluations, 8% was crashed evaluations, 7% was race and 6% was bearoff evaluations.

Joseph then used some months to improve the crashed net. I guess he used the same technic as usual described on his page. Database of positons and rollout results traind over several epochs. and we had nets called 0.12a and 0.12b, and the crashed net slowly improved.

Now the new problem arise: It's not a problem to bread new neural nets, but how can you say that one net is better than an other one? Two good nets needs millions of games to give a significant anser of which is best. For this purpose Joseph started the gnubg training project. Voluenteers over the internet, specially Ian Shaw, had big files of position collected from online games, and rolled them out in big scale. (We had a own tool for rolling the positions out called sagnubg.) The rollout results was used as reference positions or benchmark, and the net who played best according to all the rollout results in the reference positions, was considered the best neural net. I guess we rolled out about half a million positions (?).

Now Joseph started to use a slightly other technique for training. He wanted to let the neural net learn "consepts". He let the computer play games against it self or on fibs. He analysed moves instead of positions. If a 2-ply evaluation chooses another move than a 0-ply evaluation, there is a "concept" of the position it doesn't understand. If 0-ply an 2-ply disagreed on a move, both resulting positions was added to the training database. Then these positions in the database was rolled out, and a new series of supervised epoch training was performed. If the new resulting net scored better against the reference database, the net was considered better. In this way the static evaluations was trained to play like the 2-ply evaluations. Note that the positions in the reference database was never used for training, just for reference.

The training method in the above paragraph gave the some new versions of 0.12 nets, all the net was gradually improved, the race net, the crached net and the contact net. these where named 0.12c, 0.12d and so on. In December 2002 or January 2003 the 0.13 nets was released. It was real world class! Really amazing! We started to roll out contact position for reference position benchmarking as well, and just as the last benchmark rollout was completed, Joseph released the 0.14 nets. This nets are probably the best neural nets for backgammon playing in the universe right now. (I can only think of mloner and zbot as real competitors, since I strongly belive that the 0.14 net has a edge over Snowie4.)

(It's late I have to finnish this mail....)

If this mail sounds like a tribute and hail to Joseph and his amazing work on the neural net, I must say it acctually _is_ a tribute. Without his intelligence, his insight, his computer wizardry, his push and go-ahead spirit, the GNU Backgammon project would still have been a poor player with a fibs rating about 1600. The backgammon community all over the world owes him a lot. THANK YOU, PEPE!

Thanks!

While GNUbg has come a long way, the NN work just explores the tip of the iceberg.

Furthermore, no matter how good an engine is, without the right features and a good user interface the program will not get used.

-Joseph


Thomas, I hope this gives you some of the story and some info on the training techniques used in GNU Backgammon

Strongest in the World?
I actually feel more confident with the analysis done by Michael Depreli at GammOnLine. Search net for his results. He's probably reading this mail, so I guess he can mail you his methods and final results.


I hope he does. I don't subscribe to GammonLine so someone will have to help me out here ;-)


Here is some data:
http://groups.google.com/groups?q=g:thl3357767960d&dq=&hl=en&lr=&ie=UTF-8&oe=utf-8&selm=f9846eb9.0306231441.3f641af4%40posting.google.com

-Øystein
(Sorry the typos, it's late here in Norway)



_______________________________________________
Bug-gnubg mailing list
address@hidden
http://mail.gnu.org/mailman/listinfo/bug-gnubg








reply via email to

[Prev in Thread] Current Thread [Next in Thread]