Re: [computer-go] Rank on servers at 9x9
> Do any of the strongest MCTS programs have a rank > at 9x9 on any major server? i'm not sure that a "9x9 rank" is super well-defined, at least in the sense that ranks are generally established by your play on a 19x19 board, not a 9x9 board. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Open source real time Go server
sorry, i should have been more clear. an SE can't be any smarter than a computer player, because it could otherwise easily simulate a computer player, as described. would it be slower? yes, by a constant factor that is bounded by the boardsize. this simulation could be completely paralellized, however, so if anyone thinks that i'm wrong, they should build such an SE, and we can easily put together enough boxes to beat all existing computer players. i point this out because a pet peeve of mine is people who complain about the SE and don't realize that it's equivalently difficult, if not *more* difficult, than building a computer player. s. On Tue, Jan 19, 2010 at 12:20 AM, Michael Williams wrote: > Your point is obvious but that's a horrible proof since there are usually > more than one legal moves from which to chose (that means it takes more > time). > > steve uurtamo wrote: >>> >>> As for other things we'd like to see improved, we could build a list. My >>> pet >>> peeve is the KGS "score estimator", which is often wildly wrong. >> >> an SE can't be any smarter than a computer player that runs in the >> amount of time that you're willing to wait for the SE to calculate*. >> so don't expect much. ever. recall that the SE runs locally in your >> client. >> >> s. >> >> * proof: if it were, then it would make a better computer player by >> just evaluating its score estimate at all legal board points and >> choosing the maximum at each move. >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Open source real time Go server
> As for other things we'd like to see improved, we could build a list. My pet > peeve is the KGS "score estimator", which is often wildly wrong. an SE can't be any smarter than a computer player that runs in the amount of time that you're willing to wait for the SE to calculate*. so don't expect much. ever. recall that the SE runs locally in your client. s. * proof: if it were, then it would make a better computer player by just evaluating its score estimate at all legal board points and choosing the maximum at each move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
sorry to self-reply, but: > alternatively, it does sphere packing over the direct product of open > or closed (but bounded) intervals and discrete sets, so you can get a > set of points that is slightly better than a random set of experiments > (i.e. guaranteed to cover the space well). arguably it is not slightly better, but much, much better. especially when the dimensionality (number of parameters) is high. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
> That doesn't seem to directly support deriving information from random > trials. For computer go tuning, would you play multiple games with each > parameter set in order to get a meaningful figure? That seems likely to > be less efficient than treating it as a bandit problem. you'd decide how many experiments you wanted to run, take a stab at what you thought the interactions between parameters were (i.e. independent between #2 and #3, and no worse than quadratic between #1 and #4), generate an optimal design, run enough experiments at each setting of the parameters (as specified by the design) to keep error low, then fit the specified model with the resulting data. the way to consider the model is that you want to model winrate versus (whomever -- self-play, on kgs, whatever you want), and you have some idea about interactions between parameters (i think that this cutoff is only appropriate between these two ranges, and have reason to believe has only a very weak interaction with this other parameter, whereas these 12 parameters might all be related in some horrible quadratic way), but you don't want to blindly run thousands of random tests. you'd rather run thousands of tests that were specifically designed to maximize the amount of information that you can get about the model that you're trying to fit. alternatively, it does sphere packing over the direct product of open or closed (but bounded) intervals and discrete sets, so you can get a set of points that is slightly better than a random set of experiments (i.e. guaranteed to cover the space well). s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
the way to do all of this exactly is with experimental design. to design experiments correctly that handle inter-term interactions of moderate degree, this tool is quite useful: http://www2.research.att.com/~njas/gosset/index.html s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
:) my point was that simply totaling total "won by" points after each game is over, or totalling total "won by" points divided by ten after each game should produce the same rank order of results, therefore not punishing anyone. my comment that one handicap difference in strength, in an even game, roughly equates to 10 game stones at the end of the game, was perhaps too distracting as a rationale (perhaps because it is only empirically true at the kyu level?). the idea that i like about keeping track of number of points won or lost by is that not only could you find the winner, but you could find how absolutely dominant, on average, they were against their opponents. if the variance was low, we might expect to see, say, a less than 20 stone average advantage in points. normalizing by dividing by 10 just scales this down to something "chunkier". s. On Mon, Nov 23, 2009 at 9:53 AM, Robert Jasiek wrote: > steve uurtamo wrote: >> dividing by 10 for everyone wouldn't change the overall result > > First you describe something like handicap steps, then you describe > something different (a mere division by 10). Therefore > >> so it wouldn't punish anyone, right? > > ...this question cannot be answered. > > -- > robert jasiek > ___ > 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: Hahn system tournament and MC bots
i'm just thinking that approximating the 10 stones on the board == 1 stone of handicap phenomenon might be a nice way to keep track of score in a tournament. i realize that it's not terribly accurate, but it would give a number that's easier to parse. dividing by 10 for everyone wouldn't change the overall result, so it wouldn't punish anyone, right? s. On Mon, Nov 23, 2009 at 9:03 AM, Robert Jasiek wrote: > steve uurtamo wrote: >> >> maybe divided by ten? > > To punish programs or me for the ability of killing 70 stones dragons? > > -- > robert jasiek > ___ > 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: Hahn system tournament and MC bots
maybe divided by ten? s. On Mon, Nov 23, 2009 at 5:50 AM, Robert Jasiek wrote: > Ingo Althöfer wrote: >> >> I would have found a "completely continuous result system" >> more natural, for instance >> giving +40.5 points for each win with 40.5 or more >> giving -40.5 points for each loss with 40.5 or more > > The most natural score-dependent Go variant(!) would be the game result x > for the score x, with resignation being not available and using some scoring > method that has +-361 as its extreme scores. > > -- > robert jasiek > ___ > 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: [SPAM] Re: [computer-go] Joseki Book
you could always take a joseki dictionary and build the trees by hand, if you feel that you're strong enough to work out the most common variations for the most common opening situations. s. 2009/11/9 Olivier Teytaud : > There is a paper about that in > http://hal.inria.fr/inria-00369783/en/ > and Tristan Cazenave published something around that also. > (these two works are about the automatic building of opening book in > self-play) > See also the references in the PDF above. > Best regards, > Olivier > >> >> Only papers I can recall are from seventies (assuming you mean academic >> papers) from Wilcoxx. I may have electrical copies. Not sure though. I >> managed to find some of them from ACM site. >> >> That paper described position based approach where each and every stage >> was stored into datastructure, kinda like huge pattern matching library. Was >> called lenses if I remember correctly. More common way is store joseki moves >> as a tree. >> >> Biggest issue is always hos key in all those variations. >> >> Petri >> >> 2009/11/9 Jessica Mullins >>> >>> Hi, >>> >>> I am wondering what is the best way to build a Joseki Book? I am a >>> student at >>> Lewis & Clark College and am working with Professor Peter Drake to build >>> a >>> Joseki Book for the program Orego.sed aproach i.e each state of joske >>> >>> Right now I am extracting moves from professor players and saving those >>> into a >>> database. Then if during game play a position is contained in the >>> database, >>> play the response move like the professional. I am just wondering what >>> other >>> people have done to build a Joseki Book, or if anyone knows of any papers >>> that >>> might be helpful. >>> >>> Thank you, >>> Jessica Mullins >>> Lewis & Clark College '10 >>> >>> >>> ___ >>> 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/ > > > > -- > = > Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr > Tel (33)169154231 / Fax (33)169156586 > Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), > bat 490 Universite Paris-Sud 91405 Orsay Cedex France > (one of the 56.5 % of french who did not vote for Sarkozy in 2007) > > > > ___ > 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] Neural networks
these things have definitions, folks. everything isn't everything else. s. On Tue, Nov 3, 2009 at 7:43 AM, Willemien wrote: > I disagree with the point that MCTS is a neural network, > > In my opinion (and i maybe completely off target) One of the essences > of neural networks is that the program changes/learns from the games > it has played. . > > MCTS doesn't have that result, the improvement is only "in-game" > The program doesn't learn not to make the same mistake anymore, by > MCTS the mistake is hopefully avoided. > > if MTCS is a neyural network than alpha beta would also qualify. > > but i may be wrong it is just an opening for a discussion in which we > all can learn > > > 2009/11/2 Daniel Burgos : >> Well, at its esence a computer is an universal Turing Machine. If you >> organize the program as a neural network or as a MC algorithm is just >> cosmetics. >> >> You can see the circuits of your computer as neurons simulating a Von >> Neumann architecture that is simulating a neural network or a MC or >> whatever. An may be your whatever is simulating another thing. >> >> 2009/11/2 Álvaro Begué >>> >>> On Sun, Nov 1, 2009 at 7:50 PM, Aldric Giacomoni >>> wrote: >>> > Álvaro Begué wrote: >>> >> 2009/10/31 : >>> >>> Present day MC Go programs are neural networks. The playout is the >>> >>> trainng >>> >>> process. >>> >> >>> >> What? >>> >> ___ >>> >> computer-go mailing list >>> >> computer-go@computer-go.org >>> >> http://www.computer-go.org/mailman/listinfo/computer-go/ >>> > >>> > Go programs using the Monte-Carlo algorithms are neural networks. The >>> > actual >>> > fact of playing games is what trains them to play better. >>> > >>> > ... I'm pretty sure that's what it means, anyway. >>> >>> Except they don't fit any definition of "neural network" that I've >>> been able to find. For starters, they don't have neurons. >>> ___ >>> 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/ >> > ___ > 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] CUDA implementation of the per-intersection GPGPU approach
> Since AMAF values are so helpful, perhaps one can let go of the idea of > sequential play following the rules of go, and basically play moves in > parallel on all empty intersection. Compute new state (do captures) and > repeat a fixed number of times and evaluate. two thoughts: i) how do you determine color to play for each thread? ii) if i) becomes unsynchronized with the rules of go, you're basically exploring random boards instead of boards that are related to the game that you're interested in. the board should rapidly converge to something that retains no information about the initial state of the board (assuming that the initial board has stones on it). s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CUDA and GPU Performance
thanks for taking the time to do these experiments and to report your results. it will (has) saved a nightmarish-sounding investment of time to learn the order of the speedup for this particular problem. how much penalty do you estimate there is to pass a board from, say, a program running on the CPU over to the GPU and have the GPU operate on the partially-filled board as its starting board? it seems that a search that has narrowed down the set of next board moves to something small could use the GPU to help make very fine distinctions between those few board moves by offloading the heavy lifting. s. 2009/9/9 : > Interesting stuff. Thanks for reporting your results. > > - Dave Hillis > > > -Original Message- > From: Christian Nentwich > To: computer-go > Sent: Wed, Sep 9, 2009 11:54 am > Subject: [computer-go] CUDA and GPU Performance > > I did quite a bit of testing earlier this year on running playout algorithms > on GPUs. Unfortunately, I am too busy to write up a tech report on it, but I > finally brought myself to take the time to write this e-mail at least. See > bottom for conclusions. > > For performance testing, I used my CPU board representation, and a CUDA port > of the same (with adjustments), to test the following algorithm: > - Clear the board > - Fill the board according to a uniform random policy > - Avoid filling eyes, according to simple neighbour check > - Avoid simple ko > - Count the score and determine the winner > > In other words: no tree search is involved, and this is the lightest > possible playout. The raw numbers are as follows: > - CPU Search: 47,000 playouts per CPU core per second, on an Intel 6600 > Core-2 Duo > - GPU Search: 170,000 playouts per second, on an NVidia Geforce 285 card > > The algorithm running on the GPU is a straight port, with several > optimisations then made to severely restrict memory access. This means the > algorithm is a "naive" sort of parallel algorithm, parallel on a per-board > level like the CPU implementation, rather than per-intersection or some > other sort of highly parallel algorithm. > > Memory access other than shared processor memory carries a severe penalty on > the GPU. Instead, all threads running on the GPU at any one time have to > make do with a fast shared memory of 16834 bytes. So: > - The board was compressed into a bit board, using 2*21 unsigned ints per > thread > - The count of empty, white and black intersections and the ko position was > also in shared memory per thread > - String/group/block type information was in global memory, as there was no > way to store it in 16384 bytes > > Optimal speed was at 80 threads per block, with 256 blocks. The card had > only 9% processor occupancy, due to the shared memory being almost > exhausted. However, branch divergence was at only 2%, which is not bad at > all - suggesting that the form of parallelism may not be a block. This may > be because the "usual" case of a point either being illegal to play, or a > simple play without a need to merge or remove strings is by far the most > common case. > > Conclusions: > > I see these results as broadly negative with the current generation of > technology. Per-board parallelism on a GPU is not worth it compared to the > CPU speed and the severe drawbacks of working on a GPU (testing is hard, > unfamiliar environment for most programmers, lots of time to spend on > optimisation, etc). > > The problems would be severely compounded by trying to integrate any tree > search, or heavy playouts. Trees are almost impossible to construct on a GPU > because pointers cannot be transferred from the host to the GPU. They could > still be represented using arrays, but the random nature of tree access > would cause huge penalties as it would prevent coalesced memory access. > > Highly parallel algorithms (e.g. one thread per intersection) can still be > investigated, but my (unproven!) intuition is that it is not worth it, as > most intersections will be idle on any given move, wasting processor > occupancy time. > > My feeling is that GPUs may have some potential in this area, but possibly > in a supplementary role such as running additional pattern matching in the > background, or driving machine learning components. > > This e-mail is a bit hurried, so.. questions are welcome!! > > Christian > > ___ > 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
zen wins many more of its "even" games with no handicap than it does with even, say, an even 2 stone handicap as either black or white. i haven't compiled numbers for it (i'm not zen's maintainer), but i watched it happen over the course of about 50 games one day. it was pretty consistently worse with any kind of handicap on the board, the more handicap the worse. fix the handicap problem and it would likely rise a stone in strength. s. On Wed, Aug 19, 2009 at 12:15 PM, Jeff Nowakowski wrote: > On Wed, Aug 19, 2009 at 07:27:00AM -0700, terry mcintyre wrote: >> Consider the game when computer is black, with 7 stones against a very >> strong human opponent. >> >> Computer thinks every move is a winning move; it plays randomly; a >> half-point win is as good as a 70-point win. > > Didn't this game actually happen? Didn't MoGo *beat* a pro with 7 > stones? Did it play randomly? > > Don't the monte carlo bots frequently win as White when giving > handicap stones on KGS? > > I think we need some real statistical evidence that this problem is > even worth talking about, aside from stylistic issues. I'm not the > first to say this, but I think it bears repeating. > > -Jeff > ___ > 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: Dynamic komi in commercial programs
ken regan has done some modeling the complexity of chess positions, and perhaps more interestingly, the modeling of the ability of a human player based upon how he or she makes move choices -- this only works because a computer player can vastly outplay a human player (and can act a bit like an oracle for many positions). so in computer go it should only be expected to be applicable when the human player is very, very weak. so there's some hope for giving large handicap, but it shouldn't be expected to be useful for taking large handicap. s. 2009/7/13 terry mcintyre : > Is it possible to design metrics for "complexity" of positions? An opponent > model could make use of that information; there are positions which some > players will totally fail to grok. > > Double-digit kyu players are weak on life-and-death, ko, and seki. Some > otherwise strong programs will fail to read seki properly. As players move > up in rank, they read life-and-death at an earlier point. Human players, > with practice, discover the weaknesses of their particular opponents. > > Terry McIntyre > > “We hang the petty thieves and appoint the great ones to public office.” -- > Aesop > > > From: Magnus Persson > > I am open to opponent modeling such as make the playouts of black in > handicap games weaker. But in this case I think real gain if any would come > from making the statistics more sensitive to the qualitative difference in > available moves, rather than actually modeling the opponent, by bringing the > win rates closer to 50%. Although I think it would be really hard to degrade > the black moves in the playouts in a realistic way. > > > > ___ > 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: Dynamic komi in commercial programs
i think that the rationale behind variable komi is intuitive: good players can handicap one another more effectively with komi than with handicap stones, because it's more fine-grained. this is likely what is leading to the idea that computers playing handicap games could use this to their advantage. there's something like an exact tradeoff between stones and komi, although i don't know the function and it'd be interesting to find. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Experimentation
something i've played with a little bit: only look at algorithms with the following property: * they every so often update an in-memory score for each board position. you can then run a timing loop around this and just make the highest-scoring valid move the play. you can use a signal handler to dump the list at any time. s. 2009/7/7 terry mcintyre : > Digesting Don's remarks, it seems that a reasonable method would start with > equal numbers of simulations. It could then proceed to try various > optimizations, and compare algorithms which use equal time. > > It makes perfect sense for the ultimate goal to be "better performance using > the same time or less", but it might be easier to progress stepwise - first > tweak the top-level design, then tweak the performance - in order to > separate out the different inputs to the experiment. > > Terry McIntyre > > “We hang the petty thieves and appoint the great ones to public office.” -- > Aesop > > > > ___ > 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] Complicated seki with Ko
zen builds sekis, and occasionally wins games that way. s. On Tue, Jun 30, 2009 at 1:25 PM, Jason House wrote: > Is it possible to explicitly use a monospace font? I can't read your board > positions. > > I haven't heard of any handling of seki in playouts except for Remi's > CrazyStone. I don't think he's ever given specifics on how he did it. Maybe > he'll respond to your e-mail? > > Sent from my iPhone > > On Jun 26, 2009, at 1:37 PM, "Brian Sheppard" wrote: > >> Here is a position that exposed some bugs in Pebbles. Maybe it will help >> you. >> >> 1 2 3 4 5 6 7 8 9 >> A - O - O X - - X - >> B - X O - O X - O O >> C - O O - O - X O - >> D X X X O O O O O O >> E - O X X X O X O O >> F - - O X O X X X X >> G - - X X O O X X - >> H - O X O - O O X X >> J - O X O O - X - X >> X to play. >> >> X is already doomed in this position. The bottom O group is in a seki >> with the X group at right. O cannot play J6 self-atari. X cannot fill >> in J8 and then play J6, and after X J6, O captures and X cannot recapture. >> So it will be dual life. Because the top of the board is O's, O have >> more than half the board, even without komi. >> >> The playouts have to handle certain issues well in order to find that. >> The first point is to filter out plays that make self-atari on large >> groups. This will cause the rest of the board to fill up until only >> the seki remains. >> >> The the playout will be in a position like the following: >> >> 1 2 3 4 5 6 7 8 9 >> A - O - O O - O O - >> B O - O - O O - O O >> C - O O - O - O O - >> D X X X O O O O O O >> E - X X X X O X O O >> F X X - X O X X X X >> G X - X X O O X X - >> H X X X O - O O X X >> J X - X O O - X - X >> X to play. >> >> Pebbles does not detect superko in playouts, so this position will loop >> forever with J6/J8/J7/pass. In Pebbles, infinite games were scored as >> draws. I changed that to give the win to O on the basis of its >> preponderance >> of material. (No doubt that will bite me at some point.) >> >> Even if we detect the superko repetition, it seems to me that we are only >> getting the right answer by accident. For instance, if X plays J6 then >> after J8/J7 there is no move for X, so X has self-ataried himself. >> >> Another possibility if to see that X's J6 is atari and also self-atari, so >> X can look for the approach move. In this case X would play J8 instead of >> J6 >> which avoids the ko. Then the seki is obvious. >> >> How do other programs handle this case? >> >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ko in light playouts
what happens with the following? rank the moves as normal, ignoring ko. choose the highest ranked legal move at the end. (i.e. only check for ko-legality when choosing the final move) s. On Mon, Jun 15, 2009 at 4:45 PM, Heikki Levanto wrote: > I am slowly getting my little bot to do very light playouts. I came to think > about detecting ko. Is it even necessary in a simple playout? During the > earlier stages of the game, the playouts have no idea of wanting to > recapture the ko, of ko threats, or anything else. Only in the endgame can > we run into problems, when everything else is filled up, and the only points > left are in a ko fight. At that point the playout moves are fast, repeating > the same position all over again, until a limit to the number of moves puts a > stop to it all. > > I suppose that in the end the right thing is to do the right thing, and > detect at least a simple ko properly and according to the rules. But I > thought I'd ask if people are trying alternative tricks? > > - Heikki > > > P.S. My progress is awfully slow, as I work full time with other things, and > have several hobbies cometing for my spare time. Still, I am making slow > progress, and at some point I get my "halfgo" playing on cgos. Very badly, to > begin with... It is a simple program, written in C, using bitmaps for the > board images. I just wanted to see how far I could take that approach. Now it > seems to be a good foundation for my next experiments, which I will have to > do before discussing them here. > > > > > > -- > Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk > > ___ > 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] MCTS, 19x19, hitting a wall? moore's law limits
I think it'd be great to have an extremely simple integer operation cpu (small bitwidth fine!) if it meant I could have a million of them. Something about the pinouts makes me think this impractical ;) s. On Fri, Jun 12, 2009 at 4:58 PM, Mark Boon wrote: > 2009/6/10 David Fotland : >> I think we will get another 64x to 256 x density then it will stop, for >> single chips. We should eventually get desktop machines with thousands of >> cores, but probably never with millions of cores. There really are limits >> built into physics L >> > > How about the cores becoming much smaller and simpler? > > Intel's CPUs are approaching a billion transistors on a chip. But you > can probably make a very decent and fast CPU with just a million > transistors. Maybe double that number to give each a bit of cache > memory. If you can see computers with thousands of cores, does that > already assume they'll be simpler? Or could we have a few (hundred) > heavy-duty CPUs like today's for multi-purpose use and a card with a > million simpler CPUs on them next to it for tasks suitable for > parallel processing? A hybrid system if you will. > > Just thinking out loud, I'm obviously a layman when it comes to > semiconductors. > > Mark > ___ > 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] MCTS, 19x19, hitting a wall?
> To conclude, it appears that 500 MHz (embedded: poor > cache performance) with little memory for transposition > tables is the lowest you can go, while still staying at grandmaster > level. that's quite impressive. some kind of pipelining is involved? are they 32bit? s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
> But here is someting interesting: In the case of computer > chess it has been estimated that the progress in software > has been roughly the same as the progress in hardware. > Modern chess programs are truly amazing, and not just > a result of faster hardware. There is no reason to think > that this won't be true of computer go. This makes me wonder... so how slow (and RAM starved) of a computer could you use and still get grandmaster level chess play? In other words, how far back could we go in time if we had today's software and expect a computer to play chess as well as humans? s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] bots and handicaps (Re: New CGOS)
> The handicap system is imperfect anyway, it's almost > a coincidence that it works as well as it does. okay, this sounds like chess bias. the handicap system *defines* the difference in skill levels in go. it's a coincidence that something like ELO can match fairly well to stones. not the other way around. the fact that chess doesn't have a fine-grained way to handicap a game, in fact, the fact that most games don't, doesn't mean that it's hard to deal with. my guess is that any go playing program that doesn't depend upon an opening book for a lot of its strength is going to adapt just fine. experiments between players of different CGOS-measured strengths could find this out for sure -- time for another set of experiments? i'll donate some cpu time. if it helps to encourage the authors, just keep in mind that winning with handicap is extremely convincing evidence to "regular go players" that one player is much stronger than another. plus, it takes exponentially fewer games to determine that difference. with a logarithmic (in range of handicap, say, +/-6 stones) number of games you could get a very accurate view of the strength difference between two players. say, take best of 2 out of 3 at each test level and do binary search. some go clubs just keep track of the relative difference in stone strength between pairs of players, requiring, say, a 3-win streak by one player to adjust the handicap by a single stone. alternatively, you can (somewhat cheesily) map ELO to handicap and vice-versa for a limited range of ELO and handicap. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to Steenvreter!
contests are never hindered by weak opponents, in my opinion. the more the merrier the better of course! s. 2009/6/1 : > One factor is that there seems to be a narrow range between too few entrants > and too many. For any given contest, the potential pool includes an elite > few who have a chance at first place and maybe a couple who have a new or > newly improved bot. There is a larger group, back in the pack, whose last > breakthrough was a while ago. For many of us in that last group, it would be > easy enough to enter, but hard to know if that would help or hinder. > > - Dave Hillis > > > -Original Message- > From: David Doshay > To: computer-go > Sent: Mon, 1 Jun 2009 5:32 pm > Subject: Re: [computer-go] Congratulations to Steenvreter! > > SlugGo has not been participating because we had made no progress. > I hope to have something by the end of summer. > > Cheers, > David > > > On 1, Jun 2009, at 1:39 PM, Nick Wedd wrote: > >> would like to know what I might do to attract more entrants. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > Wanna slim down for summer? Go to America Takes it Off to learn how. > ___ > 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] Implications of a CPU vs Memory trend on MCTS
cool, that's what i was wondering -- that you'd have to treat it as something inbetween ram and a HD. thanks, s. On Tue, May 12, 2009 at 12:48 PM, Michael Williams wrote: > It depends on how you use it and how much you pay for it. If you get a > high-end Intel SSD, you can treat it however you like. But I can't afford > that. I got a cheap SSD and so I had shape my algorithm around which kind > of disk operations it likes and which ones it doesn't. > > > steve uurtamo wrote: >> >> is the ssd fast enough to be practical? >> >> s. >> >> On Tue, May 12, 2009 at 12:41 PM, Michael Williams >> wrote: >>> >>> Don Dailey wrote: >>>> >>>> On Tue, May 12, 2009 at 12:16 PM, Michael Williams >>>> mailto:michaelwilliam...@gmail.com>> >>>> wrote: >>>> >>>> I have a trick ;) >>>> >>>> I am currently creating MCTS trees of over a billion nodes on my 4GB >>>> machine. >>>> >>>> >>>> Ok, I'll bite. What is your solution? >>> >>> I use an SSD. There are many details, of course. But it's still in the >>> works and I'm still making lots of changes and adjustments. I seem to be >>> able to "solve" (there are lots of definitions) 6x6 Go in that when I use >>> a >>> komi of 3.5, it is unable to find a winning line for white and when I use >>> 4.5, it is unable to find a winning line for black. >>> >>> ___ >>> 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/ >> > > ___ > 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] Implications of a CPU vs Memory trend on MCTS
is the ssd fast enough to be practical? s. On Tue, May 12, 2009 at 12:41 PM, Michael Williams wrote: > Don Dailey wrote: >> >> On Tue, May 12, 2009 at 12:16 PM, Michael Williams >> mailto:michaelwilliam...@gmail.com>> wrote: >> >> I have a trick ;) >> >> I am currently creating MCTS trees of over a billion nodes on my 4GB >> machine. >> >> >> Ok, I'll bite. What is your solution? > > I use an SSD. There are many details, of course. But it's still in the > works and I'm still making lots of changes and adjustments. I seem to be > able to "solve" (there are lots of definitions) 6x6 Go in that when I use a > komi of 3.5, it is unable to find a winning line for white and when I use > 4.5, it is unable to find a winning line for black. > > ___ > 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] Implications of a CPU vs Memory trend on MCTS
increasing memory is more expensive than increasing cpu speed at this point. there was an addressing issue with 32bit machines, but that shouldn't be too much of an issue anymore. most people want to pay less than or equal to the price of their last machine whenever they buy one, though, so companies oblige them -- companies have to change something, though, so they make new cpus. i agree that ram is the more useful thing to have access to, but it's just hideously expensive to have lots and lots of high speed ram available to the cpu. if you need some extra ram, feel free to use your graphics card's ram. most modern graphics cards have way more ram than you might think. there aren't many technologies that work cheaper than ram that are within an order of magnitude or two of the speed of ram. so you're pretty much stuck. one nice thing about your compression idea is that fast cpu means that you can afford to spend more time fiddling with compression and decompression. if the size of any object is really an issue, here's what i'd suggest -- * look at the structure of your objects during actual games and try to figure out where self-similarity lies. * actually copy the memory objects to disk and bzip them and see how much compression you get. if it's not much, it's a big waste of time to even think about it. * think, hard, about how much extra ram you'd need to be happy and content, and how much extra gameplay you'd get out of having that extra ram. if doubling your ram would only effect a 10% advantage, is it worth the effort? * turn the problem around and ask yourself what you'd do if you had, say, a terabyte of ram. such machines exist, but that isn't that important. how would you write your code differently if you had that much ram, and would it instantly mean that your program would be immensely stronger? if not, then ram isn't the main issue. if you can figure out how to use that much ram to guarantee a much stronger player, then maybe someone will loan you one to play with. even if they don't, it's an important exercise, especially if it turns out that: * perhaps your structures are so self-similar that you can get radical levels of compression easily. there are some very cheesy ways to do this. you can use zlib on structures that haven't been accessed in awhile or which you expect not to be accessed for awhile. you'll need to fully decompress them to access anything inside of them, though, so it might make sense to set up your compression hierarchically according to how you wander through your structure. this is very tricky stuff that entirely depends upon what access patterns you're using through your structure, and how it's built. enjoy serializing and unserializing your objects. basically, if you want to have high-speed random access to nearly random data, you have to use ram. change any two of these variables and you can probably hog some of the cpu to give you a hand. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
also, i'm not sure that a lot of most amateurs' moves are very good. the spectrum of bad moves is wide, it's just that it takes someone many stones stronger to severely punish small differences between good and nearly-good moves. among players of relatively similar strength, these differences will go unnoticed and unpunished. s. 2009/4/28 Don Dailey : > A simplistic model that helps explain this is golf. On a single hole, even > a casual golfer has a realistic chance of out-golfing Tiger Woods. Tiger > occasionally shoots a 1 over par on some hole and even weak amateurs > occasionally par or even birdie a hole. It's not going to happen a lot, > but it's not ridiculous either. Years ago I taught a player how to golf, > and on his third time out with me, he hit a hole in one on a short par > 3. If Tiger Woods had been playing with us, he would have lost that hole > to this beginner. > > But in a 9 hole match, the odds go down enormously - for all practical > purposes there is no chance. > > I kind of think of GO like that, even though it's a pretty simplistic > model. Each move is like a hole of golf, it can be a good "shot" or a bad > one. With GO, however, probably a LOT of your moves are just as good as > the moves of a good player. But it's the ones that fall short, that kill > you. > > Go on a big board is like 18 holes of golf compared to just 1 or 2 holes of > golf. The better player is far more likely to win the 18 hole match than > the 1 hole match. > > - Don > > > > > > On Tue, Apr 28, 2009 at 1:53 PM, Ivan Dubois wrote: >>> >>> I noticed that, in general, changes in the playout policy have a much >>> bigger impact on larger boards than on smaller boards. >>> >>> Rémi >> >> I think rating differences are emplified on larger boards. This is easy to >> see if you think about it this way : >> >> Somehow a 19x19 board is like 4 9x9 boards. Let us define a new game that >> I would call 4-Go where instead of playing one game, you play simultenously >> 4 games and determine the winner by calculating the sum of the scores of the >> four games. Certainly rating differences would be bigger with 4-go than with >> go (given the same two players). This explains why rating differences are >> bigger on 19x19 than 9x9. >> >> Ivan >> >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Could be that nobody is playing?
it would slowly grow in (measured) strength over time. s. 2009/4/20 terry mcintyre : > > > From: Jason House > >> CGOS requires us to use new names on the server each time we change our >> bots. It computes the strength using all games (heavilly biased with the >> results of the first 100 games) > > Hypothetically speaking, if a bot were to actually learn from experience, > how would CGOS deal with that? > > > > ___ > 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] COGS bug in Ko detection?
it's simply too easy to write the code to check for this on the server side for it to be a bug. :) s. 2009/4/13 Don Dailey : > Hi Brain, > > I get a superko bug report or two almost every month since CGOS has been > running (2 or 3 years?) It's usually due to a misunderstanding of which > specific superko rule CGOS uses. CGOS uses positional superko. I'm > quite sure there is no bug here. There are OTHER bugs in the server, but > not superko! > > - Don > > > > On Mon, 2009-04-13 at 09:32 -0400, Brian Sheppard wrote: > > Black is flagged for an illegal Ko at the end of game 738921 on CGOS. Black > played H1, which looks legal to me. Server bug? > > > > Scanning through the log today, I found a similar situation in game 738998. > > > > The setup is that two stones in the corner are captured by playing 1 stone. > Recapture of the capturing stone is declared a Ko. There was no SuperKo > repetition involved in either game. > > > > Best, > > Brian > > > > ___ > 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fast ways to evaluate program strength.
otherwise pair-go wouldn't be as funny to watch. s. On Tue, Apr 7, 2009 at 8:05 PM, Michael Williams wrote: > Łukasz Lew wrote: >> >> I would like to rephrase my question: >> Let's measure prediction of pro moves of a whole engine while >> modifying heavy playouts / MCTS in the engine. >> How well might it work? > > Probably not well. Because what matters is not how often you play strong > moves, but how often you avoid blunders. > > ___ > 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] Rules for remote play at the Computer Olympiad
Moreover, this is a really complicated issue. There has been some extensive statistical work on human cheating in chess done by Ken Regan at the University at Buffalo. However, this relies heavily upon the fact that computers dominate human play by a wide margin. The same is not the case in go. s. On Sat, Apr 4, 2009 at 1:56 AM, Robert Jasiek wrote: > Vincent Diepeveen wrote: >> >> If a program under no circumstance can reproduce a specific move and that >> for several occasions, then that's very clear proof of course. > > [...] >> >> Statistics prove everything here. > > No. Rather it proves that the program cheats OR that the methods of > detecting cheating are improper. > >> One always must have a logfile > > Good. > > -- > robert jasiek > ___ > 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] time measurement
a slightly simpler protocol: you let me put a machine on your local network that i control, and you agree to do an ntp-like service with it. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] time measurement
if it really mattered, remote participants could use a phone to connect -- it's not like these are very high-volume transmissions, and the latency, while high, is still an unimportant fraction of total time. on the plus side, the latency is exact. on the minus side, it's a pretty expensive phone call. :) s. On Tue, Feb 3, 2009 at 12:03 PM, terry mcintyre wrote: > I would not want to discourage remote players - some systems are designed to > take advantage of large supercomputers which are not very portable. > > However, remote players need to accept the trade-off. They get to avoid the > trouble of packing up and shipping a trailer full of computer gear to the > other side of the world. The downside is that network lag happens. > > As others have mentioned, client-side timing can be gamed by the simple > expedient of pulling the plug to the modem; I can think of a few ways to > manipulate iptables which would have similar effects. > > I hope that tournament organizers do their best to provide a decent > connection. Remote participants need to do likewise. > > > > > ___ > 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
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] Re: Hardware limits
also, it's quite surprising how few watts the human brain uses. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: GCP on ICGA Events 2009 in Pamplona
i think you might be estimating this incorrectly. s. On Sat, Jan 10, 2009 at 9:00 AM, Gian-Carlo Pascutto wrote: > Ingo Althöfer wrote: > >> What prevents you from freezing in your chess >> activities for the next few months and hobbying >> full (free) time on computer go. > > The amount of chess players compared to the amount of go players. > > -- > GCP > ___ > 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] 3-4-5 rule
that's with "or manhattan distance 2" as well? how about 3 or 4? s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey wrote: > After 842 games with 19x19 go the version with the 3-4-5 line rule is > scoring about 55% > > I thought it might do better, I think the rule is reasonably sound - but > 55% is pretty respectable for such an easy change and it hardly slows > down the search at all. > > Rank Name Elo+- games score oppo. draws > 1 d2p 2037 12 12 842 55% 20000% > 2 base 2000 12 12 842 45% 20370% > > > ___ > 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] Value of rule
don, this rule is very intuitive for a 19x19 board even if you include the 5th line. for a 9x9, i'm not so sure. s. On Sun, Dec 21, 2008 at 3:55 PM, Don Dailey wrote: > As previously mentioned, I have been testing the rule which says move > only to the 3rd and 4th lines unless something is nearby.In this > case, the rule is 3-5 lines. > > I started with 200 playouts, because I'm also interested in how this > rule affects play at various depths. Here is the 200 playout results: > > Rank Name Elo+- games score oppo. draws > 1 d2p 204188 5803 53% 20210% > 2 d2r 202988 5803 50% 20290% > 3 d3r 200988 5810 50% 20080% > 4 d3p 200788 5805 49% 20160% > 5 base 200088 5803 48% 20130% > > > Here is a key: > > base - no rule > d2 - distance 2 (must be <= 2, otherwise move only to 3-5 lines) > d3 - distance 3 > r - only applied to root move selection. > p - applied in playouts AND root move selection. > > So d2p - is the version with distance 2 applied in playouts and root. > > > >From the above ELO chart, the idea look pretty good. Distance 2 seems > to be superior to distance 3 and the best version takes it all the way > through the playouts. > > > The other test uses 2000 playouts. The results is not so rosy and > could be due to statistical noise. But at least the same idea tested > strongest, but only by 17 ELO. 17 ELO gives you a win expectancy of a > little over 52% using ELO's formula. > > > Rank Name Elo+- games score oppo. draws > 1 d2p 2017 12 12 2190 52% 20010% > 2 d3r 2004 12 12 2196 49% 20080% > 3 base 2000 12 12 2193 49% 20040% > 4 d2r 1999 12 12 2191 50% 19980% > 5 d3p 1993 12 12 2190 49% 20010% > > > Conclusion: At low playouts, it works well. At high playouts, it's > difficult to say if it helps or not. The evidence is slightly in favor > of using it, especially since it does not show much of a slowdown. I'm > now measuring approximately 3% slowdown for doing this in the playouts. > > I have a feeling this would work significantly better on larger boards, > so I will try 11x11 next. > > 11 x 11 is the best board size for go :-) > > - Don > > > > > > > > > > ___ > 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] MC Opening stage
the thing about "within manhattan distance (small) of other stones" type heuristics is that they seem to leave out the possibility of tenuki. s. On Thu, Dec 11, 2008 at 5:27 AM, Thomas Lavergne <[EMAIL PROTECTED]> wrote: > I've not tryed it for the moment due to lack of time for computer go, > but I've thinked about an opening heuristic thta from a go player point > of view seems acceptable : > - For the first play, restrict to intersection at a manhatan distance of > 2 from the corner hoshi (4-4 points) (and tengen if you want ot allow > a more cosmic style) > - Next restrict to a manhatan distance of 2 from : >- Corner hoshi >- Side hoshi if at there is a stone in at least one of the corners > and manhatan distance of 3 from stones already on board > As the game progress, increase theses distance progressively. Probably > something like add 1 to each every five moves. > > Play on the first line are forbidden until mid-game, unless there is a > stone in manhatan distance of 2. > > You can stop using early, for example at play 15 or 20, or wait to the > time were there is no restriction due to the ever increasing number of > stone and distance restriction. > > This cover most of professional games, and seems for me sufficiently > conservative. > Other policies can reduce more the search tree, but from my point of > view they can prune too much the search tree. > > Tom > > On Thu, Dec 11, 2008 at 08:29:40AM +0900, Darren Cook wrote: >> > Most of those 55 distinct moves are rarely used in the opening. I >> > once heard a simple rule which seems to cover just about everything >> > interesting: "consider only moves which are on the 3rd and 4th lines, >> > and/or within a manhattan distance of n, for some small n, of some >> > other stone already on the board." >> >> Wandering off the opening theme a bit, but the book, Oriental Strategy >> in a Nutshell, by Bruce and Sue Wilcox has numerous rules of thumb of >> this nature. It will probably appeal to the people on this list more >> than the wishy-washy "play here because it feels good" style of most >> traditional go books. The rules might be useful in MC heavy playouts. >> >> Going back to the topic, for 19x19 at least, I would suggest make an >> opening book from pro and strong amateur games. Only start using MCTS >> once you leave the book. Using MCTS on the first move is like trying to >> use a precision screwdriver to hammer in a three-inch nail: your tool >> will break before you get any worthwhile results. >> >> Darren >> >> -- >> Darren Cook, Software Researcher/Developer >> http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic >> open source dictionary/semantic network) >> http://dcook.org/work/ (About me and my work) >> http://dcook.org/blogs.html (My blogs and articles) >> ___ >> computer-go mailing list >> computer-go@computer-go.org >> http://www.computer-go.org/mailman/listinfo/computer-go/ >> > > -- > Thomas Lavergne"Entia non sunt multiplicanda praeter > necessitatem." (Guillaume d'Ockham) > [EMAIL PROTECTED]http://oniros.org > ___ > 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] MC Opening stage
and there are nontrivial arguments concerning points way out near the center. s. On Wed, Dec 10, 2008 at 3:39 PM, terry mcintyre <[EMAIL PROTECTED]> wrote: > > From: tony tang <[EMAIL PROTECTED]> > > >>> Back to the original question - accounting for symmetry, there 55 >>> distinct opening moves on a 19x19 board. > >>Are there a noted collection of these opening moves? if so could you direct >> me to the > material? cheers > > Do you mean the 55 distinct opening moves? Divide a 19x19 grid along the two > diagonals, and the vertical and horizontal midlines; you have eight > identical pie slices. The number of points in any triangular slice is the > sum of 1,2,3..10 - or 55. The slices share points along the common edges. > > Most of those 55 distinct moves are rarely used in the opening. I once heard > a simple rule which seems to cover just about everything interesting: > "consider only moves which are on the 3rd and 4th lines, and/or within a > manhattan distance of n, for some small n, of some other stone already on > the board." If memory serves, David Fotland mentioned this at the Portland > Congress. Some players favor opening moves on the fifth line, however. > > > > ___ > 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
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] On Don Dailey's first chess program
commercial software was freely available on BBSes when i was a small child, and very, very many people had modems. no internet access, but modems and local BBSes. s. On Sat, Nov 22, 2008 at 10:13 AM, Matthew Woodcraft <[EMAIL PROTECTED]> wrote: > Don Dailey wrote: >> A few years later I was pointed to a site where I could download that >> and just about any commercial chess program.We are talking several >> decades ago, I didn't bookmark the site or use it myself and I have no >> idea if it's still there. > > It seems to me that only a very small number of people would have been > in a position to download anything, several decades ago. What kind of > 'site' was it, anyway? Doubtless not a web site! > > -M- > > ___ > 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] One-sided 2-inch Rules
for small k, this should give a massive advantage to black. the additional requirement that white place a stone within the smallest cityblock distance of the last stone whenever he has no valid move within distance k of black's last move is an even more substantial advantage for black. i'm thinking that black can set up situations that cause white to make bad shape. if not, it's an unimportant rule, but otherwise it's a big advantage to black. just my $0.02. s. On Tue, Nov 18, 2008 at 5:20 PM, "Ingo Althöfer" <[EMAIL PROTECTED]> wrote: > Hello, > > one of the basic problems of go newbies > is their tendency to place the next stone > near to the latest stone of the opponent. > Sometimes this is called the "2-inch heuristic > of beginners". > > What do you think about a formalized variant > of Go with one-sided distance-k rule? > >> Let k be some natural number. >> The normal rules of Go hold, except for one thing: >> When possible, White has to place his next stone >> within distance k (in city-block metric) of the latest >> stone of Black. If there is no feasible move of this type >> the stone has to be placed within the smallest >> possible city-block distance of the latest stone of >> Black. White may pass at any time. Example: >> On 19x19 board k=36 would mean no restriction at all.) > > * What should be fair values of komi(k) or fair numbers > of handicap stones? > > * Main question: How strong would MCTS-based programs be in this variant(s)? > > * Would computers be stronger than humans for certain values of k? > > Ingo. > > -- > Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten > Browser-Versionen downloaden: http://www.gmx.net/de/go/browser > ___ > 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] simple MC reference bot and specification
sorry to be pedantic, but: 13. Chinese scoring. s. On Sat, Oct 11, 2008 at 9:11 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > On Sat, 2008-10-11 at 13:33 +0100, Claus Reinke wrote: >> I have a rough idea of what that might be. And I suspect that keeping >> this >> "de facto standard" implicit has been hiding some actual differences >> in what >> different people think that standard is. Some of my questions arise >> from trying >> to pin down where and why different authors have different ideas of >> what "the" >> standard is. If there has been some explicit standardisation since >> those papers >> were published, I'd be interested in a pointer to that standard and >> its rationale. > > I'm going to publish a real simple java reference program and some docs > to go with it and a program to "test" it for black box conformance. > (Actually, it will test 2 or more and compare them.) I would like to > get someone who writes better than I do to write up the standard in less > casual language but it goes something like this: > > 1. A complete game playing program so it can also be tested in real > games. > > 2. Play uniformly random moves except to 1 pt eyes and avoiding simple > ko. When a move is otherwise not possible, pass. > > 3. Playout ends after 2 consecutive pass moves (1 for each side.) > > 4. 1 pt eye is an empty point surrounded by friendly stones for the > side to move. Additionally, we have 2 cases. If the stone is NOT on > any edge (where the corner is an edge) there must be no more than one > diagonal enemy stone.If the point in question is on the edge, there > must be NO diagonal enemy stones. > > 5. In the playouts, statistics are taken on moves played during the > playouts. If the move is played FIRST (during the playout) by the side > to move it is one data point and the win loss record is maintained. > > 6. The move with the highest statistical win rate is the one selected > for move in the actual game. > > 7. In the case of moves with even scores a random selection is made. > > 8. Pass move are never selected as the final move to play unless no > other non-eye filling move is possible. > > 9. Random number generator is unspecified - your program should > simply pass the black box test and as a further optional test your > program should score close to 50% against other "properly implemented" > programs. > > 10. Suicide not allowed in the playouts or in games it plays. > > 11. When selecting moves to play in the actual game (not playouts) > superko is checked and forbidden. > > 12. If a move has NO STATS taken (which is highly unlikely unless you > do very few playouts) it is ignored for move selection. > > Did I miss anything? I would like to get feedback and agreement on > this. > > Please note - a few GTP commands will be added in order to instrument > any conforming programs. Haven't figured those out yet, but it will > be designed so that it can report number of nodes, number of playouts, > average score of playouts, etc. So the tester may set up some position > and a ko, and ask for statistics based on the number of specified > playouts. > > - Don > > > > > > > > > > ___ > 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] Congratulations to David Fotland!
sure, this would work much better, and is easy to implement (diameter is log(# nodes) if you set it up as an expander!). but writing it from scratch is a bit of a burden. i may have a project like this next semester for my networking class, if so, we can tack the rest onto it if anyone's interested, over the summer, perhaps. s. On Thu, Oct 2, 2008 at 5:19 PM, Zach Wegner <[EMAIL PROTECTED]> wrote: > On Thu, Oct 2, 2008 at 3:48 PM, steve uurtamo <[EMAIL PROTECTED]> wrote: >> The networking issue is somewhat more serious. >> Not the actual network delay, but the mechanism >> that the boinc client software uses to process work requests >> and the interval at which people typically send >> back their results is such that you'd be unlikely to >> get a single work request back until after you needed >> it. > > This makes the assumption that boinc is used, or at least that one > central server is used. I've thought a lot about this issue, and I > think one central server would be too inefficient. I would use a > distributed network, and let each computer just connect with a small > number of others, creating something more like a web than a tree. This > could be optimized for ping time as well--arrange the nodes in the web > so that they talk most with those close to them. > ___ > 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] Congratulations to David Fotland!
The fault tolerance is not a serious problem, even being tolerant against false result reporting isn't too bad with a decent error-correcting coding scheme for handing out the work. The networking issue is somewhat more serious. Not the actual network delay, but the mechanism that the boinc client software uses to process work requests and the interval at which people typically send back their results is such that you'd be unlikely to get a single work request back until after you needed it. This could work for very long-length (24h-ish) games, however, if that's the only boinc project that the remote machines were participating in. s. On Thu, Oct 2, 2008 at 3:43 PM, David Doshay <[EMAIL PROTECTED]> wrote: > Yes, various kinds of off-line (not in-game) processing could be done. > But nothing in a real-time game. > > Cheers, > David > > > > On 2, Oct 2008, at 10:48 AM, terry mcintyre wrote: > >> An @home network might be better for things such as creating opening >> books, testing algorithms, etc. > > ___ > 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] Analysis of 6x6 Go
even-sized boards have the disability that there's no tengen. i think that this makes mirror go functional until fairly late in the game. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: sgf format for non-quadratic board sizes?
every point having 4 liberties would seem to make the opening much more about influence. my guess is that it's an easier game. (but that's just wild speculation). s. On Fri, Sep 19, 2008 at 2:30 PM, David Doshay <[EMAIL PROTECTED]> wrote: > First move is easy, but depending upon ratio of diameter to length > of torus, ladders can get complicated. > > Cheers, > David > > > > On 19, Sep 2008, at 10:48 AM, Álvaro Begué wrote: > >> On Fri, Sep 19, 2008 at 1:29 PM, Don Dailey <[EMAIL PROTECTED]> wrote: >>> >>> Would go on a torus be interesting? There are not corners or edges, the >>> sides of the board simply wrap around. >>> >>> - Don >> >> Yes, it's probably similar in spirit to regular go, except everything >> feels like the center of the board. It would also make the first move >> easy. :) >> >> Álvaro. >> >> >>> >>> On Fri, 2008-09-19 at 09:52 -0700, Ross Werner wrote: Urban Hafner wrote: > > Ah, right. I thought you were talking about implementing this feature > for your own program. Personally I don't know of any program that > supports rectangular boards. There was a recent thread on GoDiscussions about this topic: http://www.godiscussions.com/forum/showthread.php?t=6960 Not much information there, but maybe enough to be useful. ~ Ross ___ 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/ >>> >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: OT: Teaching Go (was Re: Disputes under Japanese rules)
i've read suggestions along the lines of teaching "capture go" first. this should get a lot of the life-and-death intuition under the belt (plus should help learn counting liberties). s. On Thu, Sep 18, 2008 at 3:15 PM, Jeff Nowakowski <[EMAIL PROTECTED]> wrote: > On Thu, 2008-09-18 at 11:12 -0700, Peter Drake wrote: >> Eventually, sure -- but I'd like them to have a few games under their >> belts before I bring up the issue of different versions of the rules. > > Ok, then play some 9x9 games with area scoring rules as Dave Devos > suggested. I was making the same suggestion. Don't hit them with both > rules at the same time, but make sure to choose the right set to start > with! > >> I may just follow Kim and Jeong's pedagogical lead and let the >> students experiment with pieces of the rules before trying to play a >> complete game. > > It's ok to teach "unconditional life" or simple life and death first, > but once you get beyond that you need to be able to end and score the > game, and beginners just can't do that easily with territory scoring and > an agreement phase. > > I tried to learn with Kim's "Learn to Play Go", and I was absolutely > confused and frustrated when it came to end game scoring. > >> The computer scientist's instinct is to lay down a >> terse and elegant set of rules and then deal with the consequences of >> those rules, but perhaps that is a bad thing when teaching. > > You need foundations to build on. One foundation is life and death; > however, life and death is just a simple consequence of the capturing > rule. The other foundation is the score at the end of the game. Having > an easy way to score let's the beginner experiment with what is alive > and what is dead, what is true territory that cannot be invaded. An > informal agreement phase with rules that punish a player for trying to > "play it out" is a detriment. > > Nobody is advocating that you give noobs Tromp-Taylor and letting them > figure it out. Just don't give them territory rules with dead-stone > agreement as a first ruleset. > > -Jeff > > ___ > 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] Congratulations to Leela and to Many Faces!
without vast captures of territory, someone will either violate the superko rule or make an illegal move before lots of time passes. s. On Tue, Sep 16, 2008 at 10:24 AM, Jeff Nowakowski <[EMAIL PROTECTED]> wrote: > On Tue, 2008-09-16 at 10:10 -0400, Don Dailey wrote: >> It's a shame Fischer Timing is not available. A small Fischer >> increment of 1 or 2 seconds would do the job nicely. > > It doesn't solve the problem of two programs that don't pass. You can't > keep to a fixed schedule if you keep on allowing "just a few seconds > more" ad nauseum. > > -Jeff > > ___ > 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] Disputes under Japanese rules
>> I've asked this question of a couple of people and got different answers, >> so I thought I'd check here. to get a different set of different answers. :) >> Suppose, under Japanese rules, I throw a (hopeless) stone into your >> territory. I keep passing until you've actually removed it (playing four >> stones inside your own territory, thus losing a net three points). If you >> try to pass as well, I stubbornly insist that the stone is alive, thus >> restarting the game. stones on the board aren't counted unless they're dead. your hopeless one stone has neither two eyes nor is a seki, so i can ignore it and we will remove it from my territory after the game is over. in fact, after you place it there, i will pass, unless you've actually caused me some danger by placing it there, in which case i will respond (and the net effect will be that we will each have placed a stone inside my territory, not affecting the outcome of the score so far). if, after we've both passed, you suggest that this clearly dead stone is in fact alive, and that all of its surrounded territory should be counted as yours, i'll point out that it doesn't surround any territory and isn't a seki, so is dead. the stones on the board that are alive dont count toward points in japanese rules, just the territory, so it matters not how many stones are on the board or if you've placed a stone inside my territory, simply that we agree on the life and death status of stones inside what we both agree *is* our territory. right? so imagine instead that you have three dead stones inside my territory and place a fourth, surrounding one point of territory, and i pass, and you place a fifth and create some intensely important ko or seki opportunity for yourself. well, then perhaps i shouldn't have passed. i was being greedy, or cocky, by taking those 3 free points, but after that, i should have been more careful. when i was first learning how to play, i would occasionally drop a stone into my opponent's territory thinking that it counted for something (that i could build life in the hopeless chasm of my opponent's territory). he'd pass. i'd drop another in. he'd pass again. basically, until he responded, i was making moves that didn't provide a real threat to him. it was only after a bit of gentle advice that i realized that i was both giving him free points and annoying the crap out of him. even an opponent who doesn't understand the concept of two eyes or seki could be persuaded according to the "official procedure", which i've never seen anyone need to use in practice. if the putative opponent actually doesn't understand two eyes or seki, playing out on a separate board might be a good way to educate them without ruining the stones-in-play and creating a situation that is well-nigh impossible to undo without convincing your opponent that you're doing something sneaky to the score. of course, you could bore them to tears by writing each move down in the on-the-board after-game sequence so that they could be undone, one at a time, after life or death had been established. superko and bent four in the corner actually do require someone explaining why this is a rule, same as explaining why ko is a rule. ko because it makes the game more fun. superko because of the same thing as ko only over a longer timeframe. bent four because it's a totally crappy situation that is hard to resolve otherwise. in the case of malicious intent, a much simpler option, which i have seen exercised, is for the stronger opponent to resign and watch or start a game with someone else. it's about having fun, after all. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bobby Fischer
i thought that story was about lasker. s. On Thu, Sep 11, 2008 at 9:43 AM, Magnus Persson <[EMAIL PROTECTED]> wrote: > I know a 4-Dan player who told a story that goes something like this: He and > his friends who were all very strong chess players at the time, discovered > the rules of go and played a bunch of games against each other until they > thought they mastered it. Later they met a player who gave them a 9-stone > handicap and beat them easily. They were shocked and told him he must be a > master player but he just replied: "No I am just a beginner". > > -Magnus > > Quoting Mark Boon <[EMAIL PROTECTED]>: > >> On Thu, Sep 11, 2008 at 8:53 AM, Adrian Grajdeanu <[EMAIL PROTECTED]> >> wrote: >>> >>> I read that story in a book, just after Bobby Fisher's death. Don't >>> remember >>> all details, save that he was astonished he got beaten. >>> Adrian >> >> Hehe. After I learned the game (from a book, playing with my father >> who brought a set from Japan for my birthday) I was also astonished to >> be beaten by the first other person I met that knew the game. And he >> gave me 9 stones handicap! But rather than putting me off it made me >> even more intrigued by the game. Now I know this person was probably >> not even 15 kyu. >> >> Mark >> ___ >> computer-go mailing list >> computer-go@computer-go.org >> http://www.computer-go.org/mailman/listinfo/computer-go/ >> > > > > -- > Magnus Persson > Berlin, Germany > ___ > 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] Time controls in bots vs human matches
only if the human won all games and the machine didn't use opponent's time would that be true. any other combination would definitely show something. s. On Thu, Sep 4, 2008 at 2:40 PM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote: > Don Dailey wrote: > >> In such a case, I think it's better for the human not to have a time >> control at all. This is more satisfying than having a human lose on >> time, but giving the win to him anyway under the assumption that he >> didn't really need all that time even though he used it. > > I think the problem is that in this case the match can't possibly show > anything. > > -- > GCP > ___ > 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] Kaori-Crazystone
in fact, if you made a betting game out of it, and formed a pool that would go to anyone willing to take the challenge, i think that you'd find that the ratio of dollars "against" to dollars "for" would be a fairly accurate depiction of the strength increase over time. the ratio would likely lag behind the reality, but with money involved, people might tend to think more carefully about the situation. i think that people have set up such market indicators for all kinds of things just to see how accurately they predict reality. s. On Thu, Sep 4, 2008 at 12:38 PM, steve uurtamo <[EMAIL PROTECTED]> wrote: > 1d (amateur) is a kind of holy grail for amateurs, because > it separates fairly serious players from people just messing > around, so seeing a program at that level on a 19x19 board at > reasonable (non-blitz) time controls is quite impressive. > > 1p is generally stronger than all but a small handful of > amateurs, so can be thought of as >=7d (amateur). > > beating a 1p in a zero-handicap game would be a > really, really big deal for a computer player. $1M prize > was well-considered, from that point of view. i think > that the "insurance value" of such a proposition is still > pretty low. > > s. > > On Thu, Sep 4, 2008 at 11:38 AM, Don Dailey <[EMAIL PROTECTED]> wrote: >> It's difficult for me to understand this due to different ranking >> systems and pro ratings vs amateur ratings. I see here listed as a 4 >> dan player on this page: >> >>http://www.nihonkiin.or.jp/player/htm/ki000343.htm >> >> >> Is that 4 dan pro? My understanding is something like this: >> >> kyu player are casual players (or weak tournament players) >> >> low dan players are something like advanced amateurs or experts and weak >> masters in chess. >> >> Pro's are like super high dan players and there is not very much >> difference between ranks compared to regular dan players. I have heard >> that a 1d professional will beat a 9d professional with 3 or 4 stones. >> >> So a 1d pro is something like a 7 or 8d+ amateur? >> >> Is this all "roughly" correct? >> >> So I assume that Aoba Kaori is a 4d professional? That would relate to >> something in the ballpark of 9 or 10d amateur if there were such a >> thing. And with 8 stones handicap, this implies that CrazyStone did >> what a 2d+ would have done, or it is weaker than 2d but got lucky. So >> it's "performance rating" for that one game is lower bounded at around 1 >> or 2 dan. Since it won the game we could pick 2 dan as a better lower >> bound guess although since it won we do not have a reasonable upper >> bound guess on it's performance except our own credulity. >> >> Does what I said make any sense? I am not a go player and I'm not very >> comfortable with this guesswork. In chess, if you beat a player I am >> used to thinking in terms of setting a performance rating of around 400 >> ELO higher for that one game. I know this is not precise, but I also >> think of 400 ELO subtracted from the player you beat as a kind of >> "estimated" lower bound on your strength. If you beat a 2500 ELO chess >> player, it's a relatively safe bet that you are at least 2100 ELO in >> strength although technically there is a chance you could lose to >> anybody, even a random move generator. >> >> I know this isn't precise language, but how many ranks would give us >> around 90 - 95% confidence of superiority?If I beat a 5 dan player, >> could you say that it's "very likely" I am at least 3 dan in strength? >> >> I'm thinking that if we estimate Aoba at 10d amateur and CrazyStone wins >> with 8 stone handicap, it is roughly equivalent to beating a 2d player >> without handicap and that we can subtract 2 stones to say that with >> pretty high confidence CrazyStone is playing at least 1 kyu (but that's >> it's much more likely Crazy Stone is stronger than this - after all it >> performed in this one game at least as well as 2d player.) >> >> >> - Don >> >> >> >> >> On Thu, 2008-09-04 at 16:28 +0200, Rémi Coulom wrote: >>> terry mcintyre wrote: >>> > Congratulations! >>> > >>> >>> Thanks. >>> >>> > I'm dying for details! What was the time limit? >>> >>> The organizers asked that the program should play at a constant time (30 >>> second) per move. The sgf file contains time stamps (you can see the
Re: [computer-go] Kaori-Crazystone
1d (amateur) is a kind of holy grail for amateurs, because it separates fairly serious players from people just messing around, so seeing a program at that level on a 19x19 board at reasonable (non-blitz) time controls is quite impressive. 1p is generally stronger than all but a small handful of amateurs, so can be thought of as >=7d (amateur). beating a 1p in a zero-handicap game would be a really, really big deal for a computer player. $1M prize was well-considered, from that point of view. i think that the "insurance value" of such a proposition is still pretty low. s. On Thu, Sep 4, 2008 at 11:38 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > It's difficult for me to understand this due to different ranking > systems and pro ratings vs amateur ratings. I see here listed as a 4 > dan player on this page: > >http://www.nihonkiin.or.jp/player/htm/ki000343.htm > > > Is that 4 dan pro? My understanding is something like this: > > kyu player are casual players (or weak tournament players) > > low dan players are something like advanced amateurs or experts and weak > masters in chess. > > Pro's are like super high dan players and there is not very much > difference between ranks compared to regular dan players. I have heard > that a 1d professional will beat a 9d professional with 3 or 4 stones. > > So a 1d pro is something like a 7 or 8d+ amateur? > > Is this all "roughly" correct? > > So I assume that Aoba Kaori is a 4d professional? That would relate to > something in the ballpark of 9 or 10d amateur if there were such a > thing. And with 8 stones handicap, this implies that CrazyStone did > what a 2d+ would have done, or it is weaker than 2d but got lucky. So > it's "performance rating" for that one game is lower bounded at around 1 > or 2 dan. Since it won the game we could pick 2 dan as a better lower > bound guess although since it won we do not have a reasonable upper > bound guess on it's performance except our own credulity. > > Does what I said make any sense? I am not a go player and I'm not very > comfortable with this guesswork. In chess, if you beat a player I am > used to thinking in terms of setting a performance rating of around 400 > ELO higher for that one game. I know this is not precise, but I also > think of 400 ELO subtracted from the player you beat as a kind of > "estimated" lower bound on your strength. If you beat a 2500 ELO chess > player, it's a relatively safe bet that you are at least 2100 ELO in > strength although technically there is a chance you could lose to > anybody, even a random move generator. > > I know this isn't precise language, but how many ranks would give us > around 90 - 95% confidence of superiority?If I beat a 5 dan player, > could you say that it's "very likely" I am at least 3 dan in strength? > > I'm thinking that if we estimate Aoba at 10d amateur and CrazyStone wins > with 8 stone handicap, it is roughly equivalent to beating a 2d player > without handicap and that we can subtract 2 stones to say that with > pretty high confidence CrazyStone is playing at least 1 kyu (but that's > it's much more likely Crazy Stone is stronger than this - after all it > performed in this one game at least as well as 2d player.) > > > - Don > > > > > On Thu, 2008-09-04 at 16:28 +0200, Rémi Coulom wrote: >> terry mcintyre wrote: >> > Congratulations! >> > >> >> Thanks. >> >> > I'm dying for details! What was the time limit? >> >> The organizers asked that the program should play at a constant time (30 >> second) per move. The sgf file contains time stamps (you can see the >> time with gogui, for instance). I don't know what was her time control, >> but she apparently played at the same pace as the program. >> >> > Did the game end on time or by resignation at move 179? >> > >> >> She resigned. >> >> > The pro was Aoba Kaori, yes? >> > >> >> Yes. >> >> The only other information I have about the match are these pages in >> Japanese: >> https://secure1.gakkai-web.net/gakkai/fit/program/html/event/event.html#6 >> http://www.ipsj.or.jp/10jigyo/fit/fit2008/events.html#1-4-1 >> >> I hope the organizers can send me some photos tomorrow. Then I will set >> up a web page and tell the list. >> >> Rémi >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yet a mogo vs human game
out of curiosity, can you estimate the largest number of opponents that all played each other a reasonable number of times? (i.e. what's the largest subset of opponents and number of games that you can choose so that everyone started playing everyone else in the subset without anyone leaving for good)? i've got some HMM code lying around and could generate the full matrix of win probabilities from such a dataset. this would answer the question, "just how intransitively do these players play against one another". s. On Thu, Aug 28, 2008 at 12:37 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > If you ever want to try, I can give you the data for cgos in compact > form that you can experiment with (one line per game - 2 names and 1 > result + date) or you can simply extract them from the archived games. > > - Don > > > On Thu, 2008-08-28 at 17:44 +0200, Rémi Coulom wrote: >> This was my post about multi-dimensional Elo: >> http://www.mail-archive.com/computer-go@computer-go.org/msg06267.html >> >> I have not tried it since that time. >> >> Rémi >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yet a mogo vs human game
this approach would also severely limit the number of players that could be involved in the rating system, since it would require manipulating an 2*(N choose 2) matrix, where N is the number of players involved. s. On Thu, Aug 28, 2008 at 12:35 PM, steve uurtamo <[EMAIL PROTECTED]> wrote: > you could use HMMs as long as you > didn't mind retraining (and thus starting your ratings > system over from scratch) every time you added or > subtracted a new player. it'd be relatively fast in any case. > > s. > > On Thu, Aug 28, 2008 at 11:44 AM, Rémi Coulom > <[EMAIL PROTECTED]> wrote: >> This was my post about multi-dimensional Elo: >> http://www.mail-archive.com/computer-go@computer-go.org/msg06267.html >> >> I have not tried it since that time. >> >> Rémi >> ___ >> 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] yet a mogo vs human game
you could use HMMs as long as you didn't mind retraining (and thus starting your ratings system over from scratch) every time you added or subtracted a new player. it'd be relatively fast in any case. s. On Thu, Aug 28, 2008 at 11:44 AM, Rémi Coulom <[EMAIL PROTECTED]> wrote: > This was my post about multi-dimensional Elo: > http://www.mail-archive.com/computer-go@computer-go.org/msg06267.html > > I have not tried it since that time. > > Rémi > ___ > 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: mogo beats pro!
this is interesting! perhaps i misunderstand the setup of the experiment -- what is the unit of measure for the delay, or how is delay being implemented? the FIFO queue is doing what, and where is the delay being introduced? thanks, s. On Wed, Aug 13, 2008 at 9:20 AM, Hideki Kato <[EMAIL PROTECTED]> wrote: > Magnus Persson: <[EMAIL PROTECTED]>: >>Quoting Don Dailey <[EMAIL PROTECTED]>: >> >>> Yes, UCT is easier to use with multiple CPU's because with additional >>> processors alpha-beta programs do wasted work, unless you are talking >>> about theoretical programs with perfect move ordering, which you aren't. >> >>Nice that all is clear about alpha-beta programs. >> >>But... does not UCT with additional processors waste a lot of >>simulations because what would be the optimal path through the search >>tree depends on the threads that have not finished yet? > > Yes, UCT does. From my recent experiments with a delay > line (a fixed size FIFO queue) between a UCTsearcher and an MC > simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single > thread): > > delay #po winsgames winning rateELO 1 sigma of wr > 0 1,000 721 2,000 36.05% -99.6 1.07% > 1 1,000 721 2,000 36.05% -99.6 1.07% > 2 1,000 690 2,000 34.50% -111.4 1.06% > 3 1,000 663 2,000 33.15% -121.8 1.05% > 5 1,000 642 2,000 32.10% -130.1 1.04% > 10 1,000 522 2,000 26.10% -180.8 0.98% > 20 1,000 412 2,000 20.60% -234.4 0.90% > 50 1,000 82 2,000 4.10% -547.6 0.44% > > Hideki > >>Some people reported that more processors helps a lot on large boards, >>whereas on smaller one there is not much gain. >> >>-Magnus >>___ >>computer-go mailing list >>computer-go@computer-go.org >>http://www.computer-go.org/mailman/listinfo/computer-go/ > -- > [EMAIL PROTECTED] (Kato) > ___ > 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] What was the specific design of the Mogo version which beat the pro...
> And what language/platform is Mogo written in; C/C++, Java, Assembly, PHP, > etc.? This made coffee spray out of my nose (PHP). I think that C is most likely, based upon how they parallelized it. Did you read the list posting that mentioned (briefly) how they scaled it up? s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
what happens when the opponent deviates from joseki? knowing how to punish joseki mistakes can be very, very tricky. also knowing which joseki to use where is very, very sophisticated. the wrong joseki can be worse globally than a non-joseki move. s. On 8/12/08, Ian Osgood <[EMAIL PROTECTED]> wrote: > > On Aug 12, 2008, at 5:25 AM, Don Dailey wrote: > > > > On Tue, 2008-08-12 at 08:43 +0200, Gian-Carlo Pascutto wrote: > > > > > > > > I don't like opening books. They are a liability when the rest of the > > > program is still improving so quickly. > > > > > > > I had one that worked effectively, but had to be redone if the program > > improved substantially, so it was a program. I essentially deep-search > > each new position encountered. So each game played presented a new book > > position to learn which I did off-line. It even had variety - I didn't > > want it too predictable so I deep searched N times, and used the moves > > in the same ratio they were chosen. Usually only 1 or 2 moves get > > played. > > > > This is a different kind of opening book than I'm thinking of. You are both > talking about cached computation, whereas I consider an opening book as > codified theory and wisdom gained over the entire history of the game > (semeais and joseki). How could adding established semeai and joseki > patterns (probably for early move selection and bias) to a program make it > weaker? If anything, the global view of full-board MCTS has the potential > to make better use of semeai and joseki patterns than the classical > shallow-search programs. > > Self-learned books were also abandoned in chess. Hand tuned books are labor > intensive, often requiring a separate team member to create them, but the > best chess programs all have them. > > Ian > > > ___ > 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: Strength of Monte-Carlo w/ UCT...
> You mentioned three proofs relating to go... could you post the links to the > papers? the first two statements are consequences of the following: all two-person, finite, zero-sum games have solutions. * for a more precise statement, see john von neumann's 1928 paper: Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320 and the definitions of the terms used in the statement (*). or perhaps more helpfully, a modern treatment on the subject of game theory. the third statement is true simply because the minimax algorithm exists. i am not claiming that any of this has anything to do with the actual problem of beating a human. i am not making this claim because i also make the claim that beating humans at go is pretty much unrelated to the mathematics in these proofs. > I didn't ask for a mathematical proof saying if a computer can beat a human. > I asked in a roundabout way if this algorithm (or any known algorithm) has a > proven complexity that is somehow tractable or useful to beat humans. Just > by throwing human in does not mean you are out of the realms of math. What > about statistics? The object of many statistical models is a group of > people. So please don't say it makes no sense to ask about mathematical > proofs of anything related to humans. A mathematical proof can have a result > that affects humans. If it was proven tomorrow that there is a set of > algorithms that can solve the game in poly time.. we could draw relevant > conclusions with regards to beating a human being. Relating humans to math > does not destroy the accuracy of the relation. algorithms do not have complexities, problems do. algorithms may have asymptotic runtimes, but even this isn't always true. poly time doesn't mean tractable. just like exptime doesn't mean intractable. there's a coefficient in front of the polynomial (or exponential function) that can radically affect the real-world tractability of the problem. another thing is that complexity classes are used to describe problems like, "find me an algorithm that can solve the game of go for *any* sized board". in this sense, go is quite difficult. however, nobody on this list is seriously hoping to write a program to solve go for any sized board and hoping that it will succeed on a 19x19 board. what they are doing is trying to engineer very good programs to beat humans on a 19x19 board. > whether or not computers can beat humans at go on a > 19x19 board in a reasonable amount of time is unrelated > to mathematics. > > Why? Let's say you can prove that the game is solvable so that black wins. > Let's say that you can prove that it is solvable in linear time. You can > then infer that we could build a machine to play the solved game and beat a > human unconditionally. Why can't you use the math here to make a statement > about beating humans? what if the linear function is this one: time = 10^10^10^10^10^10^10 * (size of board) that doesn't imply tractability, but it is still linear. the problem that i mentioned earlier: "how much effort is required to completely solve the game of go for _any_ given boardsize" is known not to be linear. it's known not to be polynomial. the problem of "solve the game of go for a 19x19 board" is known to be a *constant*. since there are only a finite number of legal board situations, there are only a finite number of legal games. enumerating all of these takes a constant amount of time. storing these takes a constant amount of space. this is not useful to make good programs for playing go, however. the thing is, all of the talk of asymptotics that you seem to be referring to are perfectly useful to prove things about arbitrary games on arbitrary sized boards, but when you have a fixed-size board, what matters is much more an issue of engineering a fixed problem. s. > > ___ > 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: Strength of Monte-Carlo w/ UCT...
erm. you guys seem to be arguing for the sake of arguing, without a clear or precise definition of what you're even arguing about. there is a mathematical proof that go, for any fixed sized board, can be completely solved. there is a mathematical proof that given a fixed komi and fixed number of handicap stones, every game is either a forcible win or loss or draw for a particular one of the two players. we don't know this function yet, so we don't know if there's advantage for white or black or not, but it's guaranteed to exist. is proven to exist. there is a mathematical proof that current algorithms can solve go. it makes no sense to ask if there is a mathematical proof of anything related to humans. the two are simply incommensurate. the mathematical proofs are simply about whether a computer with a lot of memory and a lot of free time can win or force draws in every game of go against any player. and it turns out that this is true. whether or not computers can beat humans at go on a 19x19 board in a reasonable amount of time is unrelated to mathematics. * computers are getting better and better at go. most people on this mailing list are mainly interested in helping (*) to happen. s. On Sun, Aug 10, 2008 at 11:46 PM, Denis fidaali <[EMAIL PROTECTED]> wrote: > > Hi there. > > I do agree with your point Robert Waite. > I have yet seen no such paper as one that would prove that there is such > thing as scalability based on any mathematical proofs. > So all your points at criticizing the "mathematical certainty" of the > scalability, is probably 100% right. There is no such things as mathematical > certainty there. > > It can be modelized easily, as you already did : what if the the "evaluation > function" is giving "on purpose" wrong data. How would one mathematically > prove that it doesn't ? You would at a minimum have to know WHAT the > "evaluation function" ACTUALLY exactly is ... In fact all the evidences that > we have gathered about the scalability may rather been surprising to some > persons : why in hell does all that works so well ? > > But, it's a "proven" fact that it does indeed works well so far. So that it > seems perfectly natural to speak such phrases as "there are evidences that > given the hardware we got in twenty years, human will be beaten by current > algorithms". I don't see how those evidences can be qualified with the term > "mathematical", but they are here (hiding among us !). Now if someone has > the feeling that maybe there is a roadblock, it has to be considered for > what it is : a personal intuition. What is this intuitions precisely based > on ? Why are you trying to share it with us in the first place. For myself, > i believe that what you are trying to do, is to begin to analyses all the > data the community has gathered so far, trying to understand why indeed it > worked so well that it even beaten out a pro with a 9 stones handicap and > with as few as 1.7 million evaluations/second (running on some 800 hundreds > cores). To the point that the pro felt he had no chances of wining at all > with that much of a handicap. Your are trying to understand this, and are > probably right on track for that goal. The term "mathematical" is very > valuable to you, and you'll find it that it has a much wider use (on this > list) than what you would like it to. But now, "mathematics" as proven to be > of little use in the context of go programming lately. It's more of a > "physician" world. You make up a (mathematical) model. You test it again > "reality" via experimentations. You then get "empirical" certitudes that the > model is indeed correct. > > There is no way of mathematically proving that light speed would still be > constant if i chose to dance naked on the champs-Elysée some day. You'll > definitely find no paper on that. Yet to speak of it as mathematically > certain, is probably not as wrong as it sound. > > > But as it is, i'm playing the devil advocates here. I'm totally agreeing > with you. I found your way to fight irrationnality very interesting indeed. > It's been very refreshing. > > > - > Robert Waite has wrote : > > I would really like to see what paper you are referring to. Do you mean > "Bandit based Monte-Carlo Planning"? Please post the name of the paper which > you are referring to. I do not think that the empirical evidence is > overwhelming that it is scalable in a practical way for the problem of > beating a human. > > Now the topic has moved to scalable to beat a human and I disagree with the > interpretation of the data. We are both interpreting data. Your data doesn't > count as a theory.. where you reduced my theory to one that has no data. We > are both interpreting the same data. Diminishing returns was just an example > of something that could be a roadblock. I was questioning how this > necessarily scales to humans. It seems more data is needed from MC-prog
Re: [computer-go] Some cgos 19x19 suggestions
david, is mfgo-12-0805-2c really over 400 ELO better than mfgo-11, as cgos seems to suggest? or is mfgo11 still rising up into place? thanks, s. On Sun, Aug 10, 2008 at 8:51 AM, David Fotland <[EMAIL PROTECTED]> wrote: > First, thank you very much, Don, for giving us a reliable 19x19 server. > > Please consider increasing the time a program stays on the list until it > ages off. I guess you drop programs from the ratings page after some time > that depends on the number of games they have played. Since 19x19 games > take 4 times longs, it seems you should allow four times as much time to age > off the list, for the same number of games. I like seeing the top program's > results a little longer. > > It would be nice if a program can get into position more quickly. Since the > games take longer, it can take several days to climb up from the initial > 1200 to 2000, especially if there is an early loos. Does it make sense to > set the initial k value a little higher, or to set the initial rating to > 1500 instead of 1200? > > -David > > > ___ > 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: mogo beats pro!
again, not true. there are an infinite number of complexity classes beyond P that do not require "infinite space" or "infinite time". exptime would just take exponential time instead of polynomial time, and pspace would just be able to reuse its available polynomial space (and thus use at worst exponential time). there are no problems that "would take infinite time" or "infinite space". there are problems that cannot be solved no matter how much space or time you give a computer, but that's a different matter altogether, and go isn't one of those problems. s. On Fri, Aug 8, 2008 at 6:53 PM, Robert Waite <[EMAIL PROTECTED]> wrote: >>> Besides... solving a >>> pspace-complete problem would require infinite memory... isn't that >>> correct? > >> nope. > > I flipped memory and time there. If pspace-complete is not in p, then it > will be a big problem trying to solve it without infinite time. That doesn't > seem like an ideal situation for solving it. > > > ___ > 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] mogo beats pro!
your calculation is for mogo to beat kim, according to kim and the mogo team's estimates. i think that a better thing to measure would be for a computer program to be able to regularly beat amateurs of any rank without handicap. i.e. to effectively be at the pro level. for one thing, this is easier to measure, and for another, it relies much less on mogo staying the same, kim being correct, or some other professional being much better against computer players, for instance. it just requires some machine connected to KGS to be able to attain, say, 9d, and keep it for a month or so. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some cgos 19x19 suggestions
one more thing -- you may want to keep anchors from playing one another. at least, i seem to recall that i saw two anchors playing one another. it can't (by definition) affect anyone's ratings, so... probably pointless for them to do so, right? s. On Sun, Aug 10, 2008 at 11:27 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > On Sun, 2008-08-10 at 14:15 -0400, Don Dailey wrote: >> I will also modify the server so that losses by anchors don't count. > > Woops, what I mean is losses on TIME won't count. They will still > count if the opponent loses but not if the anchor loses. > > - Don > > > ___ > 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: mogo beats pro!
> Besides... solving a > pspace-complete problem would require infinite memory... isn't that correct? nope. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
i don't think that it's known to be exptime-complete. certainly there was a joke here that i'm missing. :) s. On 8/8/08, Imran Hendley <[EMAIL PROTECTED]> wrote: > > > > go is worse than np-complete, it's pspace-complete. > > > > > > s. > > > > I thought it was even worse than that ;) > > > ___ > 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: mogo beats pro!
go is worse than np-complete, it's pspace-complete. s. On 8/8/08, Robert Waite <[EMAIL PROTECTED]> wrote: > > well, in opposition to the p neq np problem, this is a fixed > > boardsize. it's an engineering, optimization, and special-purpose > > algorithm issue at this point. no need for any solution to work > > > for "all boardsizes" in some measurable, scalable way. > > I don't necessarily think that go is np-complete... but the board > does not have to be infinite to be intractable. I mean.. let's > > say that 19x19 go or some other game has 3^361 possible positions. > That seems to be bigger than the number of available matter we > have to construct memory. > > It seems like there would be a set of algorithms that will be > > able to beat the strongest human players of go. But it is not > certain that there aren't certain limits to what we can calculate > with computers. This is why the whole p != np is interesting. > There are many common algorithmic problems that might not have > > a polynomial run time solution. > > Go has many angles of attack... but how about eye shapes... how many > possible 4 stone connected eye shapes are there? Its like tetris.. there > are 5 unique shapes. But so far... no one has found an efficient algorithm > > that will tell you how many unique shapes for N connected stones. > I think they have only calculated to N=28. This isn't really an NP > type problem as it is not a decision problem... but it could > well be intractable. > > > It is possible that as time goes on... computer go (or any computer) will > run > into certain problems that cannot be solved on a traditional computer. > > > ___ > 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: mogo beats pro!
well, in opposition to the p neq np problem, this is a fixed boardsize. it's an engineering, optimization, and special-purpose algorithm issue at this point. no need for any solution to work for "all boardsizes" in some measurable, scalable way. s. On 8/8/08, Robert Waite <[EMAIL PROTECTED]> wrote: > I might come off as being strongly opinionated on the topic.. but I have > been of the opinion for a while that maybe playing go is a problem that > can't be solved by computers. I kinda want p != np and for us to be confined > by mathematics (sorry).The general taunt from my side is that "A computer > can only beat a weak amateur" or "A computer is easily beaten by an amateur > child". > > This record clearly will make those taunts change. It certainly affected my > opinion of the strength of statistical analysis. > > ___ > 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: mogo beats pro!
don, thanks for your thoughtful comments. 9 handicap is still a real game, in the sense that the handicapping isn't arbitrary -- it definitely measures some skill difference. i think that even a match of 3 games would give quite a bit more information, although i thought that Mr. Kim had said that 9 stones would be too much regardless (or suggested as much). when janice kim won against a (13 stone?) computer handicap, that was showmanship, but a good highwater mark at the time. it'd be great if mogo, with hardware like this, or even a drastically reduced hardware set, could compete often enough to get an official ranking according to, say, the european go federation. but people are unlikely to want to risk rating points against computers, i'd think. i think that the suggestion that the mogo team with this hardware could beat a 1dan amateur regularly without handicap isn't really in question, but it'd still be worth seeing in practice. (and i wonder, as i'm sure a lot of the other scaling geeks here are, about just how much cluster you'd need in order to perform at that (1d-ish) level). although there's nothing magical about 1d versus 2d or 1k, the "dan barrier" still has an allure for many people, because it's just so difficult to attain for many amateurs. s. On 8/8/08, Don Dailey <[EMAIL PROTECTED]> wrote: > I think events like this are great. They generate interest and > excitement and are great fun. > > But they have very little scientific value. They are wide open for > speculation, non-objective analysis, etc. Often strong players fail to > take matches like this seriously because they are exhibitions with > nothing particular at stake. I don't know if this was the case or not > but I know it is happens. > > Also, it seems silly to me to find super strong players only to heavily > handicap them. What's with that? I know of course why, nobody > cares about an exhibition match with an ordinary player an thus it has > value. But it really underscores the nature of this kind of > exhibition, not really a significant scientific experiment. No serious > conclusions are possible.It's also rather silly to rank moves and > not performance in general over many games. Such and such a move was a > 5 dan move, this other move was a kyu level move, etc. This is a > sound bite to make people happy but isn't very quantifiable. > > Nevertheless, I have high praise that such an event took place, it's > always super-cool to be able to utilize such a powerful machine and this > was a good excuse to do so. > > I am left relatively confused about the outcome however. Someone gave a > computer a bunch of stones and it was able to beat a strong player. Is > that supposed to be exciting? I think I would simply be embarrassed > that it was believed that so many stones were necessary to even the > match. (Of course compared to a few years ago, this is an impressive > victory for a computer go program, although only a single data point.) > > I hope I don't come across as being critical, I think this was a great > idea and such matches should be arranged whenever possible. I just get > a little embarrassed when too much significance is made of it. > > - Don > > > > > > > On Fri, 2008-08-08 at 10:13 -0400, Robert Waite wrote: > > I was in the KGS room for a couple of hours before the match and a > > couple after. I was very surprised by the result as many were. > > > > There still is a lack of clear information about the event. For > > example, when Kim said that the computer plays at maybe 2 or 3 dan... > > > does he mean professional or amateur pro? The supercomputer itself is > > unclear... some had said it would be 3000+ cores... for the game they > > said 800 processors. Some said it was indeed 3000+ cores.. because > > each processor was 4 core. But I never found a clear answer on this. > > The records of discussion are in MogoTitan's sgf records.. but the > > discussions in the computer go room and perhaps private rooms are not > > recorded (at least that I know of). If someone did give this > > information, it was very easy to lose track of when 500 people were > > observing the match. Tonight I am probably going to go through the > > records to see if any more information can be gleaned. > > > > > One person who seemed to be in the room with Kim said that he was > > > laughing and clapping at some of the computer's moves. One person in > > > this list, but not the AGA eJournal, mentioned that Kim used about 11 > > minutes time.. where the computer used around 50. This was surprising > > to me... Kim is reported to say that he felt having extra time would > > > not have helped. To me... this seems a little odd. He may have used it > > > as a tactic to give the computer less thinking time (if Mogo was > > > indeed thinking during Kim's turn). He also might have done this to > > show that the computer is quite a bit weaker than him. I
Re: [computer-go] Re: mogo beats pro!
okay, thanks, david. s. On Fri, Aug 8, 2008 at 8:08 AM, David Fotland <[EMAIL PROTECTED]> wrote: > The supercomputer nodes did not have shared memory. Mogo uses shared memory > within a node, but between nodes it uses MPI message passing. The > supercomputer has low latency connections between nodes, and the Mogo team > has said that the strength scales better on systems with this kind of > interconnect than on clusters just using Ethernet. > > There is an issue with latency because the statistics in the important nodes > of the UCT tree are shared frequently. > > Sharing idle time on computers on the internet would be interesting for > postal games, but won't scale up in performance like Mogo on this > supercomputer. > > David > >> -Original Message- >> From: [EMAIL PROTECTED] [mailto:computer-go- >> [EMAIL PROTECTED] On Behalf Of steve uurtamo >> Sent: Friday, August 08, 2008 2:45 AM >> To: computer-go >> Subject: Re: [computer-go] Re: mogo beats pro! >> >> hm. this makes me think back to something. >> >> did this supercomputer have all of its ram shared >> by all processors? or could it be emulated by >> a large enough number of machines given individual >> jobs, given that combining the results of those jobs >> isn't too complicated? >> >> if so, i think that this would be ripe for BOINC -- at >> these time controls, there's no issue with latency, >> and there are clever ways to deal with people >> dropping off of the grid or giving intentionally bad >> information. >> >> and who wouldn't want to donate idle computer >> time to a project that was, say, sitting on KGS >> and kicking the crap out of decent players? >> >> lots of people sit on KGS and just simply watch. why >> not have those idle lurking watchers participate >> in the game as well, with their copious unused cycles? >> >> s. >> >> On Fri, Aug 8, 2008 at 2:12 AM, Darren Cook <[EMAIL PROTECTED]> wrote: >> >> Yes, MoGo gained much more from the longer time setting than Mr. Kim >> >> did. Note that Mr. Kim used very little of his time in the one-hour >> >> game. He said after the match that using more time would not have >> helped >> >> him. >> > >> > I imagine that is typical as white in a handicap game; you play >> solid, >> > good shape moves and wait for black to do something wrong. (I.e. >> strong >> > players can play a dozen simultaneous high-handicap games as easily >> as >> > they can play one high-handicap game.) >> > >> > Darren >> > >> > ___ >> > 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/ > > ___ > 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: mogo beats pro!
> not something he would necessarily do in a professional tournament. perhaps true. money is a great motivating force, even small amounts of money (as don has pointed out in the past). s. On Fri, Aug 8, 2008 at 7:57 AM, Robert Waite <[EMAIL PROTECTED]> wrote: > Yeah.. the misclick question is another fuzzy point. There was a lot of > debate in the actual game about what was happening... but there is the > difficulty of having weak players and strong players commenting. The only > person who really knew what was happening and the direction of play is Mr. > Kim. > > I hope that information becomes available as there are many stakeholders > hoping that the results of this game provide hope for a computer crushing > human opponents : ) > > I have a feeling that the devs are going to put out more information.. if > anyone here finds solid information in the coming weeks.. please post it > here so it is easier to find. > > What I would really hope for is someone who has a channel to Mr. Kim. This > event received some coverage in AGA eJournal and certainly some here.. but > to me this was a huge victory where the implications of the game did not > come out until the victory. I feel that if this had occured in Japan or > Korea... there would be general newspaper articles about the whole match... > and there would have been dedicated reporters at the event. It would be > really nice to have an interview with Mr. Kim to give stakeholders as much > information as possible. I am sure that the Mogo devs are getting feedback > from him... it would be nice for people in general to have Mr. Kim's take. > > The speed with which he played as well as the idea that he was laughing and > clapping would indicate that he perhaps was testing the game and did not > consider this a "Showdown". Perhaps he was very surprised with its strength > compared to other software he has played and was testing various aspects > with his play... not something he would necessarily do in a professional > tournament. This is all conjecture since we do not have a solid record yet > of what Mr. Kim thought. My feelings are that even if Kim gave it his all... > the overall result would have been the same: a computer got extremely strong > very quickly.. and this indicates that researchers are on the right track. > > I am sure he is busy.. and he may even give Korean interviews about what > happened... but if anyone finds information about Mr. Kims perspective of > the game... I think it would be of great interest to the computer go > community. > > ___ > 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: mogo beats pro!
hm. this makes me think back to something. did this supercomputer have all of its ram shared by all processors? or could it be emulated by a large enough number of machines given individual jobs, given that combining the results of those jobs isn't too complicated? if so, i think that this would be ripe for BOINC -- at these time controls, there's no issue with latency, and there are clever ways to deal with people dropping off of the grid or giving intentionally bad information. and who wouldn't want to donate idle computer time to a project that was, say, sitting on KGS and kicking the crap out of decent players? lots of people sit on KGS and just simply watch. why not have those idle lurking watchers participate in the game as well, with their copious unused cycles? s. On Fri, Aug 8, 2008 at 2:12 AM, Darren Cook <[EMAIL PROTECTED]> wrote: >> Yes, MoGo gained much more from the longer time setting than Mr. Kim >> did. Note that Mr. Kim used very little of his time in the one-hour >> game. He said after the match that using more time would not have helped >> him. > > I imagine that is typical as white in a handicap game; you play solid, > good shape moves and wait for black to do something wrong. (I.e. strong > players can play a dozen simultaneous high-handicap games as easily as > they can play one high-handicap game.) > > Darren > > ___ > 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] mogo beats pro!
> I still have this theory that when the level of the program is in the > high-dan reaches, it can take proper advantage of an opening book. Alas, it > may be a few years before enough processoring power is routinely available to > test this hypothesis. I know that we duffers can always ruin a perfectly good > joseki just as soon as we leave the memorized sequence. why would this be the case? and where would the book come from? my thinking is that unless mogo created the book itself, playing games like these, against opponents like these, at time controls like this one, then it couldn't possibly be helpful. and even then it might not be helpful. s. > > > - Original Message > From: Darren Cook <[EMAIL PROTECTED]> > >> I do have to ask -- if 1.7 million playouts per second and an hour of >> playing time are required to reach this level, ... > > Can Olivier give us more details. A few questions that come to mind: how > many playouts per *move* was it using in each of the opening, middle > game and endgame? Was it using a fuseki book, and how many moves did the > game stay in that book? And once it was out of the book was it all UCT > (*) search, or were there any joseki libraries, etc.? > > I'd also be interested to hear how inefficient the cluster was (e.g. > 1000 CPUs won't be doing 1000 times the number of playouts, there must > be some overhead). > > Darren > > *: Sorry, I've forgotten the new term we are supposed to use. > > > > ___ > 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] CGOS server boardsize
this would work best for a static board evaluator. a bot that retains state would likely be best served by using ram to retain state for a single game. s. On Fri, Aug 1, 2008 at 1:51 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > How about rotating board sizes? Each round changes the board size. > Just an idea. > > One time long ago I considered making a server where there were no time > controls. You just played at whatever pace you choose. The server > would try to keep your bot busy playing many different games > simultaneously. Whenever your move is complete, the server hands you a > new position to compute which likely would be from some other game. > > Slower bots of course play less games. Scheduling for this is an > interesting problem, especially if avoiding mismatches is a priority. > > - Don > > > > On Fri, 2008-08-01 at 13:09 -0700, Christoph Birk wrote: >> On Fri, 1 Aug 2008, [EMAIL PROTECTED] wrote: >> > Something that has worked well in other games would be to change the >> > third CGOS every month. Each month, the parameters would be announced >> > and the CGOS started empty except for the anchor(s). At the end of the >> > month, the bot at the top?would be?the winner. That would allow us to >> > experiment with novel settings like 11x11 boards or 20 seconds per game >> > that might be interesting for a short while but maybe not for long. It >> > can be a way of keeping things fresh and leveling the playing field a >> > little. >> >> It also would need a lot more maintenance ... >> IMHO there would not much to be learned from (eg) 11x11. >> I think of CGOS as a testing arena, not a monthly tournament >> to find the best program at some arbitrary setting. >> >> Christoph >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] re: What Do You Need Most?
i'm sure that we have 20 people here willing to kick in $20/year. s. On Wed, Jul 30, 2008 at 6:47 PM, Dave Dyer <[EMAIL PROTECTED]> wrote: > Boardspace is a VPS, so CGOS is currently running as a subaccount of a > VPS. Boardspace is going to be upgraded sometime in the next few > months, which will allow me to add another 1GB to CGOS allocation. > > Or, if computer Go gets a rich sugar daddy, spending $400/yr > for your own VPS would be an excellent first investment. > > -- > > ___ > 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] What Do You Need Most?
the $500K/year to hire an "expert team of programmers" to incorporate everyone's source code into an open-source framework is pretty wasteful. just let people dig through the code on their own. it'd be good enough, and save $500K/year. there's no real reason to give out the hardware, either, unless you want to encourage people to spend their time each year developing tinier and tinier high-powered wireless devices for cheating. all they need is access to an equivalent machine (say, ssh access) during the year to test and write speed optimizations. also, after this ran for a few years and started to get very competitive, it'd be difficult to convince people to give away their source code every year for the chance to win $100K/year. one reason is that commercial exploitation of their code would begin to be worth more as the strength improved significantly. another way to do all of this is to set aside a large chunk of money, let it accumulate interest, and have small milestones set each year that can pay prizes from a portion of that interest if they are met. this automatically ends up raising the value of the milestones over time. s. On Mon, Jul 28, 2008 at 4:24 AM, Mark Boon <[EMAIL PROTECTED]> wrote: > It's a question I have often contemplated. I don't think you can do > anything now that will greatly influence what the level in 2010 will > be. You have to think a little longer term. What it takes is fairly > simple, it takes a million bucks per year (roughly). Getting that > million bucks is not so simple, but if I had it to spend on > computer-Go, here's what I'd do: > > - Use a system like CGOS to create an online testing system / community. > - At some predetermined date the top n programs (say 16) get a > standard state-of-the-art PC to work on. > - Half a year later those 16 programs play an extensive tournament > using the standard hardware. > - Prize-money is $100K, $80K, $60K, $40K and $20K for the top five. > - All participants contribute their source-code to an open-source > project created for this event. > - The cost of organising the competition above is about $500K per > year, the other $500K is spent on hiring a team of expert programmers > who incorporate the contributions of the competing programs into an > open-source framework. > > This is sketchy and lacks some vital details, but you get the idea. > The main points are > a) Everybody starts from an equal base each year. > b) The PC used is a standardized piece of equipment. > c) The prize-money is enough to make people turn in their source-code. > Since coming in 2nd or 3rd isnt much less an achievement as coming in > 1st, the prize-money is also not much less. > > With a competition like this in place, I think the progress in a > decade will be astounding. > > Now we have to find a sugar-daddy who's willing to put in the $1M each year > :-) > >Mark > > On Sun, Jul 27, 2008 at 10:23 PM, Darren Cook <[EMAIL PROTECTED]> wrote: >> I have a strong interest in seeing a 19x19 computer go program that is >> at least 3-dan by 2010. The recent jump in strength on the 9x9 board has >> given me new hope and I want to ask people here, especially the authors >> of strong programs, what you now need to make the next jump in strength. >> There seem to be four broad categories: >> >> * More hardware (CPU cycles? Memory? Faster networking? Do you just >> need that hardware for offline tuning, or for playing too?) >> >> * More data >> >> * New algorithms (if so, to solve exactly what? evaluation? search? other?) >> >> * More community >> >> By community I mean things like this mailing list, CGOS, open source >> projects, etc. >> >> By data I mean things like: game records, or board positions, marked up >> with correct/incorrect moves; game records generally; pattern libraries; >> test suites; opening libraries. >> >> Darren >> >> -- >> Darren Cook, Software Researcher/Developer >> http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic >>open source dictionary/semantic network) >> http://dcook.org/work/ (About me and my work) >> http://darrendev.blogspot.com/ (blog on php, flash, i18n, linux, ...) >> ___ >> 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey <[EMAIL PROTECTED]> wrote:
> For a long time I have pondered whether you could build a very high quality
> random number generator that was extremely fast using the pentium RDTSC
> instruction as a low order bit entropy source. The idea would be to use
> an extremely fast (but low quality) pseudo random number generator, but
> modify the output (or the internal state of the generator) with the time
> stamp register at each call.
>
> RDTSC reads the pentiums internal clock and is basically just a 64 bit
> counter.However it increments very quickly and could be viewed as an
> entropy source in the lowest bits as it would introduce at least a little
> bit of non-determinism, and I think a little is all you would need to
> transform a horrible generator into a good practical one for many
> applications. I think the lowest 2 or 3 (or more) bits would appear to
> modern processors as almost unpredictable since there is so much going on
> inside modern computers that are unpredictable.
> I don't know if the call to RDTSC is fast or how it would affect the
> parallelism of todays modern machines. I'm not particularly interested in
> non-deterministic generators as I sometimes depend on this for testing and
> debugging, but it's an idea I thought I would throw out there.
> - Don
>
>
>
>
>
> Don Dailey wrote:
> > If you are looking for a cheap fast and simple random number generator, A
> post by George Marsaglia, an expert/guru on random number generation has
> several and a C implemention.
> >
> > These are one line generators, coded as macros.He also discusses the
> period and quality of each of them. This is a gem of a post on
> sci.stat.math,sci.math if you are interested in RNG:
> >
> > http://www.math.niu.edu/~rusin/known-math/99/RNG
> >
> > - Don
> >
> >
> >
> > Heikki Levanto wrote:
> >
> > >
> > > > In addition, xor_shift is better than builtin rand() and faster and
> > > > much smaller than MT.
> > > >
> > >
> > > I don't know that much about random numbers, so excuse my ignorance. But
> a
> > > bit of googling got me to the Park - Miller Minimal Standard random
> number
> > > generator
> http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
> > >
> > > >From what I read, it should be quite sufficient for go programs. It is
> > > dead simple and fast:
> > >
> > > long int pmrand() {
> > >const long int a=16807;
> > >const long int m= ( 1 << 31 ) -1;
> > >pmrandseed = ( pmrandseed * a ) % m ;
> > >return pmrandseed;
> > > } /* pmrand */
> > >
> > >
> > > Should I worry about this not being good enough?
> > > - Heikki
> > >
> > >
> > >
> > >
> > >
> > ___
> > 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/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to LeelaBot2 and to CzechBot
> Do you claim it's possible to avoid time losses by better coding? If so, > I'm very interested in what you have in mind. Measuring lag isn't the > answer: if your opponent is willing to play 2500 moves and you can make at > most 2 per second because of lag, then you will lose no matter what you do. in a tournament setting, you could always drop a binary of your code onto a local network with two machines for each game being played at any one time. i.e. reduce the lag to as near zero as possible by removing the network-wise distance between the binaries involved. this doesn't work in a kgs setting unless your machines are in the same machine room as the kgs machine, but it does work in other tournament settings. from the server's point of view, if i ask you what move you want to make, and it takes 0.5s for you to respond, it seems reasonable to me that since i (as the server) had to wait 0.5s for your response, i should remove 0.5s from your clock. now, if i know my lag to you (and this is easy enough for me to find out), and i can assume that your lag to me is the same (which isn't that terrible of an assumption, as simplified as it is), then i can add back double whatever my lag to you is to your clock after each move. i can do this calculation and measurement *independently* of you making moves, so if you suddenly start gaining lag, i'll notice, and likely i'll notice at a time different from (and prior to) when you are making a move. can you eat my pings and delay their responses? yes. but what kind of sociopath would do such a thing among programs none of which is better than a human on a big board? i.e. a much more obvious way to cheat would be to let a human play for the bot, yet nobody here worries much about that. also, if everyone involved were part of a private NTP network, the clocks would all agree, and if it were encrypted correctly, it'd be silly for anyone to bother hacking. then lag could be calculated quite exactly by the server. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A problem with selectivity and AMAF bias
magnus, I hate to ask the obvious, but how much time does each simulation take? If 100 simulations would be enough information to get it out of its rut, why not just check every legal move for (say) 100 simulations before doing anything else? on another note, i think that it's cool that you have a board situation that exhibits such borderline behavior (i.e. that it takes relatively few simulations to fix the problem, but that the code as it stood would never find the problem on its own). steve. On Fri, Apr 11, 2008 at 4:25 AM, Magnus Persson <[EMAIL PROTECTED]> wrote: > Quoting Michael Williams <[EMAIL PROTECTED]>: > > > > Magnus Persson wrote: > > > > > Yesterday I noticed an odd phenomena in Valkyria wich was caused by > high selectivity and AMAF. > > > > > > > > > > > > Then since there is nothing in the AMAF scores that indicate that move > 2 is any good it is never searched, since the search is so selective that > the bounds will not grow large to compensate for the bias in a reasonable > time. > > > > > > > > > Isn't this fixed by never straying from a move in the tree until it > > loses and then trying an untried move? > > Or something like that. It wasn't my idea and I don't remember the > > details, but it seems like it fixes what you describe. > > > > No, it does not because the AMAF score for move 2 is strictly lower than > the evaluation for move 1 and all other moves for some reason. It will try > other moves deeper in the tree instead and the position is sufficently > complex to generate a very large tree until it gives up on the move at the > root level. The thing is that if it searches move 2 for at least 100 > simulations it will discover it is a good move. But because of the AMAF > score is so low and all other moves are indeed losing moves it sticks to > move 1 because it at least makes it into a fight although at bad odds. > > Otherwise I am quite happy with the current implementation since it is > strong in testing, this only happens when there are two hot candidates and > the first one is searched first because of a limitation in move ordering, > and a particularly strong bias works against the second best. > > The annoying thing is that is can suddenly lose a game it was winning. > > But I found a better fix. I also tried to enter my pattern priorities as > the priors of the AMAF scores. And I now strongly believe that this is also > better in general and not for this particular situation. In the position I > wrote about yesterday this version get the right move almost immediately. I > tested as Valkyria 3.2.0 overnight on CGOS and it seems to be just as strong > as the previous version, and I can still tune the parameters of it. > > This means that the search of position will be guided in order by > > 1) My pattern priorities disguised as priors of AMAF scores. > 2) Then AMAF score will take over > 3) If a move is searched, then the true winrates for those moves will be > used and there is no bias from the pattern priorities except very weakly > from the AMAF scores. > > -Magnus > > > > -- > Magnus Persson > Berlin, Germany > > > ___ > 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] My experience with Linux
The difference (and I'm not defending HP here) is that a print scheduler for your OS shouldn't even be *writable* by the install "wizard" for your printer. Imagine an OS environment where a printer is a completely passive device that accepts requests to print onto paper. Imagine that it doesn't pong every device on the network, or every other printer on the network (remember appletalk?), and that there is no automatic "printer discovery". In my opinion, printer "discovery" should happen well before the time that the printer is installed. There's nothing to discover if you install the printer yourself. I didn't "discover" the printer attached to my PC when I plugged it in, I "discovered" it on the shelf of the store that I bought it from. If i'm a network administrator, I should be pretty much aware of when I plug a networked printer into the local network, and it seems to be a reasonable responsibility of mine to first make the decision about which machines should be able to print from it, and then to take the necessary steps to make that happen. Expecting an entire network of machines to do that job for me is not a particularly smart way to manage your network. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] now: operating systems and love, was: Paper for AAAI (David Silver) PDF problem
> That's the real problem with Windows. I need a double boot, place > the OS on a FAT32 partition and have a copy of every file + an > image of the installed partition. Every day I fight against the > operating system I have paid for and if the OS doesn't let me > change it the nice way I have to do it the hard way. If I was > starting now, I would be a Linux user. There's another way, and it's not too bad, depending upon how often you want to switch operating systems. Get a second drive. I have been burnt by windows more times than I care to have been (twice), so I decided to do the safest thing possible -- I don't even cross the streams. I just separate the OSes onto physically distinct drives, and in my case on different controller types, which makes it super-easy to switch between them. Yes, you can modify the boot loader on the main (windows) drive so that it recognizes the second drive, but I do something even less error-prone -- I just swap which drive is considered the boot drive in my BIOS at boot time. This takes about 2 seconds and does the obvious thing that I want -- if I'm spending weeks in FreeBSD, I don't have to do a thing until for some crazy reason I want to switch back to windows (usually to play a game of some kind, or to use some esoteric feature of my peripherals that nobody has bothered to reverse-engineer yet). Most windows-esque tasks are handleable in a modern unix system: abiword and openoffice do a reasonable job at emulating word and office, respectively (and openoffice is about as bloated a chunk of code as you might expect as a result) can read and save files from/into the relevant formats, and have about the same ease/unease of use. Gimp is a reasonable clone of photoshop, although if you're a serious designer you already have a mac and over $1200 worth of adobe software and are doing it the right way. There isn't, and this is actually a fortunate thing, yet any way to use unix without at some point needing to use a command-line tool. This is what will keep it out of the hands of consumers for a long time to come, but I think that it's an inherent fact of a secure operating system. Anything that runs in the same way that vmware runs is pretty cool, although I'm not aware of anything mature and free that does the same thing as well as it does (i'm sure that someone will correct me on this point.) If the company you work for will pay for it, just tell them that you need a copy to get work done. As of a few years ago, it was working really well (vmware, that is -- the tactic is timeless). The reason that NetBSD is so good is for a similar reason to the reason that you like Windows95. It is tiny. Extremely tiny. Moreso, it will run on just about any hardware that you can still get to power up. Unfortunately, it comes with just enough tools to *compile* everything that you need to use it. So it's a fantastic way to learn about unix, but not practical for people who want something that has, say, a beautiful looking window system with knobs to control everything about their operating system right out of the box (not having these things is a good thing in my mind, though). The reason that it isn't practical for most people is because you're going to need to compile that window system, and there will be a large and painfully recursive tree of dependencies that will need to be compiled first. If you enjoy this kind of one-time masochism in the pursuit of knowledge, then it's well worth your time. Linux is starting to be a good compromise for most folks, and ubuntu is pretty popular these days, but I still think that FreeBSD has the best compromise between features and kernel sanity for someone moderately comfortable with unix. I've seem windows users semi-easily switch to ubuntu without regret or too much of a learning curve, but they will eventually find something that doesn't work and/or is extremely difficult to do without using windows. It's just an issue of compromise -- people are so used to rebooting their broken operating systems that they've forgotten that it's not something that you're supposed to have to do! Unix boxes can brag about 10+ year uptimes, for crying out loud. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
NOW: OS wars, WAS: [computer-go] Paper for AAAI (David Silver) PDF problem
> But anyways, NetBSD is the best. yes, this is obviously true. on another (the original?) note, the relevant factor regarding being able to open a scientific paper on multiple platforms is that it be readable by as many people as possible -- even those people who run windows. OS belligerence is charming in its own way, but it's unrelated to whether or not the average person can access the equations in your work without booting into a particular operating system. the brand newest version of acrobat is working fine for me after uninstalling the older version. for what it's worth, there's anecdotal evidence that it was a change in the way that acrobat was dealing with certain fonts that they broke in one version (i think that they were adhering to some internal spec more stringently) and then fixed (probably because it caused lots of problems for people). or maybe it's not adobe's fault at all but something in windows. :) s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper for AAAI (David Silver) PDF problem
Hello, I'm getting the same thing here in windows: "Cannot extract the embedded font..." Was it made with pdflatex or somesuch? Could it be a version issue there? s. On Mon, Apr 7, 2008 at 6:48 AM, Jacques Basaldúa <[EMAIL PROTECTED]> wrote: > Hi David > > > http://www.cs.ualberta.ca/~silver/research/publications/files/MoGoNectar.pdf > > Your paper has a PDF problem concerning "embedded font BXGQFO+CMR12". I > have used > different versions of Adobe Reader. I even updated one of the computers to > the latest version > and I still cannot read any mathematical expressions. I guess this applies > to all Windows users. > > Jacques. > ___ > 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] Some ideas how to make strong heavy playouts
don, > But I also discovered that there seems to be no benefit whatsoever in > removing them from the play-outs.I have no real explanation for > this. But it does tell me that the play-outs are very different in > nature from the tree - you cannot just use the same algorithms for > selection and prioritizing moves. did you use the same heuristic in the playouts when pruning them? i.e. that no other stones are anywhere nearby? in any particular playout, they may be the killing move for a group that ends up getting built near to the edge of the board, or a successful monkey jump. so removing them from somewhere deep in the tree as a rule would be bad, but if nothing is anywhere nearby, removing them as a first move choice is pretty reasonable. they make up a fairly small fraction of possible moves, and this is magnified the deeper you go into a search (so the net effect would be diminished, even with the heuristic). anything you can say about what not to do on the very first move of a search, if it applies to every board situation (ha ha ha) is great, though, if it's fast enough to check for. in fact, if *nothing* is *anywhere* nearby, a move on even the second line is bad. third or fourth is much better. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 9x9
congratulations to mogo on its performance today! it was an excellent result (1-2) versus a professional, s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
> You have to have a nakade pattern on the > board somewhere, the score has to be close and in your favor > considering the nakade, and the program has to believe that it is more > advantageous to give away stones that not. eh, or it can't see the capture until it's only a few moves away, because its horizon with respect to self-atari is so shallow. deepen the horizon and it'll consider those moves early enough not to screw up its overall win percentage evaluation. > Although it's easy to see that nakade is a problem, I agree with > someone who said it takes a lot of skill to produce this.In fact, I > believe that it cannot be done reliably by any player unless he is > already much stronger than the program, in which case he doesn't "need" > to do it in order to beat the program. I wouldn't go this far -- humans learn from their mistakes, but can stay at the same skill level regardless of how much they learn, either because they forget things that they earlier learned, or because they have very shallow reading, say. for a computer, though, it's quite possible that every single player ranked one or two stones lower than (arbitrary mc program with this weakness -- AMCW) could exploit this weakness in a systematic way, more than 50% of the time. this would eventually reduce AMCW's ranking, of course, but wouldn't raise any of those player's rankings, because their ability to beat one specific player consistently isn't enough to modify their ranking. > (Indeed, it may be a > counterproductive strategy if it distracts you from playing good moves.) these aren't bad moves in any way. they're normal, healthy, strong go-player moves that are recognized instantly by anyone who has a read a copy of "life and death" or similar. > Most MC programs won't just let you pick off points because that is > normally a strategy that decreases your winning chances. They will > only do that if every move leads to the same win or loss in every single > play-out, or if the small win turns out to be easier to manage. or if they aren't reading out the playouts deeply enough that would allow them to correctly consider the impact of those moves early enough to avoid them! > I would love to see a 5kyu player get on KGS and beat mogo in more than > 1 out of 10 games using this specific strategy.My guess is that if > your energy is spent setting up this trick, you will play weaker in general. i dunno. imagine one of the "mate in 20" types of sequences that you're supposed to learn when you first learn chess. imagine that you never learn how to deal with them. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
yes, and the fact that turning a dumpling into a dead group can take more than a few moves, since you may have to fill up the eyespace several times, meaning going fairly deeply down branches with several self-ataris along the way. s. On Thu, Mar 6, 2008 at 9:23 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > > > > > > You won't find that in computer vs computer games, because "tricking" the > > strong programs requires some go skill and it only works if you wait long > > enough before you "solve" the position. But if you search KGS (LeelaBot, > > CrazyStone, CzechBot) for even games where the bot lost against a kyu > > players you will find many. All go more or less like that: > > > > A 4-6 kyu human is behind by 10-15 points in the midgame (at that > > stage the > > probability of winning is correlated with territory, so the MC bot is > > building fine.) He creates a 12-16 point worth nakade trick in a corner > > and does not solve it.The bot is happy, it thinks a bulk five is alive or > > something like that. Perhaps the human sacrificed another 15 points > > somewhere to create the trick so he should be dead lost. But, he only > > has to play on, reduce, etc. As the endgame approaches, the MC bot > > allows the reduction only until the territorial balance would change the > > winner. The player is happy, he turned a 25 points loss into a 1.5 point > > loss (assumed by the program) and has a 12 point surprise. > > At the end, when the whole board is decided, the player kills > > the bot's group and the bot turns a sure win into a sure loss and > > resigns. > > > > Because the trick can only be played by similar strength players (much > > weaker players can't build something like that, much stronger don't > > need it) > > it affects the rating of the bots. I guess CrazyStone could be near > > KGS 1dan > > with that solved. It is 2k now. But, of course, the solution may not > > come at > > the price of making the program weaker. That is the difficult part. > > I want to make sure I understand the nakade problem, please correct me > if I am wrong: > > My understanding of this is that many program do not allow self-atari > moves in the play-outs because in general the overwhelming majority are > stupid moves. Is that what is causing the nakade problem? And if > you start including self-atari you weaken the program in general? > > And can I assume the tree portion is also inhibited from seeing this due > to a combination of factors such as heuristics to delay exploring "ugly" > moves as well as the weakness of the play-outs in this regard (which > would cause the tree to not be inclined to get close enough to the issue > to understand it properly?) > > - Don > > > > > > > > > > > Jacques. > > ___ > > 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Floating komi
why doesn't someone simply try this and post the results, if they think that it would help? s. On Thu, Mar 6, 2008 at 8:30 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > Christoph Birk wrote: > > On Mar 5, 2008, at 11:58 AM, Don Dailey wrote: > >>> Don Dailey wrote: > not assuming that MC plays the best move. The problem isn't the > >> assumptions I am making, but the assumptions others are making, that > >> it's NOT playing the best move.You want to apply a fix to all > >> positions without really knowing which positions are a problem. > > > > One last time: Nobody suggested a one fix for all positions/problems. > > The "floating komi" was suggested to guide the UCT search along > > certain lines of play during specific (close!) endgame positions. > When I said all positions I meant all games.You expect to apply this > to all winning and losing positions in every game, not just specific ones. > > - Don > > > > > > > Christoph > > > > ___ > > 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Almost whole board seki
hey, that's great! s. On Wed, Mar 5, 2008 at 2:43 PM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > For those of you who enjoy uncommon positions, CGOS 9x9 game 322479 > offers a lot of seki. This is the final position: > > A B C D E F G H J > 9 . X X O . O . X . 9 > 8 X . X O O X X X X 8 > 7 O X X X O O O X O 7 > 6 O X X O X X O O O 6 > 5 O O X O X X X X O 5 > 4 O . O O O X . X O 4 > 3 . O O O O O X X . 3 > 2 O X X X O O O X X 2 > 1 . X . X X O O O O 1 > A B C D E F G H J > > Except for the small black group in the upper left the whole board is > seki. Amazingly white wins the game without a single independently > alive stone, in total one proper and two false eyes. Game record is > attached. > > /Gunnar > > > ___ > 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
cool. do you have any examples from a 19x19 game? that's what i was referring to when i said that i've never seen an MC player play out a ko fight. thanks, s. On Tue, Mar 4, 2008 at 9:35 AM, Magnus Persson <[EMAIL PROTECTED]> wrote: > Attached is an sgf-game of a long kofight on 9x9 between Valkyria and > Gnugo. Valkyria of course wins with 0.5 otherwise it would probably > not have been such a nice example of a long kofight. > > -Magnus > > > ___ > 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
ah, sorry to respond to my own post, but of course if the game is close, the threat doesn't even need to be of value > X, if it is large enough to threaten to win the game, which can happen in near-endgame situations. the idea is that you start a ko for something that your opponent is absolutely unwilling to give up (because it would lose the game), and for which you have no expectation of being able to win that fight, you can still either get small compensation (by making an unanswered tiny threat) or big compensation (by making a threat that if unanswered would lose the game). so simply having these threats lying around in the bank can be quite profitable if they're used correctly. games are sometimes resigned as soon as one player realizes that he doesn't have enough ko threats to win a ko fight, if it's for enough points. but as you mentioned earlier, sometimes MC players abandon the fight because something else looks more interesting. this is fairly rare behavior in human games, which is why i noticed it of these (MC) players. s. On Mon, Mar 3, 2008 at 12:37 PM, steve uurtamo <[EMAIL PROTECTED]> wrote: > the general idea is that if the ko represents something of value X, > then making threats of value > X will force your opponent to answer, > and if he does not have as many threats of value > X as you do, then > you can eventually win the ko fight (by filling the ko) and gain X-(value of > sente) points, or have a threat unanswered and gain (> X - X) points, > along with > possibly taking sente (which could be worth something near to X, but is > probably smaller). > > this is really relevant when X is large, or when there are multiple kos on > the board of varying values. > > important kos are often at a critical connection point for one or both > players, or at a critical eyespace (such as in the corner or along the edge) > > strong players can crush weaker players simply by starting kos in > important places because they know that they can win the ko or gain > points in compensation for starting a ko, since ko fights are generally > very hard for weaker players, who usually misjudge the value of ko > threats, remove ko threats early in the game for no good reason, or > have difficulty finding (or creating a sequence of!) reasonably-valued > ko threats. > > s. > > > > On Mon, Mar 3, 2008 at 8:49 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > > > > > > steve uurtamo wrote: > > >> So I don't think > > >> sophisticated ko fights are resolved but I not strong enough to really > > >> quantify this. > > >> > > > > > > It's very often the case that games between, say, two 7d players on KGS > > > will come down, in large part, to one or two or three ko fights and > their > > > resolution. or even the threat of a ko fight if one player is weak > enough. i'm > > > not sure that even the strongest amateurs count all of their ko threats > > > correctly ahead of playing them (the game is quite dynamic, after all) > but > > > this is way, way deeper water than i tread in, so i don't have any real > idea. > > > > > > i just wonder if anyone has tried to beat these programs by initiating a > > > complicated but critical ko fight. i'd think it'd be a can't-lose if > you chose > > > it correctly. i wonder if it's a repeatable way to beat these guys, or > if the > > > depth is handled just fine. > > > > > > the thing that got me thinking about this is that i've never seen an MC > > > player really play out a ko fight. (or perhaps they are in their own > cryptic > > > MC way that i can't see). > > > > > Perhaps I don't know what I'm talking about here, but is it possible > > that most ko fights can be avoided?Perhaps ko fights introduce too > > much uncertainty and they look for a more simple way to proceed? > > I've seen lot's of positions where there is a ko back and forth 2 or 3 > > times and the computer used every other turn to do something > > constructive in some particular area - then when it stopped fighting it > > stayed interested in that other area. I don't really know if what I > > saw meant anything - it involved only 1 ko point.Is that still > > considered a ko fight? It "seemed" to me to know what it was doing, > > picking (what seemed to me) just the right moment to abandon the ko. > > > > - Don > > > > > > > > > s. > > > ___ > > > 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/ > > > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
the general idea is that if the ko represents something of value X, then making threats of value > X will force your opponent to answer, and if he does not have as many threats of value > X as you do, then you can eventually win the ko fight (by filling the ko) and gain X-(value of sente) points, or have a threat unanswered and gain (> X - X) points, along with possibly taking sente (which could be worth something near to X, but is probably smaller). this is really relevant when X is large, or when there are multiple kos on the board of varying values. important kos are often at a critical connection point for one or both players, or at a critical eyespace (such as in the corner or along the edge) strong players can crush weaker players simply by starting kos in important places because they know that they can win the ko or gain points in compensation for starting a ko, since ko fights are generally very hard for weaker players, who usually misjudge the value of ko threats, remove ko threats early in the game for no good reason, or have difficulty finding (or creating a sequence of!) reasonably-valued ko threats. s. On Mon, Mar 3, 2008 at 8:49 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > > steve uurtamo wrote: > >> So I don't think > >> sophisticated ko fights are resolved but I not strong enough to really > >> quantify this. > >> > > > > It's very often the case that games between, say, two 7d players on KGS > > will come down, in large part, to one or two or three ko fights and their > > resolution. or even the threat of a ko fight if one player is weak > enough. i'm > > not sure that even the strongest amateurs count all of their ko threats > > correctly ahead of playing them (the game is quite dynamic, after all) but > > this is way, way deeper water than i tread in, so i don't have any real > idea. > > > > i just wonder if anyone has tried to beat these programs by initiating a > > complicated but critical ko fight. i'd think it'd be a can't-lose if you > chose > > it correctly. i wonder if it's a repeatable way to beat these guys, or if > the > > depth is handled just fine. > > > > the thing that got me thinking about this is that i've never seen an MC > > player really play out a ko fight. (or perhaps they are in their own > cryptic > > MC way that i can't see). > > > Perhaps I don't know what I'm talking about here, but is it possible > that most ko fights can be avoided?Perhaps ko fights introduce too > much uncertainty and they look for a more simple way to proceed? > I've seen lot's of positions where there is a ko back and forth 2 or 3 > times and the computer used every other turn to do something > constructive in some particular area - then when it stopped fighting it > stayed interested in that other area. I don't really know if what I > saw meant anything - it involved only 1 ko point.Is that still > considered a ko fight? It "seemed" to me to know what it was doing, > picking (what seemed to me) just the right moment to abandon the ko. > > - Don > > > > > s. > > ___ > > 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/ > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
> So I don't think > sophisticated ko fights are resolved but I not strong enough to really > quantify this. It's very often the case that games between, say, two 7d players on KGS will come down, in large part, to one or two or three ko fights and their resolution. or even the threat of a ko fight if one player is weak enough. i'm not sure that even the strongest amateurs count all of their ko threats correctly ahead of playing them (the game is quite dynamic, after all) but this is way, way deeper water than i tread in, so i don't have any real idea. i just wonder if anyone has tried to beat these programs by initiating a complicated but critical ko fight. i'd think it'd be a can't-lose if you chose it correctly. i wonder if it's a repeatable way to beat these guys, or if the depth is handled just fine. the thing that got me thinking about this is that i've never seen an MC player really play out a ko fight. (or perhaps they are in their own cryptic MC way that i can't see). s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
the issue with ko is the order in which the ko threats are played, which can only be successfully evaluated if the average playout finishes the ko correctly. s. On Sun, Mar 2, 2008 at 4:56 PM, ivan dubois <[EMAIL PROTECTED]> wrote: > Ok, I think I see what you mean, but I am not sure I really agree. > As you say, this is related to horizon effect. I think current MC programs > can play ko quite well because they are trying do delay the outcome of losing > the ko, therefore they tend to play threats do gain time, just like human > players do. I dont think it is essential that the ko be resolved inside the > tree part. And I dont believe there exist efficient way to handle ko in the > playout other than just fordiding simple ko recapture. > > Ivan > > - Message d'origine > De : Jonas Kahn <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Dimanche, 2 Mars 2008, 21h32mn 43s > Objet : Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?]) > > > But correct ko threats playing has nothing to do with the playout part : > Since it is a strategic concept that involves global understanting, It is > handled by the UCT tree part. > > Yes and no. > Theoretically, that's the work of the UCT part. But, as Steve pointed > out, kos can go on for long. I don't know what depth is attained in the > tree (by the way, I would really like to know), but I doubt it is that > long. Moreover, some kos must be kept for later. > > Hence, some basic understanding of kos in the playouts might be useful. > > That's merely a variation of the horizon effect. We could even imagine a > situation where the UCT makes a threat that loses points in the only aim > of having the ko past the horizon, where it would be 50-50 (for example) > in the playout. > > Jonas > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > _ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail > http://mail.yahoo.fr > ___ > 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: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
i'm just saying (and perhaps i'm misunderstanding something here) that lots of playout depth, and therefore lots of simulations are required to see *any* advantage to playing out a ko. s. On Sun, Mar 2, 2008 at 3:17 PM, ivan dubois <[EMAIL PROTECTED]> wrote: > Mogo is already very strong at endgame and certainly plays perfectly near the > end of the game. The more advanced the program, the sooner it can play > perfect endgame. > But correct ko threats playing has nothing to do with the playout part : > Since it is a strategic concept that involves global understanting, It is > handled by the UCT tree part. > > ----- Message d'origine > De : steve uurtamo <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Dimanche, 2 Mars 2008, 20h25mn 33s > Objet : Re: [computer-go] Re: Should 9x9 komi be 8.0 ?] > > a few subtleties -- > > it's possible for a machine to play a perfect endgame, and my > guess is that machines will play perfect endgames before people > do, although most pros are excellent at the endgame. > > counting ko threats and utilizing kos effectively is tricky in playouts -- > kos can naturally extend a playout very, very far beyond where the > actual advantage would be taken in a non-ko situation, and the likelihood > of getting this far often enough in playouts to see the advantage is going > to be difficult for machines without a lot of domain-specific knowledge. > > different humans are often good at different stages of the game, and > making up a few points in the endgame, or getting a massive lead in > the beginning of the game may be possible, convincing a computer > player of something that isn't true -- either that it's nearly guaranteed > to win, or nearly guaranteed to lose. > > all that having been said, i'm quite impressed with how well these programs > are doing. > > s. > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > _ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail > http://mail.yahoo.fr > ___ > 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: Should 9x9 komi be 8.0 ?]
a few subtleties -- it's possible for a machine to play a perfect endgame, and my guess is that machines will play perfect endgames before people do, although most pros are excellent at the endgame. counting ko threats and utilizing kos effectively is tricky in playouts -- kos can naturally extend a playout very, very far beyond where the actual advantage would be taken in a non-ko situation, and the likelihood of getting this far often enough in playouts to see the advantage is going to be difficult for machines without a lot of domain-specific knowledge. different humans are often good at different stages of the game, and making up a few points in the endgame, or getting a massive lead in the beginning of the game may be possible, convincing a computer player of something that isn't true -- either that it's nearly guaranteed to win, or nearly guaranteed to lose. all that having been said, i'm quite impressed with how well these programs are doing. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
