Re: [Computer-go] Need help with fuego source code
Hi Rene, It may have sounded like you describe it but I think it's still a bit different. I don't think opening books go deep into the game. For example if I say the top N moves right now that means N=100. But that could change to 150 or more depending on the quality of the predictor. Also opening book lookups don't consider the whole board but just local situations as far as i know. But I will remember what you said and if I still have time for it I will look into the Fuego's opening book code. David 2013/6/24 René van de Veerdonk > Looking at it from a distance, this sounds like a fancy way of saying that > you created an opening book. This may sound a little strange and a > mis-characterization of your effort, but please entertain the thought for a > while. What you are attempting to do is to bias the move selection in the > opening phase using priors on the top-30 moves. Perhaps Fuego's opening > book code would allow you to import your weights outside of the > tree/playout code. Now, typically opening books contains well-defined lines > of play, whereas yours would be a model, so integration may not be that > straightforward. You would also lose the guidance inside the random > playouts. > > Rene > > PS. Welcome to the list. > > > On Mon, Jun 24, 2013 at 8:33 AM, David Briemann wrote: > >> Well it is an attempt to improve the playing strength, but that won't >> mean that it succeeds. >> >> What I do is the following(in short): >> I have a trained move predictor model which consumes a board situation >> and outputs beliefs for every playable move. >> I want to use it to bias the search tree for the first N moves of a game >> (opening phase). >> >> So when tree search generates all legal moves, the predictor will score >> them and only consider the best X move as legal moves. >> >> It then should be forced to play "good" opening moves(of couse only if >> the predictions make sense). >> >> David >> >> >> 2013/6/24 Don Dailey >> >>> >>> On Mon, Jun 24, 2013 at 7:58 AM, David Briemann wrote: >>> I'm beginning to think that I didn't understand the tree search part correctly. You say the tree search generates moves too. I thought moves were only generated in playouts and the tree search part was to follow already played lines until it reaches a position which has not been played out. Probably that's the location were I have too look into. >>> >>> I don't know the gory details of the implementation, but clearly the >>> tree portion of the search considers all moves (sooner or later) and much >>> has been written about how MCTS is admissible - at least in theory.That >>> means it would, if given enough time and memory, play perfect go and will >>> consider every legal move at some point.But we know that playouts are >>> not fully random and in many positions will only play a limited number of >>> moves (perhaps just one) such as when defending atari. So the search >>> tree portion is not constrained by only what the next playout move will >>> return. >>> >>> Read the code - and perhaps any documentation that comes with this >>> program. One this is clear to me though, if you impose patterns >>> non-probabilistically on the tree you will weaken the program considerably. >>> The reason MCTS works so incredibly well is that we have put patterns >>> in their proper place, as move guidance and not as a plausible move >>> generator only. The old style weak programs were heavily pattern based. >>> So I may be misunderstanding what you are trying to do - is this a >>> study of some kind or a real attempt to improve the program? >>> >>> Don >>> >>> >>> ___ >>> Computer-go mailing list >>> Computer-go@dvandva.org >>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >>> >> >> >> ___ >> Computer-go mailing list >> Computer-go@dvandva.org >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
Looking at it from a distance, this sounds like a fancy way of saying that you created an opening book. This may sound a little strange and a mis-characterization of your effort, but please entertain the thought for a while. What you are attempting to do is to bias the move selection in the opening phase using priors on the top-30 moves. Perhaps Fuego's opening book code would allow you to import your weights outside of the tree/playout code. Now, typically opening books contains well-defined lines of play, whereas yours would be a model, so integration may not be that straightforward. You would also lose the guidance inside the random playouts. Rene PS. Welcome to the list. On Mon, Jun 24, 2013 at 8:33 AM, David Briemann wrote: > Well it is an attempt to improve the playing strength, but that won't mean > that it succeeds. > > What I do is the following(in short): > I have a trained move predictor model which consumes a board situation and > outputs beliefs for every playable move. > I want to use it to bias the search tree for the first N moves of a game > (opening phase). > > So when tree search generates all legal moves, the predictor will score > them and only consider the best X move as legal moves. > > It then should be forced to play "good" opening moves(of couse only if the > predictions make sense). > > David > > > 2013/6/24 Don Dailey > >> >> On Mon, Jun 24, 2013 at 7:58 AM, David Briemann wrote: >> >>> I'm beginning to think that I didn't understand the tree search part >>> correctly. You say the tree search generates moves too. I thought moves >>> were only generated in playouts and the tree search part was to follow >>> already played lines until it reaches a position which has not been played >>> out. Probably that's the location were I have too look into. >>> >> >> I don't know the gory details of the implementation, but clearly the >> tree portion of the search considers all moves (sooner or later) and much >> has been written about how MCTS is admissible - at least in theory.That >> means it would, if given enough time and memory, play perfect go and will >> consider every legal move at some point.But we know that playouts are >> not fully random and in many positions will only play a limited number of >> moves (perhaps just one) such as when defending atari. So the search >> tree portion is not constrained by only what the next playout move will >> return. >> >> Read the code - and perhaps any documentation that comes with this >> program. One this is clear to me though, if you impose patterns >> non-probabilistically on the tree you will weaken the program considerably. >> The reason MCTS works so incredibly well is that we have put patterns >> in their proper place, as move guidance and not as a plausible move >> generator only. The old style weak programs were heavily pattern based. >> So I may be misunderstanding what you are trying to do - is this a >> study of some kind or a real attempt to improve the program? >> >> Don >> >> >> ___ >> Computer-go mailing list >> Computer-go@dvandva.org >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
Well it is an attempt to improve the playing strength, but that won't mean that it succeeds. What I do is the following(in short): I have a trained move predictor model which consumes a board situation and outputs beliefs for every playable move. I want to use it to bias the search tree for the first N moves of a game (opening phase). So when tree search generates all legal moves, the predictor will score them and only consider the best X move as legal moves. It then should be forced to play "good" opening moves(of couse only if the predictions make sense). David 2013/6/24 Don Dailey > > On Mon, Jun 24, 2013 at 7:58 AM, David Briemann wrote: > >> I'm beginning to think that I didn't understand the tree search part >> correctly. You say the tree search generates moves too. I thought moves >> were only generated in playouts and the tree search part was to follow >> already played lines until it reaches a position which has not been played >> out. Probably that's the location were I have too look into. >> > > I don't know the gory details of the implementation, but clearly the tree > portion of the search considers all moves (sooner or later) and much has > been written about how MCTS is admissible - at least in theory.That > means it would, if given enough time and memory, play perfect go and will > consider every legal move at some point.But we know that playouts are > not fully random and in many positions will only play a limited number of > moves (perhaps just one) such as when defending atari. So the search > tree portion is not constrained by only what the next playout move will > return. > > Read the code - and perhaps any documentation that comes with this > program. One this is clear to me though, if you impose patterns > non-probabilistically on the tree you will weaken the program considerably. > The reason MCTS works so incredibly well is that we have put patterns > in their proper place, as move guidance and not as a plausible move > generator only. The old style weak programs were heavily pattern based. > So I may be misunderstanding what you are trying to do - is this a > study of some kind or a real attempt to improve the program? > > Don > > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
Thanks for you input Don! You are absolutely right. I tried to bias the search in the wrong location. I fixed this now and hacked the GenerateLegalMoves moves function, which is used by the tree search. This seems to fix the problem. Now i have to run tests for evaluation. Regards, David 2013/6/24 Don Dailey > It seems to me that you want to change the TREE portion of the playouts to > only consider moves your predictor sanctions.Am I misunderstanding > this?The tree portion of the search is still going to try every move at > least a few times (depending on the level set) and the only way to > guarantee that it never choose a move to play is if you somehow invalid > these. You could use a hack which is to give them very low bogus scores > or make it appear to the program that these moves do not even exist - but > the normal flow of the program will cause them to still be considered > regardless of anything you do with playouts. > > Don > > > On Mon, Jun 24, 2013 at 7:58 AM, David Briemann wrote: > >> Hi Aja, >> >> What the picture shows is just the result of the current board situation >> fed into the predictor, namely the first 30 moves the predictor recommends. >> >> The only thing I changed in how Fuego works is how the random playouts >> (GOUCT_RANDOM) are done. They are not just random anymore but semi-random >> biased by the predictor. >> >> So Fuego does still try to generate moves with heuristics and only if all >> heuristics fail it uses random playouts(which I biased). >> >> >> And by "play different moves" I mean the moves Fuego actually plays after >> finishing calculations. What I want is to forbid Fuego to even consider >> certain moves(the bad ones, according to the predictor). If you look at my >> screenshot.. I want Fuego to only consider the moves marked with numbers. >> >> I'm beginning to think that I didn't understand the tree search part >> correctly. You say the tree search generates moves too. I thought moves >> were only generated in playouts and the tree search part was to follow >> already played lines until it reaches a position which has not been played >> out. Probably that's the location were I have too look into. >> >> David >> >> >> 2013/6/24 Aja Huang >> >>> Hi David, >>> >>> 2013/6/24 David Briemann To give you an impression, this is what it looks like in fuego for a well known opening position: http://www.abload.de/img/board7brdj.png So what is puzzling me right now is this: Even if I limit the possible playout moves to the best Y predictions, fuego will play different moves. For example in the linked picture it could play K11, which is not in the predictor move list. This happens too if I disable all heuristics and just do the biased playouts. >>> >>> By "play different moves" do you mean the moves generated by the tree >>> search or playout policy? From the linked picture it looks like the moves >>> proposed by priors and being searched, since Fuego doesn't consider global >>> patterns playouts in the current version. >>> >>> Aja >>> >>> ___ >>> Computer-go mailing list >>> Computer-go@dvandva.org >>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >>> >> >> >> ___ >> Computer-go mailing list >> Computer-go@dvandva.org >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
Thank you very much for that link Aja. it will certainly be helpful. I just discovered another very helpful document on the matter: http://users.soe.ucsc.edu/~glin/docs/Fuego_Fall09Report.pdf I leave it here in case someone else needs that information too. David 2013/6/24 Aja Huang > 2013/6/24 David Briemann >> >> I'm beginning to think that I didn't understand the tree search part >> correctly. You say the tree search generates moves too. I thought moves >> were only generated in playouts and the tree search part was to follow >> already played lines until it reaches a position which has not been played >> out. Probably that's the location were I have too look into. >> > > To understand the framework of Fuego, this paper is a good start > > Fuego - An Open-Source Framework for Board Games and Go Engine Based on > Monte Carlo Tree Search > http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf > > particularly Section 3 The Fuego Engine, where it describes Fuego's > playout policy and the full-board MCTS generator. > > Aja > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
On Mon, Jun 24, 2013 at 7:58 AM, David Briemann wrote: > I'm beginning to think that I didn't understand the tree search part > correctly. You say the tree search generates moves too. I thought moves > were only generated in playouts and the tree search part was to follow > already played lines until it reaches a position which has not been played > out. Probably that's the location were I have too look into. > I don't know the gory details of the implementation, but clearly the tree portion of the search considers all moves (sooner or later) and much has been written about how MCTS is admissible - at least in theory.That means it would, if given enough time and memory, play perfect go and will consider every legal move at some point.But we know that playouts are not fully random and in many positions will only play a limited number of moves (perhaps just one) such as when defending atari. So the search tree portion is not constrained by only what the next playout move will return. Read the code - and perhaps any documentation that comes with this program. One this is clear to me though, if you impose patterns non-probabilistically on the tree you will weaken the program considerably. The reason MCTS works so incredibly well is that we have put patterns in their proper place, as move guidance and not as a plausible move generator only. The old style weak programs were heavily pattern based. So I may be misunderstanding what you are trying to do - is this a study of some kind or a real attempt to improve the program? Don ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
2013/6/24 David Briemann > > I'm beginning to think that I didn't understand the tree search part > correctly. You say the tree search generates moves too. I thought moves > were only generated in playouts and the tree search part was to follow > already played lines until it reaches a position which has not been played > out. Probably that's the location were I have too look into. > To understand the framework of Fuego, this paper is a good start Fuego - An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf particularly Section 3 The Fuego Engine, where it describes Fuego's playout policy and the full-board MCTS generator. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
It seems to me that you want to change the TREE portion of the playouts to only consider moves your predictor sanctions.Am I misunderstanding this?The tree portion of the search is still going to try every move at least a few times (depending on the level set) and the only way to guarantee that it never choose a move to play is if you somehow invalid these. You could use a hack which is to give them very low bogus scores or make it appear to the program that these moves do not even exist - but the normal flow of the program will cause them to still be considered regardless of anything you do with playouts. Don On Mon, Jun 24, 2013 at 7:58 AM, David Briemann wrote: > Hi Aja, > > What the picture shows is just the result of the current board situation > fed into the predictor, namely the first 30 moves the predictor recommends. > > The only thing I changed in how Fuego works is how the random playouts > (GOUCT_RANDOM) are done. They are not just random anymore but semi-random > biased by the predictor. > > So Fuego does still try to generate moves with heuristics and only if all > heuristics fail it uses random playouts(which I biased). > > > And by "play different moves" I mean the moves Fuego actually plays after > finishing calculations. What I want is to forbid Fuego to even consider > certain moves(the bad ones, according to the predictor). If you look at my > screenshot.. I want Fuego to only consider the moves marked with numbers. > > I'm beginning to think that I didn't understand the tree search part > correctly. You say the tree search generates moves too. I thought moves > were only generated in playouts and the tree search part was to follow > already played lines until it reaches a position which has not been played > out. Probably that's the location were I have too look into. > > David > > > 2013/6/24 Aja Huang > >> Hi David, >> >> 2013/6/24 David Briemann >>> >>> To give you an impression, this is what it looks like in fuego for a >>> well known opening position: http://www.abload.de/img/board7brdj.png >>> >>> So what is puzzling me right now is this: Even if I limit the possible >>> playout moves to the best Y predictions, fuego will play different moves. >>> For example in the linked picture it could play K11, which is not in the >>> predictor move list. This happens too if I disable all heuristics and just >>> do the biased playouts. >>> >> >> By "play different moves" do you mean the moves generated by the tree >> search or playout policy? From the linked picture it looks like the moves >> proposed by priors and being searched, since Fuego doesn't consider global >> patterns playouts in the current version. >> >> Aja >> >> ___ >> Computer-go mailing list >> Computer-go@dvandva.org >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
Hi Aja, What the picture shows is just the result of the current board situation fed into the predictor, namely the first 30 moves the predictor recommends. The only thing I changed in how Fuego works is how the random playouts (GOUCT_RANDOM) are done. They are not just random anymore but semi-random biased by the predictor. So Fuego does still try to generate moves with heuristics and only if all heuristics fail it uses random playouts(which I biased). And by "play different moves" I mean the moves Fuego actually plays after finishing calculations. What I want is to forbid Fuego to even consider certain moves(the bad ones, according to the predictor). If you look at my screenshot.. I want Fuego to only consider the moves marked with numbers. I'm beginning to think that I didn't understand the tree search part correctly. You say the tree search generates moves too. I thought moves were only generated in playouts and the tree search part was to follow already played lines until it reaches a position which has not been played out. Probably that's the location were I have too look into. David 2013/6/24 Aja Huang > Hi David, > > 2013/6/24 David Briemann >> >> To give you an impression, this is what it looks like in fuego for a well >> known opening position: http://www.abload.de/img/board7brdj.png >> >> So what is puzzling me right now is this: Even if I limit the possible >> playout moves to the best Y predictions, fuego will play different moves. >> For example in the linked picture it could play K11, which is not in the >> predictor move list. This happens too if I disable all heuristics and just >> do the biased playouts. >> > > By "play different moves" do you mean the moves generated by the tree > search or playout policy? From the linked picture it looks like the moves > proposed by priors and being searched, since Fuego doesn't consider global > patterns playouts in the current version. > > Aja > > ___ > Computer-go mailing list > Computer-go@dvandva.org > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Need help with fuego source code
Hi David, 2013/6/24 David Briemann > > To give you an impression, this is what it looks like in fuego for a well > known opening position: http://www.abload.de/img/board7brdj.png > > So what is puzzling me right now is this: Even if I limit the possible > playout moves to the best Y predictions, fuego will play different moves. > For example in the linked picture it could play K11, which is not in the > predictor move list. This happens too if I disable all heuristics and just > do the biased playouts. > By "play different moves" do you mean the moves generated by the tree search or playout policy? From the linked picture it looks like the moves proposed by priors and being searched, since Fuego doesn't consider global patterns playouts in the current version. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] Need help with fuego source code
Hi, I'm reading this mailing list for a while but I've never wrote something here until now. I'm currently in a late phase of my master thesis on a move predictor for computer go. I have several working move predictors trained on a large set of 6d+ amateur games. My current goal is to use the move predictor as an extension to an existing go mcts engine. Most of all I want to use it for the opening phase of the game to produce better quality moves. I've chosen Fuego since it's written in c++ which I'm more comfortable with than c(pachi). I have extended the GoUctPlayoutPolicy::GenerateMove() function. It still tries to generate moves with heuristics first( nakade, atari, etc.) but after that the random move selection is biased. The move predictor scores all empty/valid moves and then a move is chosen based on the probabilities. This is only done for board situations with less than X stones(x is 100 right now). Also i limit the possible moves at this stage to the best Y predictions made(Y is 30 right now). To give you an impression, this is what it looks like in fuego for a well known opening position: http://www.abload.de/img/board7brdj.png So what is puzzling me right now is this: Even if I limit the possible playout moves to the best Y predictions, fuego will play different moves. For example in the linked picture it could play K11, which is not in the predictor move list. This happens too if I disable all heuristics and just do the biased playouts. So my guess is, Fuego is doing searches somewhere else too, which are independent from the GoUctPlayoutPolicy::GenerateMove() function. Does anybody have an idea what I am missing here? And how I can limit fuego to only consider some moves? Sorry for this longish text. Best regards, David Briemann ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
