RE: [computer-go] Re: Hardware limits
Still, in the unlimited class of a rally from Bagdad to Beijing, it is probably not the dragracer nor the solar car that wins, but the landrover with good road maps and a GPS. I agree with most posters that in the end, you have to find the best thing to do the job. Hardware could play a major role in your solution, but you need more than just that to win. Dave Van: computer-go-boun...@computer-go.org namens Ryan Grant Verzonden: vr 16-1-2009 3:55 Aan: computer-go Onderwerp: Re: [computer-go] Re: Hardware limits On Thu, Jan 15, 2009 at 8:47 AM, steve uurtamo wrote: > this isn't an asymptotic problem requiring an algorithmic > solution. this is a fixed-size board requiring a "best of show" > answer. whoever gets there, however they get there, deserves > to win, as long as the machines are choosing their own > moves. scalability is still essential and beautiful. the "unlimited class" winner will always be important. hardware access is very unevenly distributed. yet access to hardware currently matters in every tournament. some people like that part of the game, some don't. there is the potential for people in this community to speak up and create a culture that rewards good algorithm design as much as possible. to do so requires at least noticing hardware power. -- - Ryan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hardware limits
On Thu, Jan 15, 2009 at 8:47 AM, steve uurtamo wrote: > this isn't an asymptotic problem requiring an algorithmic > solution. this is a fixed-size board requiring a "best of show" > answer. whoever gets there, however they get there, deserves > to win, as long as the machines are choosing their own > moves. scalability is still essential and beautiful. the "unlimited class" winner will always be important. hardware access is very unevenly distributed. yet access to hardware currently matters in every tournament. some people like that part of the game, some don't. there is the potential for people in this community to speak up and create a culture that rewards good algorithm design as much as possible. to do so requires at least noticing hardware power. -- - Ryan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hardware limits
my biased $0.02: i don't think that the point is to call it even. someone's got to win, and everyone else has to come in <= 2nd place. moreover, pretending as if this is the kind of contest that can be won with money (or hardware) alone is just sour grapes. one way to make this a contest about algorithms would be to require everyone's code to run on identical hardware under the identical operating system. how much fun would that be? not very much at all. imagine that you're used to being able to fit a very frequently-accessed table entirely in ram. in fact, many of your other data structures and code flow are built around the fact that it fits entirely in ram on your box. then imagine that the contest hardware has less ram and that you get to spend 90% of your "thinking time" watching the machine swap, or rewrite all of your code. no thanks. sure, this is the opposite of the problem that is being described -- instead of it being a sad story for the guy who has tiny hardware, it's a sad story for the guy who has access to better hardware. in neither case is it a really sad story, however. it's just that arbitrary limits always cause problems for somebody. the *only* time where hardware could really become an issue is if everyone competing is using algorithms all of which scale at roughly the same rate, all of which parallelize at roughly the same rate, etc. talk about a boring contest! this isn't an asymptotic problem requiring an algorithmic solution. this is a fixed-size board requiring a "best of show" answer. whoever gets there, however they get there, deserves to win, as long as the machines are choosing their own moves. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to "properly" implement RAVE?
On 12:53 Thu 15 Jan , Mark Boon wrote: > > On Jan 15, 2009, at 12:33 PM, Daniel Waeber wrote: > > > yes, but the weight/color maps stay the same for all updated nodes. > > > > I think the first playoutNode (the one most deep inside the tree) only > > should get amaf values for the random playout, the next one form > > random > > playout + from the first playoutNode ... and the root node amaf values > > form all the nodes. > > OK, I think I see now what you're trying to say. This is something I > did think about. I hope my memory serves me well enough to say why I > didn't do it that way. > > - What you propose adds complexity and possibly computation (if it > means recalculating or adjusting the weight map). > - I don't think it makes all that much difference. > > The reason I don't think it makes much difference is that adding AMAF > values for the moves above (closer to the root) the playoutNode is > that most likely those points are now occupied. Since the AMAF values > are used to compute which empty points are the best next candidate, > the AMAF values at occupied points are immaterial. They are not even > added. So it only makes a difference in cases where played stones get > captured and those points then are occupied again. This brings us back > to the issue discussed earlier about ko and ishi-no-shita. Yes, I don't know if it would be a big improvement. It is not a real speed decrease, as you just move the point were you add the additional values to the maps. Perhaps I'll run some tests when I have the time. > Mark > > P.S. what do I need to open that file? Is it a SVN patch? it's standard diff format, outputed by git. You can view it with a text editor and apply it with unix "patch" commandline tool or use eclipse->team->apply-patch. it's done agains svn-root, so you have to ignore 2 leading pathnames if you apply it inside the refbot folder. regards wabu ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to "properly" implement RAVE?
On Jan 15, 2009, at 12:33 PM, Daniel Waeber wrote: yes, but the weight/color maps stay the same for all updated nodes. I think the first playoutNode (the one most deep inside the tree) only should get amaf values for the random playout, the next one form random playout + from the first playoutNode ... and the root node amaf values form all the nodes. OK, I think I see now what you're trying to say. This is something I did think about. I hope my memory serves me well enough to say why I didn't do it that way. - What you propose adds complexity and possibly computation (if it means recalculating or adjusting the weight map). - I don't think it makes all that much difference. The reason I don't think it makes much difference is that adding AMAF values for the moves above (closer to the root) the playoutNode is that most likely those points are now occupied. Since the AMAF values are used to compute which empty points are the best next candidate, the AMAF values at occupied points are immaterial. They are not even added. So it only makes a difference in cases where played stones get captured and those points then are occupied again. This brings us back to the issue discussed earlier about ko and ishi-no-shita. Mark P.S. what do I need to open that file? Is it a SVN patch? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to "properly" implement RAVE?
Hi,
On 11:24 Thu 15 Jan , Mark Boon wrote:
>
> On Jan 15, 2009, at 10:47 AM, Daniel Waeber wrote:
>
> > Thanks you. I think that I understand it now :)
> >
> > On 23:21 Wed 14 Jan , Mark Boon wrote:
> >> You have to understand that the 'start' variable really starts at the
> >> root from the position for which we do the search. So all the moves
> >> 'below' the playoutNode are also taken into account. The check in the
> >> earlier part "if (_colorMap[moveXY]==0)" makes sure there's no move
> >> between the playoutNode and the n.move as you call it.
> >
> > Ah, yes, I did not get the meaning of start right. But still I think
> > you
> > have to incrementally add values to the maps as you go down the tree.
>
> But it does that. This happens when playoutNode is set to its parent
> and the AMAF values are added again (now for the other color) until
> the root is reached.
yes, but the weight/color maps stay the same for all updated nodes.
I think the first playoutNode (the one most deep inside the tree) only
should get amaf values for the random playout, the next one form random
playout + from the first playoutNode ... and the root node amaf values
form all the nodes.
I attached code for what I would do, but had no time to test it.
> > I think there's a problem with caputres/ko-fights inside the tree.
> > All nodes after the capture should get the amaf color/value for the
> > stones put there after the capture and not the value of the stones
> > that
> > were put there and captured.
> >
> > Most likely I missed a little piece of code again, but hey, perhaps
> > its
> > a real bug.
>
> I did stop to think about ko and 'ishi no shita' (something like
> 'playing under the stones') a little bit but couldn't come to an
> immediate conclusion what would be the best thing to do. So I decided
> to leave it as it is. You didn't miss any little piece of code there.
> Maybe there's room for improvement in case of ko, but my guess is the
> difference will be minimal at best. If you find it does make a big
> difference everyone here will be delighted to hear it.
>
> Given how it's performing I doubt there are major problems with my
> AMAF-RAVE implementation.
regards
wabu
>
> Mark
>
diff --git a/TesujiRefBot/source/tesuji/games/go/reference/search/MonteCarloTreeSearch.java b/TesujiRefBot/source/tesuji/games/go/reference/search/MonteCarloTreeSearch.java
index 5e47e00..ee650e1 100644
--- a/TesujiRefBot/source/tesuji/games/go/reference/search/MonteCarloTreeSearch.java
+++ b/TesujiRefBot/source/tesuji/games/go/reference/search/MonteCarloTreeSearch.java
@@ -566,6 +566,7 @@ public class MonteCarloTreeSearch
TreeNode> node = getNodeToExpand(_rootNode, _searchAdministration);
TreeNode> playoutNode = node;
+ int start = _searchAdministration.getMoveStack().getSize(); // begin at playoutNode
if (node != null)
{
@@ -580,7 +581,6 @@ public class MonteCarloTreeSearch
{
IntStack playoutMoves = _searchAdministration.getMoveStack();
byte color = _monteCarloAdministration.getColorToMove();
- int start = _monteCarloAdministration.getMoveStack().getSize();
int end = playoutMoves.getSize();
double weight = 1.0;
double weightDelta = 1.0 / (end - start + 1); // Michael Williams' idea to use decreasing weights
@@ -613,6 +613,13 @@ public class MonteCarloTreeSearch
if (_colorMap[xy]==color)
result.increaseVirtualPlayouts(_weightMap[xy]*score,_weightMap[xy]);
}
+ // add the move to the maps now
+ GoMove move = (GoMove) playoutNode.getContent().getMove();
+ int xy = move.getXY();
+ byte col = move.getColor();
+ _colorMap[xy] = col;
+ _weightMap[xy] = 1.0; //TODO: handle weight
+
playoutNode = playoutNode.getParent();
}
}
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to "properly" implement RAVE?
On Jan 15, 2009, at 10:47 AM, Daniel Waeber wrote: Thanks you. I think that I understand it now :) On 23:21 Wed 14 Jan , Mark Boon wrote: You have to understand that the 'start' variable really starts at the root from the position for which we do the search. So all the moves 'below' the playoutNode are also taken into account. The check in the earlier part "if (_colorMap[moveXY]==0)" makes sure there's no move between the playoutNode and the n.move as you call it. Ah, yes, I did not get the meaning of start right. But still I think you have to incrementally add values to the maps as you go down the tree. But it does that. This happens when playoutNode is set to its parent and the AMAF values are added again (now for the other color) until the root is reached. I think there's a problem with caputres/ko-fights inside the tree. All nodes after the capture should get the amaf color/value for the stones put there after the capture and not the value of the stones that were put there and captured. Most likely I missed a little piece of code again, but hey, perhaps its a real bug. I did stop to think about ko and 'ishi no shita' (something like 'playing under the stones') a little bit but couldn't come to an immediate conclusion what would be the best thing to do. So I decided to leave it as it is. You didn't miss any little piece of code there. Maybe there's room for improvement in case of ko, but my guess is the difference will be minimal at best. If you find it does make a big difference everyone here will be delighted to hear it. Given how it's performing I doubt there are major problems with my AMAF-RAVE implementation. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hardware limits
The thing about computer chess is that "the swift do not always win the race." Many times in the past modest hardware has beaten powerful hardware. Even Deep Blue didn't always win the tournaments it played in. They came to one competition and Campbell told me that they had estimated their winning chances at about 50/50 - which was far ahead of any of the other competitors. As it turns out, Fritz won that particular time on one of the least powerful machines that was at that tournament. - Don On Wed, 2009-01-14 at 22:27 -0800, Dave Dyer wrote: > Lets look at it another way - no one would care what hardware > you choose to use, unless you win. So at the very least, you > ought to be able to use arbitrary hardware until it becomes > established that only that class of hardware can win. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hardware limits
Hi Joshua, Yes, I think it was implicitly understood that these chess competitions were about creating the best chess playing (non-human) entity. However human nature being what it is we attach the author to the program and judge the author through his program. However, if you create a really strong program even on modest hardware, opportunities open up. Some company, or in my case a university, will approach you and give you some support. - Don On Thu, 2009-01-15 at 00:16 -0500, Joshua Shriver wrote: > When I was big into Chess programming this was a sore topic for me as > well. I felt it was unfair for people competing in the WCCC to win if > they had a cluster of of 100 PCs, a Cray, etc, when another person > was using a P200mhz. > > I believe it was Dr. Hyatt that said this and it made a lot of sense > to me "It's not just about creating the best chess program, it's > creating the best playing machine" > > So when you look at competitions that dont have hardware limits, you > can't look at it like Engine X is the best in the world. You have to > look at it like Engine X + this hardware setup is the best in the > world; and take it with a grain of salt. > > Even if you did set hardware limits, it would be a hard task. Even if > it's just a single PC do you use single core or multicore? Multicore > would help those who have parallelized their code but hurt others. Is > it fair? There's no real line that can be drawn, because on the flip > side I wouldnt find it fair if I had written a parallel engine and > spent all that time and effort to only be limited to 1 core. > > Just my $0.02. > -Josh > > > > For now I tend to be of the opinion that in competitions, one > should be able to bring your own hardware or run on standard > hardware provided by organizers. The restriction that the > hardware be physically present allows for enough flexibility > that people or teams can try different set-ups (like a row of > PS3s) while avoiding having people with access to a big > cluster compete with people who only have access to a PC. > > But similarly to the competition of building the most powerful > computer in the world, I can see room for a competition > between big clusters that play Go as well. One doesn't have to > be to the exclusion of the other. Think of car-racing. You > have drag-racing where they use rockets to cross half a mile > as fast as possible and you have F1-racing where the > 'hardware' is constrained within certain limits. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to "properly" implement RAVE?
Thanks you. I think that I understand it now :) On 23:21 Wed 14 Jan , Mark Boon wrote: > You have to understand that the 'start' variable really starts at the > root from the position for which we do the search. So all the moves > 'below' the playoutNode are also taken into account. The check in the > earlier part "if (_colorMap[moveXY]==0)" makes sure there's no move > between the playoutNode and the n.move as you call it. Ah, yes, I did not get the meaning of start right. But still I think you have to incrementally add values to the maps as you go down the tree. I think there's a problem with caputres/ko-fights inside the tree. All nodes after the capture should get the amaf color/value for the stones put there after the capture and not the value of the stones that were put there and captured. Most likely I missed a little piece of code again, but hey, perhaps its a real bug. > That is, if I understand you correctly. Because I'm not quite sure > what you mean by 'finding all these nodes n'. This is not a sub-set of > RAVE as I understand it. What you see in the code is the accumulation > of the AMAF values after each playout. The RAVE value is calculated > using these values when comparing move-candidates, which is in an > altogether different place. (The MonteCarloTreeSearchResult class in > my project). > > I'm afraid I haven't made things much clearer for you. The problem is that I was confused, but now, as I understand it, all your and all the other comments suddenly make sense ;) > Mark Thank again, wabu ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
