Re: [computer-go] Re: Drunken sailor on payday
one seemingly overlooked aspect of the whole speed vs. devel. time argument is that in order to actually *test* to see how strong your code is, you need to compete with it. once you do so, you will immediately see how cycles matter. i only know this because i've done some testing of various go engines, of different flavors, and having to calculate how to compensate for the cpu speed differences is nontrivial. compilation differences, cpu differences, cpu clock differences, etc. can all add up to actual, readily measurable differences in playing strength. i don't think that anyone is suggesting that they want to write some code that loses all of its games but is written in the uber-coolest way known to man. so let's imagine that you want to beat, say, a very weak opponent. you play against it and note that you're only winning 50% of your games. and it's an opponent that plays random moves. you note that given the time constraints, the problem is simply that you aren't able to evaluate enough positions quickly enough, so you make it 10% faster and it starts winning 75% of its games. voila! in my experience, this is actually what actually happens. eventually speed increases don't help as much and you need to come up with some other cool trick. but regardless of how you implement it, at some point you're going to want to test it against other players. and because it's a new trick that will make your code better, it'll eventually benefit from more cycles as well. unless, of course, you have an algorithm that is strong and somehow *independent of the clock available to the algorithm*. that sounds more like a proof than an algorithm to me, and i think that'd be very interesting. s. Get easy, one-click access to your favorites. Make Yahoo! your homepage. http://www.yahoo.com/r/hs ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Drunken sailor on payday
Dave Dyer wrote: I think that's somewhat contrived as well. I don't have that good idea about all the populat computer go algorithsm, do you have example of reasonably performing algorithm with these properties? A standard alpha-beta driven search takes exponentially more time with search depth, so an exponential increase in speed results in a very small incremental improvement in seeing'. Improvements in the quality of the evaluation at anything less than exponential cost more effective at improving playing strength. What do you expect to see?A non-exponential technique that leads to arbitrary playing strength? A good alpha/beta searcher does not replace smarts in a program, it supplements it.It would have to have some kind of reading at end nodes and dead stone analysis. It's a non-trivial problem - but it has nothing to do with alpha/beta. You never specifically answered Petr either. You attacked alpha/beta and never presented an alternative. One last important point. It's not a bad thing that Go is exponential. It's exponential in Chess too but it doesn't follow that this makes it infeasible. Otherwise it would be infeasible for Chess too. - 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: Drunken sailor on payday
Dave Dyer wrote: A standard alpha-beta driven search takes exponentially more time with search depth, so an exponential increase in speed results in a very small incremental improvement in seeing'. Improvements in the quality of the evaluation at anything less than exponential cost more effective at improving playing strength. What do you expect to see?A non-exponential technique that leads to arbitrary playing strength? My point is only that time spent trying to make alpha-beta as fast as possible is basically time wasted. It doesn't matter if that time is spent assembling faster hardware, coding in languages with better runtime performance, or just plain hand coding to optimize. Faster alpha-beta will never be a significant contributor to improved playing strength. I think you are like the drunken sailor, no disrespect intended. It appears that a doubling is worth about 100 ELO points in 19x19 GO. That means a speedup of even 1.4 is worth 50 ELO points.50 ELO means you will beat me about 57% of the time. If you are drunken sailor, you probably don't care that much - hardware will catch up in just a few months.So you might as well take this shortcut and avoid C. You also might as well not optimize - it makes your code ugly.It's probably only worth another 50 ELO points anyway. If your mentality is that you are only interested in the big wins, you are not respecting the little things that over time add up to big wins.It means you probably don't care about making your program slightly smarter either. You are going down the wrong path. Eventually, you become bankrupt and have a crummy program and don't know why. Of course I came from computer chess. I spend a month optimizing a very old chess program I wrote with my partner. I found some kind of speedup every day for a good while (I don't remember the time period exactly, but it was perhaps a month or so.)Most of them were very modest - and to make ourselves respect the process we didn't veiw them as speedups, but instead converted them to ELO rating points gained. We knew that 5 ELO is hard to measure in terms of actual results, but getting 5 ELO a few days in row turned our program from a modest program to a champion program. This program won a championship. There are a bunch of other issues too like bugs. It's important to have few bugs. They kill your program too. That is one argument in favor of using a high level language, but it's a dear price to pay. - Don Choosing C because it executes faster is silly. Choosing C because you can start with GNUGo might be perfectly sensible. ___ 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: Drunken sailor on payday
Don Dailey wrote: Dave Dyer wrote: A standard alpha-beta driven search takes exponentially more time with search depth, so an exponential increase in speed results in a very small incremental improvement in seeing'. Improvements in the quality of the evaluation at anything less than exponential cost more effective at improving playing strength. What do you expect to see?A non-exponential technique that leads to arbitrary playing strength? My point is only that time spent trying to make alpha-beta as fast as possible is basically time wasted. It doesn't matter if that time is spent assembling faster hardware, coding in languages with better runtime performance, or just plain hand coding to optimize. Faster alpha-beta will never be a significant contributor to improved playing strength. I forgot to mention that UCT and alpha beta seem to have about the same behavior - about 100 ELO per doubling in GO at 19x19. Also there are reasonable alpha/beta GO programs such as AYA. It's not even clear to me what the best search method is. Right now it seems to be some version of Monte Carlo with best first search. But a lot of things are being tried and I think some people are trying alpha/beta and getting good results. Of course alpha/beta doesn't imply brute force. An alpha beta search can be quite selective. It doesn't have to end with a stupid evaluation function either - it can try to be smart. - Don I think you are like the drunken sailor, no disrespect intended. It appears that a doubling is worth about 100 ELO points in 19x19 GO. That means a speedup of even 1.4 is worth 50 ELO points.50 ELO means you will beat me about 57% of the time. If you are drunken sailor, you probably don't care that much - hardware will catch up in just a few months.So you might as well take this shortcut and avoid C. You also might as well not optimize - it makes your code ugly.It's probably only worth another 50 ELO points anyway. If your mentality is that you are only interested in the big wins, you are not respecting the little things that over time add up to big wins.It means you probably don't care about making your program slightly smarter either. You are going down the wrong path. Eventually, you become bankrupt and have a crummy program and don't know why. Of course I came from computer chess. I spend a month optimizing a very old chess program I wrote with my partner. I found some kind of speedup every day for a good while (I don't remember the time period exactly, but it was perhaps a month or so.)Most of them were very modest - and to make ourselves respect the process we didn't veiw them as speedups, but instead converted them to ELO rating points gained. We knew that 5 ELO is hard to measure in terms of actual results, but getting 5 ELO a few days in row turned our program from a modest program to a champion program. This program won a championship. There are a bunch of other issues too like bugs. It's important to have few bugs. They kill your program too. That is one argument in favor of using a high level language, but it's a dear price to pay. - Don Choosing C because it executes faster is silly. Choosing C because you can start with GNUGo might be perfectly sensible. ___ 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/