Re: [computer-go] Monte-Carlo Tree Search reference bot
On 27-nov-08, at 19:50, Denis fidaali wrote: So, you use AMAF for "simulating" the first UCT evaluations ? I though the classical way to use AMAF, was to affect only the win/lose ratio portion of the uct equation. Obvioulsy it should be allowed to use an arbitrary large number of AMAF simulation accumulating them longer than what it take to expand a node. I think that a classical way to affect the win/ratio is to decrease the effect of the AMAF correction as the number of simulation grows. If you test with a very low number of simulation (in the 1000 - 3000 range), i think you should be able to get out a very nice improvement out of the AMAF version. If you don't, i would think that something is wrong somewhere. What test process do you use for this version ? I tested it mostly doing 2,000 playouts. When AMAF is true I create a map of virtual-win values of all the moves played during a playout. These values get accumulated over all the playouts (not just the first ones). The 'virtual-value' of a move is calculated as follows: exploration-factor * UCT + ( (nr-wins*2 + nr-virtual-wins) / (nr- playouts*2 + nr-virtual-playouts)) where the exploration-factor is currently sqrt(0.2) and UCT is sqrt ( log( nr-parent-playouts ) / ( nr-playouts+1) ) Like I said, I haven't had time to experiment much so this formula may not be any good. I had also expected to see some positive effect of the virtual-win / virtual-playout ratio from AMAF, but I see none. Of course it's also possible I have a different kind of bug still. What happens in my 'formula' is that when it never expands beyond the first level, which is what happens if the number of simulations is equal to the number of simulations before expansion, the virtual- value becomes completely determined by nr-virtual-wins / nr-virtual- playouts making it equivalent to the original ref-bot. In case it does expand further and creates a tree, the actual win-loss ratio is weighed twice as heavily as the virtual win-loss ratio. That seemed like a reasonable first try. I have tried a few others, but usually didn't get much different results or much worse results. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Re: hex robot
>The use of C is almost the only choice, but I'm on the lookout for the >next wave of languages that will be: > 1. Native code compiled - no external runtime required. > 2. High level language features, but not imposed on you. Have a look at Haskell (www.haskell.org). I don't want to get into language advocacy (you'll find enough of that elsewhere;-), so I'll just address your points: 1. GHC compiles to native code (either via C or, increasingly, directly) 2. Higher-level language features are strongly suggested (and even higher- level features are being worked on continuously), but not imposed - if you want to write C-style code in Haskell, you can (just don't show it:-) (and if you absolutely want to write the inner loop in C, Haskell has a nice foreign function interface - it gets a lot of its libraries from importing the C APIs and wrapping higher-level safer interfaces on top; so you always have the fallback of writing a few core pieces in C for speed while writing the framework and interface code in Haskell for expressiveness) You also mentioned string handling, which harks back to your second point above: a game engines involves many tasks, not all of which require low-level bit-fiddling, so you actually need to be able to mix high- and low-level code as appropriate. Again, Haskell allows this. Disclaimer: Haskell is by no means perfect, and I have many, many gripes with it and it implementations. But it is very good for increasingly many things, and games programming might well be one of it (I'm not yet sure about Go in particular - the performance-critical part of the code doesn't look much nicer than it would in C at the moment). The thing I like best is that it that it brings practitioners and researchers together in a fairly nice community (it used to be more research-heavy, but that has balanced over recent years). Claus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Monte-Carlo Tree Search reference bot
So, you use AMAF for "simulating" the first UCT evaluations ? I though the classical way to use AMAF, was to affect only the win/lose ratio portion of the uct equation. Obvioulsy it should be allowed to use an arbitrary large number of AMAF simulation accumulating them longer than what it take to expand a node. I think that a classical way to affect the win/ratio is to decrease the effect of the AMAF correction as the number of simulation grows. If you test with a very low number of simulation (in the 1000 - 3000 range), i think you should be able to get out a very nice improvement out of the AMAF version. If you don't, i would think that something is wrong somewhere. What test process do you use for this version ? > From: [EMAIL PROTECTED] > Date: Thu, 27 Nov 2008 18:15:34 -0200 > To: computer-go@computer-go.org > CC: > Subject: [computer-go] Monte-Carlo Tree Search reference bot > > I have added a MCTS implementation to my reference-bot project. It > allows you to specify how many nodes to search, after how many nodes > to expand and whether to use AMAF or not. If you specify the number > of nodes before expansion to be the same as the total number of nodes > to search and set AMAF to true you get the equivalent of Don's > original ref-bot. When you set AMAF to false and set the number of > nodes before epxansion to 1 you get my original UCT search algorithm. > > Between those extremes there might be a good formula to combine AMAF > with tree-search, but unfortunately I haven't had time lately to look > for one. The few small attempts I made show no benefit using AMAF in > tree-search, only when used on a single level. The contrast between > the two exptremes is very stark, so I'm actually convinced there > should be a way to use both. This implementation is also quite a bit > slower than my original search algorithm but I also didn't have time > yet to trace it. It might simply be due to the different expansion > method, which is much more expensive with a value of 1. Also, > searching for the best UCT node gets more expensive with more > (unused) nodes on each level. Using a higher expansion value may > alleviate the performance hit. Anyway I think this is a reasonable > starting point. > > At first I intended to create a different project for the search > reference bot. But half of the code (the MC part) is the same. And I > don't want to end up having to maintain the same code in two places. > I also didn't want to separate out some code into a separate library > and making the structure for the simple ref-bot more complicated. > This organization may need some more thought though. > > I'll update the project pages tomorrow. > > Mark > > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _ Email envoyé avec Windows Live Hotmail. Dites adieux aux spam et virus, passez à Hotmail ! C'est gratuit ! http://www.windowslive.fr/hotmail/default.asp___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Monte-Carlo Tree Search reference bot
I have added a MCTS implementation to my reference-bot project. It allows you to specify how many nodes to search, after how many nodes to expand and whether to use AMAF or not. If you specify the number of nodes before expansion to be the same as the total number of nodes to search and set AMAF to true you get the equivalent of Don's original ref-bot. When you set AMAF to false and set the number of nodes before epxansion to 1 you get my original UCT search algorithm. Between those extremes there might be a good formula to combine AMAF with tree-search, but unfortunately I haven't had time lately to look for one. The few small attempts I made show no benefit using AMAF in tree-search, only when used on a single level. The contrast between the two exptremes is very stark, so I'm actually convinced there should be a way to use both. This implementation is also quite a bit slower than my original search algorithm but I also didn't have time yet to trace it. It might simply be due to the different expansion method, which is much more expensive with a value of 1. Also, searching for the best UCT node gets more expensive with more (unused) nodes on each level. Using a higher expansion value may alleviate the performance hit. Anyway I think this is a reasonable starting point. At first I intended to create a different project for the search reference bot. But half of the code (the MC part) is the same. And I don't want to end up having to maintain the same code in two places. I also didn't want to separate out some code into a separate library and making the structure for the simple ref-bot more complicated. This organization may need some more thought though. I'll update the project pages tomorrow. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: hex robot
On Thu, 2008-11-27 at 16:22 -0200, Mark Boon wrote: > Don, > > I'm not going to argue about the merits of Java or C++ as it won't > change anyone's point of view anyway. > > What you're arguing is you should use C/C++, period. Fine by me if > that's what you think is best. > > But that's not what Denis was saying. He didn't specify he'd start > with C/C++, although that may be likely. He was saying he would move > to a more flexible language like Java later. That's the part that > doesn't make sense to me. Your litany against Java seems irrelevant > in this context. I don't know what Denis meant, but it doesn't seem likely that he wanted to start with a low level language and then move up to a higher level language. That's what Dave Dyer thinks he meant and maybe he did mean that, but I'm inclined to believe we just didn't understand him. My "litany" wasn't supposed to be against Java. It was against what I consider to be a myth, the idea that it makes great sense to start with a high level language to figure out what you want, then recode it all from scratch in a high performance language. The use of C is almost the only choice, but I'm on the lookout for the next wave of languages that will be: 1. Native code compiled - no external runtime required. 2. High level language features, but not imposed on you. I think we are poised for this now. Lisaac seems promising, bitC, Digital Mars D, and Vala seems very interesting. I think there are couple of others mentioned here too. These all seem to be a step in the right direction to me, these are languages that can be used for very low level control without too many compromises. One of them could be the next C. We may look back in 10 or 20 years and see that we have been foolish. It could be that the problem is with the processors we use, designed a very specific way to basically support C programming. So maybe we are perpetuating our own nightmare. - Don > Mark > > On 27-nov-08, at 14:55, Don Dailey wrote: > > > On Thu, 2008-11-27 at 13:03 -0200, Mark Boon wrote: > >> You say you're going to try to make a prototype first and then > >> when it > >> shows promise, move to a more flexible language like Java. What > >> language are you intending to use? It seems the wrong way around to > >> me. Develop the prototype in a flexible language and when it seems to > >> work, move it to a specific langauge that can leverage some specific > >> CPU features. Seems to make much more sense to me. > > > > This is clearly the conventional wisdom, but I think it's a > > mistake for > > an "ultimately" high performance game program, even for an initial > > prototype. The supposed benefit is "freedom to experiment" and > > nail > > down your algorithm, but I think this is a myth. > > > > I know that sounds like blasphemy, but when I've tried this before I > > discovered that even though C/C++ is pretty gnarly, it has at least 3 > > major advantages that might not matter for many other things, but is > > very important for games: > > > >1. It's about as fast as you will get. > > > >2. It is superbly flexible. > > > >3. It is not a memory hog. > > > > > > To summarize my experiences, these wonderful high level languages are > > full of limitations and you spent more time pulling your hair out to > > work around them. Even the speed limitation is more of an issue > > that > > you think, if you make heavy use of testing. If you don't make heavy > > use of testing, you don't know what you are doing anyway. > > > > For instance, let's say you are experimenting with an algorithm. At > > some point you must test that algorithm to see if it's better than > > what > > you were doing, or to compare it with something else. You must play a > > large number of games to measure superiority, unless it is > > overwhelming. > > Most changes won't be overwhelming and even if it is you still need a > > lot of games to know how overwhelming it is. With a slower language > > this is correspondingly a slower process, negating much of the > > supposed > > high level language advantage. I spend more time waiting on tests > > than > > programming, even in C. > > > > Someone says, but if you have a large bank of workstations ...Well > > if you do, it doesn't change the fact that you are wasting them. An > > author for a strong playing engine for any game will be able to > > utilize > > as much power as you give him for testing. If I had 100 > > workstations I > > still would not use Ruby (a joy to program in and one of my favorites) > > because what a stupid waste of resources it would be to make those 100 > > workstations perform like only 2 or 3 workstations. > > > > > > When developing the simple reference bot, and experimenting with ideas > > to make it play better with fewer simulations, guess what? I am > > performance bound - I cannot test ideas fast enough and t
Re: [computer-go] Re: hex robot
On Thu, 2008-11-27 at 12:59 -0500, steve uurtamo wrote:
> don,
>
> i agree, although i will point out one of C's biggest flaws, which
> happens (conveniently for the sake of this argument) to be its
> least important one for game programming:
>
> string handling sucks
>
> if i never have to handle a string, i'll choose C without question.
> when i need to handle strings, i choose C with major reservations.
Yes, string handling is very low level and primitive in C. However it
doesn't seem much better in Java, if you are talking about Java.
Can it be worse than this? :
if (string1.equals(string2)) {
... do stuff
}
Ok, it's probably a little worse in C, but Java is no giant in string
handling.
the C way:
if (!strcmp(string1, string2)) {
... do stuff
}
A lot of times this comes down to what is abstracted away from your
control. For instance in C you can do tricks with pointer magic to
speed things up. In Java, some of this also happens underneath the
hood, for instance string space can be shared.I think the substring
method in Java doesn't allocate more space for storing the characters,
although it must need to create a new object. But my point is that all
of this is outside the control of the programmer, at least without
herculean efforts. That is almost always bad for performance
programming, when the compiler doesn't really know what you really
intend to do and makes too many decisions for you.
Of course there is another myth about this and it's not uncommon to see
blogs or diatribes about how compilers are much smarter than humans
about making decisions. I'm completely in favor of automating things
like memory management, instruction scheduling, and other low level
details that I don't want to be bothered with, but I disagree that
humans cannot compete. The truth is that most humans don't want to be
bothered with this because it's difficult, and we would rather have a
compiler make a good decision than for ourselves to have to take a lot
of time and effort making a better decision. Having said that, there
probably are specialized cases where even expert humans would be
significantly challenged to outperform a compiler in any significant
way.
- Don
>
> s.
signature.asc
Description: This is a digitally signed message part
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: hex robot
Don, I'm not going to argue about the merits of Java or C++ as it won't change anyone's point of view anyway. What you're arguing is you should use C/C++, period. Fine by me if that's what you think is best. But that's not what Denis was saying. He didn't specify he'd start with C/C++, although that may be likely. He was saying he would move to a more flexible language like Java later. That's the part that doesn't make sense to me. Your litany against Java seems irrelevant in this context. Mark On 27-nov-08, at 14:55, Don Dailey wrote: On Thu, 2008-11-27 at 13:03 -0200, Mark Boon wrote: You say you're going to try to make a prototype first and then when it shows promise, move to a more flexible language like Java. What language are you intending to use? It seems the wrong way around to me. Develop the prototype in a flexible language and when it seems to work, move it to a specific langauge that can leverage some specific CPU features. Seems to make much more sense to me. This is clearly the conventional wisdom, but I think it's a mistake for an "ultimately" high performance game program, even for an initial prototype. The supposed benefit is "freedom to experiment" and nail down your algorithm, but I think this is a myth. I know that sounds like blasphemy, but when I've tried this before I discovered that even though C/C++ is pretty gnarly, it has at least 3 major advantages that might not matter for many other things, but is very important for games: 1. It's about as fast as you will get. 2. It is superbly flexible. 3. It is not a memory hog. To summarize my experiences, these wonderful high level languages are full of limitations and you spent more time pulling your hair out to work around them. Even the speed limitation is more of an issue that you think, if you make heavy use of testing. If you don't make heavy use of testing, you don't know what you are doing anyway. For instance, let's say you are experimenting with an algorithm. At some point you must test that algorithm to see if it's better than what you were doing, or to compare it with something else. You must play a large number of games to measure superiority, unless it is overwhelming. Most changes won't be overwhelming and even if it is you still need a lot of games to know how overwhelming it is. With a slower language this is correspondingly a slower process, negating much of the supposed high level language advantage. I spend more time waiting on tests than programming, even in C. Someone says, but if you have a large bank of workstations ...Well if you do, it doesn't change the fact that you are wasting them. An author for a strong playing engine for any game will be able to utilize as much power as you give him for testing. If I had 100 workstations I still would not use Ruby (a joy to program in and one of my favorites) because what a stupid waste of resources it would be to make those 100 workstations perform like only 2 or 3 workstations. When developing the simple reference bot, and experimenting with ideas to make it play better with fewer simulations, guess what? I am performance bound - I cannot test ideas fast enough and this would be worse with a high level language. A word about Java, which will probably produce some anger because I know some of us here love Java. I have never seen a top level, non- trivial game playing program in Java. I don't think you could build a strong chess program in Java. Probably more due to memory issues than performance - but I think for a top chess program performance would be an issue too. Yes, it's possible to write some programs in Java that are almost as fast as C, but probably not a chess program.You really need system level programming type of flexibility that C provides, not high level abstractions that the processor doesn't care about, and the compiler cannot optimize away. An ad-hoc poll: What is the strongest Java playing program on CGOS? I can't see building a very strong MCTS GO program in Java, because even in C, the tree does not fit in memory. My little reference bot can be done in Java however. The performance loss is modest and memory isn't an issue. But the code is clearly larger. Perhaps because I'm not a Java expert, it seems to take more code to do the same thing in Java. All kinds of scaffolding required to use the standard data structures.Much more typing. System.out.printf() is just one example. Seems like a little thing and I'm nitpicking - I see some value in this kind of anal-ism for big projects especially, but it's pretty annoying. I cannot see an ease of use difference between Java and C but I can imagine with large projects Java has some advantages.With it's strong typing Java seems almost as low level to me as C. To summarize, I have found over the years that just plain CPU/MEMORY performance is the primary ba
Re: [computer-go] Re: hex robot
don, i agree, although i will point out one of C's biggest flaws, which happens (conveniently for the sake of this argument) to be its least important one for game programming: string handling sucks if i never have to handle a string, i'll choose C without question. when i need to handle strings, i choose C with major reservations. s. On Thu, Nov 27, 2008 at 11:55 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > On Thu, 2008-11-27 at 13:03 -0200, Mark Boon wrote: >> You say you're going to try to make a prototype first and then when it >> shows promise, move to a more flexible language like Java. What >> language are you intending to use? It seems the wrong way around to >> me. Develop the prototype in a flexible language and when it seems to >> work, move it to a specific langauge that can leverage some specific >> CPU features. Seems to make much more sense to me. > > This is clearly the conventional wisdom, but I think it's a mistake for > an "ultimately" high performance game program, even for an initial > prototype. The supposed benefit is "freedom to experiment" and nail > down your algorithm, but I think this is a myth. > > I know that sounds like blasphemy, but when I've tried this before I > discovered that even though C/C++ is pretty gnarly, it has at least 3 > major advantages that might not matter for many other things, but is > very important for games: > > 1. It's about as fast as you will get. > > 2. It is superbly flexible. > > 3. It is not a memory hog. > > > To summarize my experiences, these wonderful high level languages are > full of limitations and you spent more time pulling your hair out to > work around them. Even the speed limitation is more of an issue that > you think, if you make heavy use of testing. If you don't make heavy > use of testing, you don't know what you are doing anyway. > > For instance, let's say you are experimenting with an algorithm. At > some point you must test that algorithm to see if it's better than what > you were doing, or to compare it with something else. You must play a > large number of games to measure superiority, unless it is overwhelming. > Most changes won't be overwhelming and even if it is you still need a > lot of games to know how overwhelming it is. With a slower language > this is correspondingly a slower process, negating much of the supposed > high level language advantage. I spend more time waiting on tests than > programming, even in C. > > Someone says, but if you have a large bank of workstations ...Well > if you do, it doesn't change the fact that you are wasting them. An > author for a strong playing engine for any game will be able to utilize > as much power as you give him for testing. If I had 100 workstations I > still would not use Ruby (a joy to program in and one of my favorites) > because what a stupid waste of resources it would be to make those 100 > workstations perform like only 2 or 3 workstations. > > > When developing the simple reference bot, and experimenting with ideas > to make it play better with fewer simulations, guess what? I am > performance bound - I cannot test ideas fast enough and this would be > worse with a high level language. > > A word about Java, which will probably produce some anger because I know > some of us here love Java. I have never seen a top level, non-trivial > game playing program in Java. I don't think you could build a strong > chess program in Java. Probably more due to memory issues than > performance - but I think for a top chess program performance would be > an issue too. Yes, it's possible to write some programs in Java that > are almost as fast as C, but probably not a chess program.You > really need system level programming type of flexibility that C > provides, not high level abstractions that the processor doesn't care > about, and the compiler cannot optimize away. > > An ad-hoc poll: What is the strongest Java playing program on CGOS? > > I can't see building a very strong MCTS GO program in Java, because even > in C, the tree does not fit in memory. > > My little reference bot can be done in Java however. The performance > loss is modest and memory isn't an issue. But the code is clearly > larger. Perhaps because I'm not a Java expert, it seems to take more > code to do the same thing in Java. All kinds of scaffolding required > to use the standard data structures.Much more typing. > System.out.printf() is just one example. Seems like a little thing > and I'm nitpicking - I see some value in this kind of anal-ism for big > projects especially, but it's pretty annoying. I cannot see an ease of > use difference between Java and C but I can imagine with large projects > Java has some advantages.With it's strong typing Java seems almost > as low level to me as C. > > To summarize, I have found over the years that just plain CPU/MEMORY > performance is the primary barrier not just to program strength, b
RE: [computer-go] Re: hex robot
I have to agree with Don. This year I went from knowing nothing about Monte Carlo and UCT to world champion. I tried more than 400 variations on the basic UCT algorithm or playout strategy during 6 months of intensive development. The engine is written in C and tuned from the start for performance. I couldn't have done this many experiments (often several per day), without a very fast engine, because I used 1000 game contests to see if there was improvement, to get statistically significant results. Part of the reason I won is because the basic UCT/MC is so fast that I can incorporate the slow Many Faces knowledge and still get over 10K playouts per second per CPU on 9x9. David > -Original Message- > From: [EMAIL PROTECTED] [mailto:computer-go- > [EMAIL PROTECTED] On Behalf Of Don Dailey > Sent: Thursday, November 27, 2008 8:56 AM > To: computer-go > Subject: Re: [computer-go] Re: hex robot > > On Thu, 2008-11-27 at 13:03 -0200, Mark Boon wrote: > > You say you're going to try to make a prototype first and then when it > > shows promise, move to a more flexible language like Java. What > > language are you intending to use? It seems the wrong way around to > > me. Develop the prototype in a flexible language and when it seems to > > work, move it to a specific langauge that can leverage some specific > > CPU features. Seems to make much more sense to me. > > This is clearly the conventional wisdom, but I think it's a mistake for an > "ultimately" high performance game program, even for an initial > prototype. The supposed benefit is "freedom to experiment" and nail > down your algorithm, but I think this is a myth. > > I know that sounds like blasphemy, but when I've tried this before I > discovered that even though C/C++ is pretty gnarly, it has at least 3 major > advantages that might not matter for many other things, but is very important > for games: > >1. It's about as fast as you will get. > >2. It is superbly flexible. > >3. It is not a memory hog. > > > To summarize my experiences, these wonderful high level languages are full of > limitations and you spent more time pulling your hair out to > work around them. Even the speed limitation is more of an issue that > you think, if you make heavy use of testing. If you don't make heavy use of > testing, you don't know what you are doing anyway. > > For instance, let's say you are experimenting with an algorithm. At some > point you must test that algorithm to see if it's better than what you were > doing, or to compare it with something else. You must play a large number of > games to measure superiority, unless it is overwhelming. > Most changes won't be overwhelming and even if it is you still need a lot of > games to know how overwhelming it is. With a slower language this is > correspondingly a slower process, negating much of the supposed > high level language advantage. I spend more time waiting on tests than > programming, even in C. > > Someone says, but if you have a large bank of workstations ...Well > if you do, it doesn't change the fact that you are wasting them. An > author for a strong playing engine for any game will be able to utilize > as much power as you give him for testing. If I had 100 workstations I > still would not use Ruby (a joy to program in and one of my favorites) because > what a stupid waste of resources it would be to make those 100 workstations > perform like only 2 or 3 workstations. > > > When developing the simple reference bot, and experimenting with ideas > to make it play better with fewer simulations, guess what? I am > performance bound - I cannot test ideas fast enough and this would be worse > with a high level language. > > A word about Java, which will probably produce some anger because I know > some of us here love Java. I have never seen a top level, non-trivial > game playing program in Java. I don't think you could build a strong > chess program in Java. Probably more due to memory issues than performance - > but I think for a top chess program performance would be > an issue too. Yes, it's possible to write some programs in Java that > are almost as fast as C, but probably not a chess program.You > really need system level programming type of flexibility that C provides, not > high level abstractions that the processor doesn't care about, and the > compiler cannot optimize away. > > An ad-hoc poll: What is the strongest Java playing program on CGOS? > > I can't see building a very strong MCTS GO program in Java, because even > in C, the tree does not fit in memory. > > My little reference bot can be done in Java however. The performance > loss is modest and memory isn't an issue. But the code is clearly > larger. Perhaps because I'm not a Java expert, it seems to take more > code to do the same thing in Java. All kinds of scaffolding required > to use the standard data structures.Much more typing. > S
Re: [computer-go] Re: hex robot
On Thu, 2008-11-27 at 13:03 -0200, Mark Boon wrote: > You say you're going to try to make a prototype first and then when it > shows promise, move to a more flexible language like Java. What > language are you intending to use? It seems the wrong way around to > me. Develop the prototype in a flexible language and when it seems to > work, move it to a specific langauge that can leverage some specific > CPU features. Seems to make much more sense to me. This is clearly the conventional wisdom, but I think it's a mistake for an "ultimately" high performance game program, even for an initial prototype. The supposed benefit is "freedom to experiment" and nail down your algorithm, but I think this is a myth. I know that sounds like blasphemy, but when I've tried this before I discovered that even though C/C++ is pretty gnarly, it has at least 3 major advantages that might not matter for many other things, but is very important for games: 1. It's about as fast as you will get. 2. It is superbly flexible. 3. It is not a memory hog. To summarize my experiences, these wonderful high level languages are full of limitations and you spent more time pulling your hair out to work around them. Even the speed limitation is more of an issue that you think, if you make heavy use of testing. If you don't make heavy use of testing, you don't know what you are doing anyway. For instance, let's say you are experimenting with an algorithm. At some point you must test that algorithm to see if it's better than what you were doing, or to compare it with something else. You must play a large number of games to measure superiority, unless it is overwhelming. Most changes won't be overwhelming and even if it is you still need a lot of games to know how overwhelming it is. With a slower language this is correspondingly a slower process, negating much of the supposed high level language advantage. I spend more time waiting on tests than programming, even in C. Someone says, but if you have a large bank of workstations ...Well if you do, it doesn't change the fact that you are wasting them. An author for a strong playing engine for any game will be able to utilize as much power as you give him for testing. If I had 100 workstations I still would not use Ruby (a joy to program in and one of my favorites) because what a stupid waste of resources it would be to make those 100 workstations perform like only 2 or 3 workstations. When developing the simple reference bot, and experimenting with ideas to make it play better with fewer simulations, guess what? I am performance bound - I cannot test ideas fast enough and this would be worse with a high level language. A word about Java, which will probably produce some anger because I know some of us here love Java. I have never seen a top level, non-trivial game playing program in Java. I don't think you could build a strong chess program in Java. Probably more due to memory issues than performance - but I think for a top chess program performance would be an issue too. Yes, it's possible to write some programs in Java that are almost as fast as C, but probably not a chess program.You really need system level programming type of flexibility that C provides, not high level abstractions that the processor doesn't care about, and the compiler cannot optimize away. An ad-hoc poll: What is the strongest Java playing program on CGOS? I can't see building a very strong MCTS GO program in Java, because even in C, the tree does not fit in memory. My little reference bot can be done in Java however. The performance loss is modest and memory isn't an issue. But the code is clearly larger. Perhaps because I'm not a Java expert, it seems to take more code to do the same thing in Java. All kinds of scaffolding required to use the standard data structures.Much more typing. System.out.printf() is just one example. Seems like a little thing and I'm nitpicking - I see some value in this kind of anal-ism for big projects especially, but it's pretty annoying. I cannot see an ease of use difference between Java and C but I can imagine with large projects Java has some advantages.With it's strong typing Java seems almost as low level to me as C. To summarize, I have found over the years that just plain CPU/MEMORY performance is the primary barrier not just to program strength, but development time. You must measure development time 2 ways. One is how many man hours are spent, and the other how much "calendar" time is spent. With a high level language you can (in theory, but maybe not in practice) minimize man hour time, by giving up calendar time and dramatically increasing testing time (which need not involve the programmer.)But you also would have to be willing to wait much longer between tests and be willing to work piece-meal on a project while mostly waiting for tests. You will also inevitably take
RE: [computer-go] Re: hex robot
Thanks all for your support and suggestion. I'll let you know if i happen to get any success. > Date: Thu, 27 Nov 2008 16:08:24 +0100 > From: [EMAIL PROTECTED] > To: computer-go@computer-go.org > Subject: Re: [computer-go] Re: hex robot > > Dave Dyer wrote: > > At 01:52 AM 11/27/2008, Denis fidaali wrote: > > > > ... > > > >> But what really lacks (or i wasn't able to find anyway) is a strong > >> community like there is for go. > >> > >> A CGOS equivalent. > >> A GTP equivalent. > >> A Gogui equivalent. > >> A Kgs equivalent. > >> > > > > > > I don't think there's a match between your goals and what boardspace > > wants, but you ought to discuss cloning and adapting CGOS/GTP for > > Hex with Don. > > > > > > > > ___ > > computer-go mailing list > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > This may be what you want: > http://www.cs.ualberta.ca/~mburo/ggsa/ > > You may also be interested in a few messages in the game-programming forum: > http://www.grappa.univ-lille3.fr/icga/phpBB3/viewforum.php?f=8 > > Rémi > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _ Inédit ! Des Emoticônes Déjantées! Installez les dans votre Messenger ! http://www.ilovemessenger.fr/Emoticones/EmoticonesDejantees.aspx___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: hex robot
Dave Dyer wrote: At 01:52 AM 11/27/2008, Denis fidaali wrote: ... But what really lacks (or i wasn't able to find anyway) is a strong community like there is for go. A CGOS equivalent. A GTP equivalent. A Gogui equivalent. A Kgs equivalent. I don't think there's a match between your goals and what boardspace wants, but you ought to discuss cloning and adapting CGOS/GTP for Hex with Don. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ This may be what you want: http://www.cs.ualberta.ca/~mburo/ggsa/ You may also be interested in a few messages in the game-programming forum: http://www.grappa.univ-lille3.fr/icga/phpBB3/viewforum.php?f=8 Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: hex robot
Denis, A CGOS equivalent for Hex would probably be good to have. But since the CGOS server software is open-source you can easily adapt it. GTP you can simply use as-is, I don't see why that wouldn't work. GoGui is also open-source and can possibly also be easily adapted to Hex as well. But to be honest, I don't really need a Gui that much. But twogtp is really useful. A KGS equivalent will only come into existence if there are actually enough people playing the game. You say you're going to try to make a prototype first and then when it shows promise, move to a more flexible language like Java. What language are you intending to use? It seems the wrong way around to me. Develop the prototype in a flexible language and when it seems to work, move it to a specific langauge that can leverage some specific CPU features. Seems to make much more sense to me. If you want to save even more time, you can consider using my CGOS client and plugin framework. Most of it can probably be used as is. Good luck. Mark On 27-nov-08, at 07:52, Denis fidaali wrote: hi. I have put a lot of though in that Hex bot stuff. I realize now how eager i am to try my ideas with an Hex bot. It's been a long time since i first realize how much more elegant it would be to try those ideas for the Hex game anyway. Your site seems a great source of interest for that game. When i tried to find out a community for Hex-computer, i stumbled upon it. But what really lacks (or i wasn't able to find anyway) is a strong community like there is for go. A CGOS equivalent. A GTP equivalent. A Gogui equivalent. A Kgs equivalent. That made it hard for me to settle for putting on the hex bot a lot of work. But as i said, it seems so much more reasonable to me, to first try my ideas with Hex, rather than with go. It seems that Montecarlo is as sound for Hex as it is for go. Given that some of the good-playing programs are montecarlo ones; Although it seems the strongest one is not. So what i will do, is to make up a prototype, that suit my goals : assembly 64 bits montecarlo prototype, with all the tricks i want to try in it. I then will provide a Java gui, for Playing against One instance of the bot when there is an Hardware online willing to support it. I will use a protocol that seems promising, or make up a new one from scratch, if nothing hits me as being standard. It would be logical to use the same protocol that the Computer Games Olympiad uses. But i wasn't able to figure out where to find it. So if all goes well, i should have a prototype available for trying punctually through a java Applet by the end of January 2009. If this prototype shows promises, then i might try to port it to a more flexible langage (like Java). The name of the prototype will be Stohex. > Date: Wed, 26 Nov 2008 13:56:19 -0800 > To: computer-go@computer-go.org > From: [EMAIL PROTECTED] > Subject: [computer-go] Re: hex robot > > At 01:31 PM 11/26/2008, Denis fidaali wrote: > >Speaking of hex ... I really think it would be a nice intermediary game before tackling the complexity of go. Do you know of any good community (and protocol equivalent to GTP) where i could start to look for submitting a bot ? > > There are a couple of pretty decent programs and some nice underlying > theory. Also a perfect play bot for a small board. I would start > at the Hex wiki page to research them. > > A credible Hex bot is on my wish list for Boardspace. The one I wrote > is laughably weak, but it will be a significant effort to write a better > one. If you're willing to work in Java and within the constraints of > a realtime web site, lets talk. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ Qui vous permet d'enregistrer la TV sur votre PC et lire vos emails sur votre mobile ? la réponse en vidéo la réponse en vidéo ___ 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: hex robot
On Thu, 2008-11-27 at 02:05 -0800, Dave Dyer wrote: > At 01:52 AM 11/27/2008, Denis fidaali wrote: > > ... > > But what really lacks (or i wasn't able to find anyway) is a strong > > community like there is for go. > > > > A CGOS equivalent. > > A GTP equivalent. > > A Gogui equivalent. > > A Kgs equivalent. > > > I don't think there's a match between your goals and what boardspace > wants, but you ought to discuss cloning and adapting CGOS/GTP for > Hex with Don. It would be simple to adapt CGOS for hex. CGOS consists of the server stuff, which would change very little, and a single class that defines the game. The class that defines the game would be completely rewritten. I wrote the initial CGOS prototype in one long work day, but I already had the class available that knows the rules of the game and thus defines the rules and such. Since I'm not familiar with Hex, writing this class would probably constitute 90% of the work.I would probably be better off spending some time first getting familiar with the game, how it's notated and so on. There is also the swap rule which seems a little non-standard (there are a couple of variations on how to do this from what I understand.) As much as I love this kind of programming, my time is in short supply as I have to make a living. I suggest that someone familiar with tcl take a look at the server code which is freely available on sourceforge and modify it accordingly if you want such a thing. Another possibility is that if someone were interested enough to pay me for this, I would be delighted.It would be very useful to have an existing bot playing program available and it would make sense to use a very GTP like protocol since that is familiar and works well.So there is already work needed to populate a server with something that works.I could probably hack up a very weak playing reference bot in short time.I wonder if Monte Carlo methods make any sense here? - Don > > > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] RE: hex robot
Hopefully you will be proved wrong by the end of January 2009. I don't feel like i should involve anyone in this before a working prototype is out. Your skepticism is probably statistically correct, so we'll resume this conversation in two month. If my algorithm doesn't work indeed, i'll certainly stop all work on go and hex altogether. Sincerely Denis FIDAALI. > Date: Thu, 27 Nov 2008 01:57:55 -0800 > To: computer-go@computer-go.org > From: [EMAIL PROTECTED] > Subject: [computer-go] RE: hex robot > > > Permit me to play the skeptic here; I think you're going about it absolutely > backwards - unless you already have a strong algorithm which depends on 128 > bit rotations, and only lack an efficient hardware engine to run it on. > > If your idea of fun is to really feel the bits squishing between your toes, > by all means do, but I don't think it's likely you will simultaneously make > advances in Hex theory or practice. > > > At 12:19 AM 11/27/2008, Denis fidaali wrote: > > > > My current plan is to tackle directly the power of x86-64bits architecture. > > Because it's now quite well represented. And there is this "larrabee" > > project that may get out in one or two years (48 x86-64bits processors). So > > my true goal is to try and see what i can do with my quad Q9300 2.5Ghz > > running a 64 bits linux. Obviously one need a bit of work before being able > > to hope to achieve something with assembly. > > etc... > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _ Inédit ! Des Emoticônes Déjantées! Installez les dans votre Messenger ! http://www.ilovemessenger.fr/Emoticones/EmoticonesDejantees.aspx___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: hex robot
At 01:52 AM 11/27/2008, Denis fidaali wrote: ... > But what really lacks (or i wasn't able to find anyway) is a strong community > like there is for go. > > A CGOS equivalent. > A GTP equivalent. > A Gogui equivalent. > A Kgs equivalent. I don't think there's a match between your goals and what boardspace wants, but you ought to discuss cloning and adapting CGOS/GTP for Hex with Don. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] RE: hex robot
Permit me to play the skeptic here; I think you're going about it absolutely backwards - unless you already have a strong algorithm which depends on 128 bit rotations, and only lack an efficient hardware engine to run it on. If your idea of fun is to really feel the bits squishing between your toes, by all means do, but I don't think it's likely you will simultaneously make advances in Hex theory or practice. At 12:19 AM 11/27/2008, Denis fidaali wrote: > My current plan is to tackle directly the power of x86-64bits architecture. > Because it's now quite well represented. And there is this "larrabee" project > that may get out in one or two years (48 x86-64bits processors). So my true > goal is to try and see what i can do with my quad Q9300 2.5Ghz running a 64 > bits linux. Obviously one need a bit of work before being able to hope to > achieve something with assembly. etc... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: hex robot
hi. I have put a lot of though in that Hex bot stuff. I realize now how eager i am to try my ideas with an Hex bot. It's been a long time since i first realize how much more elegant it would be to try those ideas for the Hex game anyway. Your site seems a great source of interest for that game. When i tried to find out a community for Hex-computer, i stumbled upon it. But what really lacks (or i wasn't able to find anyway) is a strong community like there is for go. A CGOS equivalent. A GTP equivalent. A Gogui equivalent. A Kgs equivalent. That made it hard for me to settle for putting on the hex bot a lot of work. But as i said, it seems so much more reasonable to me, to first try my ideas with Hex, rather than with go. It seems that Montecarlo is as sound for Hex as it is for go. Given that some of the good-playing programs are montecarlo ones; Although it seems the strongest one is not. So what i will do, is to make up a prototype, that suit my goals : assembly 64 bits montecarlo prototype, with all the tricks i want to try in it. I then will provide a Java gui, for Playing against One instance of the bot when there is an Hardware online willing to support it. I will use a protocol that seems promising, or make up a new one from scratch, if nothing hits me as being standard. It would be logical to use the same protocol that the Computer Games Olympiad uses. But i wasn't able to figure out where to find it. So if all goes well, i should have a prototype available for trying punctually through a java Applet by the end of January 2009. If this prototype shows promises, then i might try to port it to a more flexible langage (like Java). The name of the prototype will be Stohex. > Date: Wed, 26 Nov 2008 13:56:19 -0800 > To: computer-go@computer-go.org > From: [EMAIL PROTECTED] > Subject: [computer-go] Re: hex robot > > At 01:31 PM 11/26/2008, Denis fidaali wrote: > >Speaking of hex ... I really think it would be a nice intermediary game > >before tackling the complexity of go. Do you know of any good community (and > >protocol equivalent to GTP) where i could start to look for submitting a bot > >? > > There are a couple of pretty decent programs and some nice underlying > theory. Also a perfect play bot for a small board. I would start > at the Hex wiki page to research them. > > A credible Hex bot is on my wish list for Boardspace. The one I wrote > is laughably weak, but it will be a significant effort to write a better > one. If you're willing to work in Java and within the constraints of > a realtime web site, lets talk. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _ Email envoyé avec Windows Live Hotmail. Dites adieux aux spam et virus, passez à Hotmail ! C'est gratuit ! http://www.windowslive.fr/hotmail/default.asp___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: hex robot
My current plan is to tackle directly the power of x86-64bits architecture. Because it's now quite well represented. And there is this "larrabee" project that may get out in one or two years (48 x86-64bits processors). So my true goal is to try and see what i can do with my quad Q9300 2.5Ghz running a 64 bits linux. Obviously one need a bit of work before being able to hope to achieve something with assembly. Although if there really is nothing to do about it, i may try to translate brutally the intended assembly algorithm in java. But it may be quite slow. Especially with the heavy use of 128 bits rotations. (yes the x86 has a 128 bits rotation instruction). I don't know about java, but the C rotation is not specified for at least one (or both) the extreme rotation range (like 0 or 32 in 32bits modes). I don't even know how to do a 64 bits rotation in java. (appart from a time consuming combination of 32 bits ones). So there is chances that my translation will be quite slow. Also if i go for java, i probably won't try too hard to optimize : because it is not my target platform. So it would been hundreds time more motivating for me if i could run the bot you hope for on a quad 64-bits x86 environnement. But if you provide a way to (roughly) test the strength of the bot, i guess i will try it even if it's in java, because i'm so curious about how my ideas would do with hex. Hex is so much easier to look at :) No strange "capture" factors. If you give me a strong assurance (and a nice communication protocol) that you can provide this testing, i guess i could have a bot ready for the end of January 2009 (be it in java or in assembly). If it's really fun, i may even end up trying to optimize it a bit :) Also i would rather work for a fixed size ... (but once again, i'm willing to do it anyway, although i won't try to optimize too hard with the variable sizing) So the worst scenario would be that i try my ideas and they don't work out well by the end of January, the bot is so slow and cpu-eater, and it doesn't even beat out yours :) But i'm really willing to try. I don't understand your point about the real-time web site constraint. Do you mean that you would expect to have hundreds of people playing against the bot. All instances running on the same hardware and sharing ressources with the all the web components ? If so, i think it really gets far away from what i can be involved in. My goal is to design a bot, and then implement it in assembly, running on a quadQ9300 with 8GB of memory. Ideally i would try to use most of those ressources. I may try to downgrade from that, but it probably won't do it to get half a cycle every three seconds, within a 64kb memory frame :). It is not one hundred percent excluded that i provide a full time server of my own (although it would probably not be running a 64 bits system, nor dedicate all ressources to the running instance). But that would be running only one instance of the bot at a time. And we would have to agree on a communication protocol. (alike GTP for go). This HTP (Hex text protocol) is probably the way to go, if people are to get serious with Hex anyway. I'm sure that the protocol already exists. One would have to agree and pick up a good and easy one. > Date: Wed, 26 Nov 2008 13:56:19 -0800 > To: computer-go@computer-go.org > From: [EMAIL PROTECTED] > Subject: [computer-go] Re: hex robot > > At 01:31 PM 11/26/2008, Denis fidaali wrote: > >Speaking of hex ... I really think it would be a nice intermediary game > >before tackling the complexity of go. Do you know of any good community (and > >protocol equivalent to GTP) where i could start to look for submitting a bot > >? > > There are a couple of pretty decent programs and some nice underlying > theory. Also a perfect play bot for a small board. I would start > at the Hex wiki page to research them. > > A credible Hex bot is on my wish list for Boardspace. The one I wrote > is laughably weak, but it will be a significant effort to write a better > one. If you're willing to work in Java and within the constraints of > a realtime web site, lets talk. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _ Inédit ! Des Emoticônes Déjantées! Installez les dans votre Messenger ! http://www.ilovemessenger.fr/Emoticones/EmoticonesDejantees.aspx___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
