Re: [computer-go] How to improve my minimax speed?
This is the problem with Go. "Branching factor". 9x9=81, 81 x 80 x 79 = 511920 positions to check. You should try to search for "more likely" moves. Ex: A1 is definetely not a first move. Any move at first row/column will not be a good move, at least for the first 5 or 6 moves. So, just to ilustate: lets exclude the first row/column in the firsts moves. 7x7 = 49 49 x 48 x 47 = 110544 moves to check. That means: 79% improvement ONLY removing first row/column. As a rule of thumb: avoid optimizing functions like floodfill in the beginning. You should focus on algorithm speed but at logical level. ( calc of function O() ) .. sorry i don't know how is that called in english. Perhaps someone could help. The problem is that you are looking at a lot of positions, and how that grows on each move deep you add to the search. On every player move, you are multiplying by 81 the time spend so far, try to lower that number, the "branching factor". Eduardo --- Wodzu <[EMAIL PROTECTED]> escribió: > Greetings guys. > > Ive implemented standard minimax algorithm but is so > enormous slow even on > 9x9 board. For example when depth = 3 (player1 move, > player2 move, player1 > move) computing time at the begining is like 1 > minute. > I know that I should implement alpha-beta pruning > variation to speed up it > but what else can I do? > I am eveluating position by using floodfill metod so > for every single > evaluaton i need to copy entire board. Ive heard > that there is a > possibility to store the board and not using > floodfill to often by > remembering what has changed and to just undo such > changes but i cant > figure it out by myself. Any faster way than > floodfill to check the teritory > and catched stones? > Thanks for any tips, > > Regards. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Maximum number of strings
On 11/13/06, Chrilly <[EMAIL PROTECTED]> wrote: There is of course the question how sure this number is. Is it some sort of proove or just an example the author has found? A simple upper bound can be calculated by number_of_intersections*4/5, which gives 288 for the 19x19 board. Each empty intersection can be adjacent to at most 4 strings and all strings need at least one liberty. To maximize the number of strings they should all have the minimal size of 1 (larger strings can always be shrunk to one without affecting the string count). So for every 5 intersections we will have at best one liberty and 4 strings. If you take the edge into account this number will go down a bit, but apparently not enough to fit in 8 bits :-( Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve my minimax speed?
Start with the "low hanging fruit".You haven't implemented alpha-beta pruning yet, but you should, that is an enormous speedup. After implementing alpha beta pruning you should spend a lot of time on move ordering - doing a lot of experiments to see what is best as this will give you additional enormous speedups. But even with random move ordering, alpha beta pruning is an enormous speedup and it's absolutely free - no degradation in move quality. With excellent move ordering it can speed-up up many times faster yet. - Don On Mon, 2006-11-13 at 01:20 +0100, Wodzu wrote: > Greetings guys. > > Ive implemented standard minimax algorithm but is so enormous slow even on > 9x9 board. For example when depth = 3 (player1 move, player2 move, player1 > move) computing time at the begining is like 1 minute. > I know that I should implement alpha-beta pruning variation to speed up it > but what else can I do? > I am eveluating position by using floodfill metod so for every single > evaluaton i need to copy entire board. Ive heard that there is a > possibility to store the board and not using floodfill to often by > remembering what has changed and to just undo such changes but i cant > figure it out by myself. Any faster way than floodfill to check the teritory > and catched stones? > Thanks for any tips, > > Regards. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve my minimax speed?
But... Which evaluation function for alfa-beta pruning? Perhaps I'm missing something, but alfa-beta pruning implies not perfect solution at all, because evaluation function is not perfect. --- Don Dailey <[EMAIL PROTECTED]> escribió: > Start with the "low hanging fruit".You haven't > implemented > alpha-beta pruning yet, but you should, that is an > enormous speedup. > After implementing alpha beta pruning you should > spend a lot of time on > move ordering - doing a lot of experiments to see > what is best as this > will give you additional enormous speedups. > > But even with random move ordering, alpha beta > pruning is an enormous > speedup and it's absolutely free - no degradation in > move quality. With > excellent move ordering it can speed-up up many > times faster yet. > > - Don > > > On Mon, 2006-11-13 at 01:20 +0100, Wodzu wrote: > > Greetings guys. > > > > Ive implemented standard minimax algorithm but is > so enormous slow even on > > 9x9 board. For example when depth = 3 (player1 > move, player2 move, player1 > > move) computing time at the begining is like 1 > minute. > > I know that I should implement alpha-beta pruning > variation to speed up it > > but what else can I do? > > I am eveluating position by using floodfill metod > so for every single > > evaluaton i need to copy entire board. Ive heard > that there is a > > possibility to store the board and not using > floodfill to often by > > remembering what has changed and to just undo such > changes but i cant > > figure it out by myself. Any faster way than > floodfill to check the teritory > > and catched stones? > > Thanks for any tips, > > > > Regards. > > > > ___ > > 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/ > __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve my minimax speed?
In message <[EMAIL PROTECTED]>, Eduardo Sabbatella <[EMAIL PROTECTED]> writes But... Which evaluation function for alfa-beta pruning? The same evaluation function that you are using already. Your original posting refers to "branching factor". If you are concerned about branching factor, you are, presumably, using a tree search, with an evaluation function. However you are doing this, so long as you are searching at least two plies deep, it will run significantly faster with alpha-beta pruning than without it. Perhaps I'm missing something, but alfa-beta pruning implies not perfect solution at all, because evaluation function is not perfect. Alpha-beta pruning will not replace your evaluation function by a perfect one :-) It will reduce the number of nodes that you need to evaluate. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve my minimax speed?
> If you are concerned about branching factor, Nop, I'm not. Was another person, I just tried to explain what is branching factor. Something good about alfa-beta, search-trees that you pointed out: Using alfa-beta pruning allows you to see more 'deep' in the game tree. We could say: You exchanges "tree wide view" for "tree deep view". Its not soo difficult to miss "the" move, prunning the tree. my 2 cents. __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve my minimax speed?
On Monday, November 13, 2006, at 04:02 PM, Eduardo Sabbatella wrote: Using alfa-beta pruning allows you to see more 'deep' in the game tree. We could say: You exchanges "tree wide view" for "tree deep view". Its not soo difficult to miss "the" move, prunning the tree. Alpha-beta pruning is "safe", in the sense that it will find the same move as a full minimax search. You need to do "aggressive forward pruning" in order to run the risk of missing "the" move, but alpha-beta is conservative not aggressive. You may indeed 'miss "the" move', but when you do, minimax would do so too. Arthur ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve my minimax speed?
You can reduce this far more by using symmetry arguments: if you are willing to eliminate only the edge moves from first level considerations, then there are only 10 moves, six if you are also willing to eliminate the second row, because of the 8-fold symmetry. While this advantage drops quickly as the board fills with complicated patterns that break symmetry, there are always the 8 boards that are instantly solved by the info gained in doing the first ... but that is of little value if there is no DB of previously searched patterns. O O X OOOXX OOXXX O O Cheers, David On 13, Nov 2006, at 1:29 AM, Eduardo Sabbatella wrote: This is the problem with Go. "Branching factor". 9x9=81, 81 x 80 x 79 = 511920 positions to check. You should try to search for "more likely" moves. Ex: A1 is definetely not a first move. Any move at first row/column will not be a good move, at least for the first 5 or 6 moves. So, just to ilustate: lets exclude the first row/column in the firsts moves. 7x7 = 49 49 x 48 x 47 = 110544 moves to check. That means: 79% improvement ONLY removing first row/column. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Maximum number of strings
> This is a practically important figure. I have severall fixed > data-structures which depend on the maximum number of strings. I put it to > 300, because I was not sure. So I can save a few entries in the future. > There is of course the question how sure this number is. Is it some sort of > proove or just an example the author has found? This is an sample of maximum. He shows there is at least one checker-board-design position in all N strings positions. OXOXOXO XOXOXOX checker-board-design position OXOXOXO XOXOXOX take some stones from this position. OXOXOXO And he gives forbidden pattern. 010110100forbidden pattern 111100110 010000100"1" is stone. "0" is empty. center corner edge Then he used GLPK(GNU Linear Programming Kit) and got the result up to 15x15. MSP( 2) = 2 MSP( 3) = 6 MSP( 4) = 12 MSP( 5) = 18 MSP( 6) = 26 MSP( 7) = 36 MSP( 8) = 49 MSP( 9) = 61 MSP(10) = 76 MSP(11) = 92 MSP(12) = 109 MSP(13) = 129 MSP(14) = 149 MSP(15) = 172 ... MSP(19) = 277 MSP(19) means "Max Strings Problem in 19x19". Author could not solve 19x19, just showed 277 <= MSP(19) <= 281. But Ryuhei Miyashiro reported he got the result MSP(19) was 277 by using CPLEX(commercial solver) for 40days calculations. Hiroshi Yamashita ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Maximum number of strings
Author could not solve 19x19, just showed 277 <= MSP(19) <= 281. But Ryuhei Miyashiro reported he got the result MSP(19) was 277 by using CPLEX(commercial solver) for 40days calculations. Hiroshi Yamashita Thanks for the info. I will set it to 278 and if once Suzie crashes due to an overflow I will blame you :-). Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
