Re: [Computer-go] Computer-aided Go on High-dan Level
Now I found a youtube video, showing the whole exhibition game CrazyManja vs Guo Juan: https://www.youtube.com/watch?v=rrvadZJIveA It includes also the analysis session, starting at 2h:12min. Ingo. Gesendet: Dienstag, 11. August 2015 um 17:22 Uhr Von: Ingo Althöfer 3-hirn-ver...@gmx.de An: computer-go@computer-go.org Betreff: Re: [Computer-go] Computer-aided Go on High-dan Level In the congress there was also an exhibition game between team CrazyManja and professional Guo Juan (5p). Guo gave three handicap stones and won convincingly. Here is a photo, where Guo takes a photo of Manja. http://www.dgob.de/yabbse/index.php?action=dlattach;topic=5753.0;attach=4231;image On the left side you can see the monitor with CrazyStone's analysis mode. Manja had this information available when selecting her move. Ingo. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] How to handle triple ko efficiently?
I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] How to handle triple ko efficiently?
Yes, but to 'remember' the prior board state, doesn't the program have to store the whole board position per every turn by whatever means including Zobrist hashing that you suggested? After that, the program has to search whether the current position matches any of the previous ones. You said 3 is enough for triple kos, but as far as I know aren't there some rare repeating positions with a cycle longer than 3? But anyway solving the problem this way seems too expensive to me. 2015. 8. 31. 오전 9:59에 Jason House jason.james.ho...@gmail.com님이 작성: Triple ko can be detected by remembering the prior three board states. A zorbist hash value should be good enough to detect a repeat. On Aug 30, 2015 8:46 PM, Minjae Kim xive...@gmail.com wrote: I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] How to handle triple ko efficiently?
To my understanding, you need a sufficiently large bitstring to minimize possible hash collisions when using Zobrist hashing. When a hash collision does occur, it can possibly generate an illegal move. What is an acceptable size of the hash bitstring for a 19x19 board? On Mon, Aug 31, 2015 at 10:52 AM, Jason House jason.james.ho...@gmail.com wrote: There are longer cycles that can occur but I have never encountered any that didn't naturally resolve themselves in the playout. Zobrist having is cheap to compute (one xor if no stones were captured). Comparing the resulting number against the others is also cheap. The hash is also helpful for handling transpositions in the search tree. https://en.m.wikipedia.org/wiki/Zobrist_hashing On Aug 30, 2015 9:17 PM, Minjae Kim xive...@gmail.com wrote: Yes, but to 'remember' the prior board state, doesn't the program have to store the whole board position per every turn by whatever means including Zobrist hashing that you suggested? After that, the program has to search whether the current position matches any of the previous ones. You said 3 is enough for triple kos, but as far as I know aren't there some rare repeating positions with a cycle longer than 3? But anyway solving the problem this way seems too expensive to me. 2015. 8. 31. 오전 9:59에 Jason House jason.james.ho...@gmail.com님이 작성: Triple ko can be detected by remembering the prior three board states. A zorbist hash value should be good enough to detect a repeat. On Aug 30, 2015 8:46 PM, Minjae Kim xive...@gmail.com wrote: I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] How to handle triple ko efficiently?
64 bits seems to be enough. As I understand it, the convention is to simply *ignore* the possibility of collisions; you're more likely to have a hardware error. On Sun, Aug 30, 2015 at 8:27 PM, Minjae Kim xive...@gmail.com wrote: To my understanding, you need a sufficiently large bitstring to minimize possible hash collisions when using Zobrist hashing. When a hash collision does occur, it can possibly generate an illegal move. What is an acceptable size of the hash bitstring for a 19x19 board? On Mon, Aug 31, 2015 at 10:52 AM, Jason House jason.james.ho...@gmail.com wrote: There are longer cycles that can occur but I have never encountered any that didn't naturally resolve themselves in the playout. Zobrist having is cheap to compute (one xor if no stones were captured). Comparing the resulting number against the others is also cheap. The hash is also helpful for handling transpositions in the search tree. https://en.m.wikipedia.org/wiki/Zobrist_hashing On Aug 30, 2015 9:17 PM, Minjae Kim xive...@gmail.com wrote: Yes, but to 'remember' the prior board state, doesn't the program have to store the whole board position per every turn by whatever means including Zobrist hashing that you suggested? After that, the program has to search whether the current position matches any of the previous ones. You said 3 is enough for triple kos, but as far as I know aren't there some rare repeating positions with a cycle longer than 3? But anyway solving the problem this way seems too expensive to me. 2015. 8. 31. 오전 9:59에 Jason House jason.james.ho...@gmail.com님이 작성: Triple ko can be detected by remembering the prior three board states. A zorbist hash value should be good enough to detect a repeat. On Aug 30, 2015 8:46 PM, Minjae Kim xive...@gmail.com wrote: I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go -- Peter Drake https://sites.google.com/a/lclark.edu/drake/ ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] How to handle triple ko efficiently?
Triple ko can be detected by remembering the prior three board states. A zorbist hash value should be good enough to detect a repeat. On Aug 30, 2015 8:46 PM, Minjae Kim xive...@gmail.com wrote: I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] How to handle triple ko efficiently?
There are longer cycles that can occur but I have never encountered any that didn't naturally resolve themselves in the playout. Zobrist having is cheap to compute (one xor if no stones were captured). Comparing the resulting number against the others is also cheap. The hash is also helpful for handling transpositions in the search tree. https://en.m.wikipedia.org/wiki/Zobrist_hashing On Aug 30, 2015 9:17 PM, Minjae Kim xive...@gmail.com wrote: Yes, but to 'remember' the prior board state, doesn't the program have to store the whole board position per every turn by whatever means including Zobrist hashing that you suggested? After that, the program has to search whether the current position matches any of the previous ones. You said 3 is enough for triple kos, but as far as I know aren't there some rare repeating positions with a cycle longer than 3? But anyway solving the problem this way seems too expensive to me. 2015. 8. 31. 오전 9:59에 Jason House jason.james.ho...@gmail.com님이 작성: Triple ko can be detected by remembering the prior three board states. A zorbist hash value should be good enough to detect a repeat. On Aug 30, 2015 8:46 PM, Minjae Kim xive...@gmail.com wrote: I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] How to handle triple ko efficiently?
Is 64 bits really enough? I may be wrong but there are 3^361 possible board positions in 19x19. log2(3^361) gives me 572.171..., which means I need at least 573 bits to record all possible board positions. This still doesn't mean that a 2048 bit Zobrist hash for example will never collide for a 19x19 board, but the odds will be significantly lesser. Do you have some source about the probability of Zobrist hash collision on a go board for different bit string sizes? On Mon, Aug 31, 2015 at 12:37 PM, Peter Drake dr...@lclark.edu wrote: 64 bits seems to be enough. As I understand it, the convention is to simply *ignore* the possibility of collisions; you're more likely to have a hardware error. On Sun, Aug 30, 2015 at 8:27 PM, Minjae Kim xive...@gmail.com wrote: To my understanding, you need a sufficiently large bitstring to minimize possible hash collisions when using Zobrist hashing. When a hash collision does occur, it can possibly generate an illegal move. What is an acceptable size of the hash bitstring for a 19x19 board? On Mon, Aug 31, 2015 at 10:52 AM, Jason House jason.james.ho...@gmail.com wrote: There are longer cycles that can occur but I have never encountered any that didn't naturally resolve themselves in the playout. Zobrist having is cheap to compute (one xor if no stones were captured). Comparing the resulting number against the others is also cheap. The hash is also helpful for handling transpositions in the search tree. https://en.m.wikipedia.org/wiki/Zobrist_hashing On Aug 30, 2015 9:17 PM, Minjae Kim xive...@gmail.com wrote: Yes, but to 'remember' the prior board state, doesn't the program have to store the whole board position per every turn by whatever means including Zobrist hashing that you suggested? After that, the program has to search whether the current position matches any of the previous ones. You said 3 is enough for triple kos, but as far as I know aren't there some rare repeating positions with a cycle longer than 3? But anyway solving the problem this way seems too expensive to me. 2015. 8. 31. 오전 9:59에 Jason House jason.james.ho...@gmail.com님이 작성: Triple ko can be detected by remembering the prior three board states. A zorbist hash value should be good enough to detect a repeat. On Aug 30, 2015 8:46 PM, Minjae Kim xive...@gmail.com wrote: I finally managed to build a program that can produce a sequence of random legal go moves. One problem I found recently is that it rarely never ends a game because of triple ko, especially on small boards. One possible solution would be saving every board position that has occurred and searching for a match before generating a move. But this doesn't sound like an efficient solution at all. How do you handle this problem? Also as a side question, white constantly seems to have a better winning rate in any board size larger than 9x9 with komi greater than 6 under area scoring in completely random games; is this natural? ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go -- Peter Drake https://sites.google.com/a/lclark.edu/drake/ ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
