Re: [computer-go] rotate board
With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. Arthur On Dec 20, 2007, at 10:49 AM, Jacques Basaldúa wrote: snip The idea is that any of the board the can be transformed by mirror rot from a given board will produce the same set 8 hashes, just in a different order. Because the hashes are (with high probability) unique, one hash represents a board and the canonical hash represents the class of 8 boards produced by mirror/rot. It is true: Another board in the class - same set of 8 hashes - same canonical hash. It is almost certain (prob = 1/2^64 per check): A different board - a different set of 8 hashes - different canonical hash. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED] wrote: On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If you are going to compute all 8 hash keys, you can just add them up at the end instead of picking the minimum. Wouldn't that be better? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
That was my first thought too - actually my 2nd, my 1st was (8*8/2)/(2^64) - but I reason, one particular choice of position A's 8 must match one particular choice of position B's, rather than any one of A's matching the particular one of B's. But since the choosing is biased, the chance of collision is somewhat increased. Arthur - Original Message - From: Jason House [EMAIL PROTECTED] Date: Thursday, December 20, 2007 3:20 pm Subject: Re: [computer-go] rotate board To: computer-go computer-go@computer-go.org On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If hash collisions are worrisome, you can always use 96-bit or 128-bit hashes. Modern x86s can do 8 parallel loads, adds, subtracts, or stores of 16-bit numbers in one step using SIMD, just like Antti Huima suggests in http://fragrieu.free.fr/zobrist.pdf. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
I think that would be worse. There are lots of sets of 8 numbers that sum the same, far more than there are sets of 8 with the same minimum element. Arthur - Original Message - From: Álvaro Begué [EMAIL PROTECTED] Date: Thursday, December 20, 2007 4:08 pm Subject: Re: [computer-go] rotate board To: computer-go computer-go@computer-go.org On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED] wrote: On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If you are going to compute all 8 hash keys, you can just add them up at the end instead of picking the minimum. Wouldn't that be better? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
As Gunnar pointed out, you may not need the canonical hash at all. I think you only need to compute the canonical hash if you are matching to some game-external hash, such as a fuseki or pattern library. If you are just using it for transposition and super-ko checking, no board rotation will have occurred. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 20, 2007 11:23 AM, Arthur W Cater [EMAIL PROTECTED] wrote:
I think that would be worse. There are lots of sets of 8 numbers that sum
the same,
far more than there are sets of 8 with the same minimum element.
Arthur
- Original Message -
From: Álvaro Begué [EMAIL PROTECTED]
Date: Thursday, December 20, 2007 4:08 pm
Subject: Re: [computer-go] rotate board
To: computer-go computer-go@computer-go.org
On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED]
wrote:
On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote:
With 8 hashes per position, the chance of two different boards
producing a different set of hashes but
the same canonical hash is greater than 1/2^64, because there
will be
a bias in the choice of canonical
hashes - toward numerically lower numbers, for instance.
I think.
More importantly, how does it differ from 8/2^64 = 1/2^61?
If you are going to compute all 8 hash keys, you can just add them
up at the
end instead of picking the minimum. Wouldn't that be better?
That can't possibly be true... Think about it. Sums of random numbers are
uniformly distributed (remember we are working in the ring of integers
modulo 2^64), while the minimum is very biased towards small numbers.
These two Unix commands show the number of different sums and the number of
different minimums among 10,000 sets of 8 random integers. I did it with 16
bits instead of 64:
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x (1..1){$s=0;for
$y (1..8){$s+=int(rand(65536));}print .($s%65536).\n;}' | sort -u | wc
-l
9294
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..1){$s=999;for $y (1..8){$t=int(rand(65536)); $s=$t if
$t$s;}print $s\n;}' | sort -u | wc -l
7476
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] ELO Ratings of move pattern
On Dec 5, 2007 4:44 AM, Lars [EMAIL PROTECTED] wrote: I have some questions concernig this paper of Remi: http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf @Remi: How many iterations you had used? Anyone of you have similar or other experiences with the algorithm? I seem to have more time to think than to code lately. I believe I've derived an alternate update method. I'd be curious how quickly it converges. Using Minorization-Maximization, Remi derived new gamma = wins/sum(C/E) Using Newton-Raphson method, I derived fractional change = (estimation error) * (fractional uncertainty)^2 new gamma = gamma * (1 + fractional change) Where estimation error = (wins-expected wins) fractional uncertainty = sigma/gamma fractional change = new gamma/gamma - 1 Changing gamma based on both the estimation error and the uncertainty that gamma is correct makes intuitive sense to me. Sigma matches remi's definition. Because strengths are multiplied together, fractional uncertainty makes more sense. I'm avoiding the difficult issue of explaining why, but I do point people to consider two things: 1. If gamma=gamma+sigma, what does that do to team strength? (It multiplies the team strength by 1 + fractional uncertainty) 2. Look at the similar definitions of fractional uncertainty and fractional change. A less intuitive form is: fractional change = (wins-expected wins) / (expected wins^2 - wins) Using Remi's notation, expected wins = gamma*sum(C/E) Regardless of if someone else plays with the alternate equation, I'll be playing with both after the holidays. I'd also be curious what thoughts people have about this. To derive this, I applied the Newton-Raphson method to find where the partial derivative of the log-evidence is zero (AKA, where log-evidence is maximized). If L = log evidence, and *L = 1st partial derivative of L with respect to gamma and **L = 2nd partial derivative of L with respect to gamma, then new gamma - gamma = *L/**L. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Álvaro Begué wrote: On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If you are going to compute all 8 hash keys, you can just add them up at the end instead of picking the minimum. Wouldn't that be better? I think that's pretty workable.XOR is definitely wrong here. If you use xor, then the empty board would hash to the same value as the position after a stone (of either color) is placed on e5 as well as any other symmetry like this.I also think symetries like putting a black stone on 2 points across from each other (such as in diagonal corners) would create a zero hash because you have 2 sets of 4 hashes that cancel each other.I think addition as Álvaro suggests fixes this. - 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] rotate board
The only way this might help is in the opening or in very nearly symmetrical positions and this is really rare. The possible slight benefit would be canceled by even a very small slowdown. It would be useful on small boards as an opening book however where exact positions (or hashes) are stored. - Don Chris Fant wrote: As Gunnar pointed out, you may not need the canonical hash at all. I think you only need to compute the canonical hash if you are matching to some game-external hash, such as a fuseki or pattern library. If you are just using it for transposition and super-ko checking, no board rotation will have occurred. ___ 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] rotate board
Don Dailey wrote: You can use Zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. Yes. Don is right. Of course that is not part of the real program, but of a program that searches the book. In my case (19x19 only) I play a maximum of 20 moves (10 per player) from the book and then switch to the real program. I never shared the naif idea that some openings (played by high dan) are better than others and that finding a correlation between a given move and the result of the game was meaningful. I consider all popular openings equally balanced and playable. Finding a move in the book just saves you the time of 4-5 moves (10 if you are really lucky), gives you a straightforward way to randomize the opening (drawing between all moves in the book uniformly) and makes the board contain some information when the real thing starts. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Jacques Basaldúa wrote: Don Dailey wrote: You can use Zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. Yes. Don is right. Of course that is not part of the real program, but of a program that searches the book. In my case (19x19 only) I play a maximum of 20 moves (10 per player) from the book and then switch to the real program. I never shared the naif idea that some openings (played by high dan) are better than others and that finding a correlation between a given move and the result of the game was meaningful. I consider all popular openings equally balanced and playable. Finding a move in the book just saves you the time of 4-5 moves (10 if you are really lucky), gives you a straightforward way to randomize the opening (drawing between all moves in the book uniformly) and makes the board contain some information when the real thing starts. Indeed, my book scheme for Lazarus is very simple. I track the first move out of book for Lazarus and deep search it N times (for variety.)The next time Lazarus encounters that same position, there is a book response and Lazarus saves search time. Lazarus plays moves in same proportion they are selected in the deep search process. In the opening position, if e5 was selected 5 times and d5 1 times, Lazarus would play e5 5/6th of the time. In all games, Lazarus writes to a file the first move out of book and it is placed in a queue of moves to be deep-searched. In practice, the book search is slower than on-line play but this could be adjusted. I'm building up moves to be searched quicker than I am searching them. I could solve this by setting N smaller and/or searching faster but I prefer nice deep searches with reasonable variety. I think N is 4 right now. This doesn't guarantee that the book moves are high quality, but it does have the desirable features that the search is better than during a real game and it saves time.I suspect saving time for future searches is more important than the improved quality of the opening moves. Unfortunately, if Lazarus improves I have to rebuild from scratch (unless the improvement was very minor.) Also, the book would not be useful for games at higher time-controls than the book was searched at. - 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/
Re: [computer-go] rotate board
I stand corrected.
Arthur
- Original Message -
From: Álvaro Begué [EMAIL PROTECTED]
Date: Thursday, December 20, 2007 4:37 pm
Subject: Re: [computer-go] rotate board
To: computer-go computer-go@computer-go.org
On Dec 20, 2007 11:23 AM, Arthur W Cater [EMAIL PROTECTED] wrote:
I think that would be worse. There are lots of sets of 8 numbers
that sum
the same,
far more than there are sets of 8 with the same minimum element.
Arthur
- Original Message -
From: Álvaro Begué [EMAIL PROTECTED]
Date: Thursday, December 20, 2007 4:08 pm
Subject: Re: [computer-go] rotate board
To: computer-go computer-go@computer-go.org
On Dec 20, 2007 10:19 AM, Jason House
[EMAIL PROTECTED] wrote:
On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED]
wrote:
With 8 hashes per position, the chance of two different boards
producing a different set of hashes but
the same canonical hash is greater than 1/2^64, because there
will be
a bias in the choice of canonical
hashes - toward numerically lower numbers, for instance.
I think.
More importantly, how does it differ from 8/2^64 = 1/2^61?
If you are going to compute all 8 hash keys, you can just add them
up at the
end instead of picking the minimum. Wouldn't that be better?
That can't possibly be true... Think about it. Sums of random
numbers are
uniformly distributed (remember we are working in the ring of integers
modulo 2^64), while the minimum is very biased towards small numbers.
These two Unix commands show the number of different sums and the
number of
different minimums among 10,000 sets of 8 random integers. I did it
with 16
bits instead of 64:
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..1){$s=0;for$y (1..8){$s+=int(rand(65536));}print
.($s%65536).\n;}' | sort -u | wc
-l
9294
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..1){$s=999;for $y (1..8){$t=int(rand(65536)); $s=$t if
$t$s;}print $s\n;}' | sort -u | wc -l
7476
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Taking the min of the 8 rotated and reflected values is safe enough.
Yes, the probability density will be eight times higher at the low
end, so you're left with 61 bits and change worth of collision
protection instead of 64. If that's not enough, then you can use a
bigger hash size, as has been mentioned. And since all practical hash
table sizes are far less than 2^61, let alone 2^64, I think that
(minimum hash % hash_table_size) should work fine as a key to your
hash table, while -- and this may be different from what Jason had in
mind -- the formula ((bit-reverse of mininum hash) % hash_table_size))
will, if hash_table_size is a multiple of 8, needlessly favor hash
values that are even or multiples of 4 or 8.
On Dec 20, 2007 1:33 PM, Don Dailey [EMAIL PROTECTED] wrote:
If you are going to compute all 8 hash keys, you can just add them up
at the end instead of picking the minimum. Wouldn't that be better?
I think that's pretty workable.XOR is definitely wrong here. If
you use xor, then the empty board would hash to the same value as the
position after a stone (of either color) is placed on e5 as well as any
other symmetry like this.I also think symetries like putting a black
stone on 2 points across from each other (such as in diagonal corners)
would create a zero hash because you have 2 sets of 4 hashes that cancel
each other.I think addition as Álvaro suggests fixes this.
No, the problem you identified applies to addition too. There is no
100% certainty of collision, but there is a very elevated probability
of it. The eight symmetries include reflections and 180 degree
rotations, all of which have the property that s(s(p)) = p. Suppose
your symmetry transformation exchanges points a and c, and points b
and d. How does the sum of the Zobrist hashes compare for the set
{a,b} versus the set {a,d}? They will collide if
(a XOR b) + (c XOR d) = (a XOR d) + (c XOR b)
If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision
is guaranteed. The probability of this is closer to 2^-32 than to
2^-64.
I suggest that those who are interested follow Erik's link
(http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653),
as this is not the first or second (or probably even third) time this
issue has come up, and as people have warned several times before, it
is easy to get wrong. I vaguely remember that somebody found a safe
set of Zobrist values that allows reflections to be detected without
recomputation and without greatly increasing the collision probability
was found, but I don't remember the details. I also vaguely remember
hearing that the random values with rotated nybbles approach is
broken too.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
I wrote: If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision is guaranteed. The probability of this is closer to 2^-32 than to 2^-64. Before anybody else feels the need to correct me here -- to be more precise, the probability of collision is at least E(0.5**binomial_variable(64, 0.5)) ~= 1/100,000,000. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Pseudo random number and hashing. Two ways to get into trouble quickly.
The idea of combining all 8 transformations is appealing on modern
processors because you can eliminate all conditional branching.But
maybe this is not practical after all.
If speed is not a concern, you could simple hash the 64x8 bit value
itself with a good mixing hash function, such as md4 or md5.But even
this doesn't work unless you establish some kind of ordering first,
such as sorting them before hashing them.
- Don
Eric Boesch wrote:
Taking the min of the 8 rotated and reflected values is safe enough.
Yes, the probability density will be eight times higher at the low
end, so you're left with 61 bits and change worth of collision
protection instead of 64. If that's not enough, then you can use a
bigger hash size, as has been mentioned. And since all practical hash
table sizes are far less than 2^61, let alone 2^64, I think that
(minimum hash % hash_table_size) should work fine as a key to your
hash table, while -- and this may be different from what Jason had in
mind -- the formula ((bit-reverse of mininum hash) % hash_table_size))
will, if hash_table_size is a multiple of 8, needlessly favor hash
values that are even or multiples of 4 or 8.
On Dec 20, 2007 1:33 PM, Don Dailey [EMAIL PROTECTED] wrote:
If you are going to compute all 8 hash keys, you can just add them up
at the end instead of picking the minimum. Wouldn't that be better?
I think that's pretty workable.XOR is definitely wrong here. If
you use xor, then the empty board would hash to the same value as the
position after a stone (of either color) is placed on e5 as well as any
other symmetry like this.I also think symetries like putting a black
stone on 2 points across from each other (such as in diagonal corners)
would create a zero hash because you have 2 sets of 4 hashes that cancel
each other.I think addition as Álvaro suggests fixes this.
No, the problem you identified applies to addition too. There is no
100% certainty of collision, but there is a very elevated probability
of it. The eight symmetries include reflections and 180 degree
rotations, all of which have the property that s(s(p)) = p. Suppose
your symmetry transformation exchanges points a and c, and points b
and d. How does the sum of the Zobrist hashes compare for the set
{a,b} versus the set {a,d}? They will collide if
(a XOR b) + (c XOR d) = (a XOR d) + (c XOR b)
If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision
is guaranteed. The probability of this is closer to 2^-32 than to
2^-64.
I suggest that those who are interested follow Erik's link
(http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653),
as this is not the first or second (or probably even third) time this
issue has come up, and as people have warned several times before, it
is easy to get wrong. I vaguely remember that somebody found a safe
set of Zobrist values that allows reflections to be detected without
recomputation and without greatly increasing the collision probability
was found, but I don't remember the details. I also vaguely remember
hearing that the random values with rotated nybbles approach is
broken too.
___
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] CGOS 19 is stuck
CGOS 19 is has been stuck for a while now. At the bottom of the page, it says Many Faces is in a game, but does not show it as currently playing at the top of the page. Perhaps the problem is related to a bot leaving near the time a round is ending/beginning. I guess Oliver isn't running the watchdog script that Don created? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS 19 is stuck
The watchdog script works great! It has restarted the server several times over the past month. However, right now 9x9 is down due to some frequent reboots of the boardspace server that is being looked into. I still manually run the watchdog script so it will not recover the server after a reboot. Eventually I will turn this into a cron script. I will ask Olivier if he wants to incorporate my scripts into the 19x19 server once I have it set up in cron. It's a real hack - I should just fix the server. - Don Chris Fant wrote: CGOS 19 is has been stuck for a while now. At the bottom of the page, it says Many Faces is in a game, but does not show it as currently playing at the top of the page. Perhaps the problem is related to a bot leaving near the time a round is ending/beginning. I guess Oliver isn't running the watchdog script that Don created? ___ 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] ELO Ratings of move pattern
I was trying to come up with my own algorithm to maximize likelihood and I am having a hard time getting it all in my mind. I managed to write a working algorithm for the case of logistic regression, but it was kind of brittle and I didn't know how to extend it to the softmax case, which is what I wanted. Over lunch I thought of another way of doing it that would be very general and easy to implement. Basically, I can compute the log-likelihood for a particular setting of the weights, and I can compute the gradient and the Jacobian matrix (the derivative with respect to each weight or pair of weights, respectively). Then I can approximate the function I am minimizing using a paraboloid computed from that data, compute the minimum of the paraboloid and take that point to be the new setting of the weights. Has anyone tried something like this? It seems like the natural way to do it to me. Anyway, I would really appreciate if other people that are trying this kind of thing could exchange some test datasets with me to see if I get to similar weights. I think I will make the code available for anyone to use after I get it to be satisfactory enough. Álvaro. On Dec 20, 2007 11:43 AM, Jason House [EMAIL PROTECTED] wrote: On Dec 5, 2007 4:44 AM, Lars [EMAIL PROTECTED] wrote: I have some questions concernig this paper of Remi: http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf @Remi: How many iterations you had used? Anyone of you have similar or other experiences with the algorithm? I seem to have more time to think than to code lately. I believe I've derived an alternate update method. I'd be curious how quickly it converges. Using Minorization-Maximization, Remi derived new gamma = wins/sum(C/E) Using Newton-Raphson method, I derived fractional change = (estimation error) * (fractional uncertainty)^2 new gamma = gamma * (1 + fractional change) Where estimation error = (wins-expected wins) fractional uncertainty = sigma/gamma fractional change = new gamma/gamma - 1 Changing gamma based on both the estimation error and the uncertainty that gamma is correct makes intuitive sense to me. Sigma matches remi's definition. Because strengths are multiplied together, fractional uncertainty makes more sense. I'm avoiding the difficult issue of explaining why, but I do point people to consider two things: 1. If gamma=gamma+sigma, what does that do to team strength? (It multiplies the team strength by 1 + fractional uncertainty) 2. Look at the similar definitions of fractional uncertainty and fractional change. A less intuitive form is: fractional change = (wins-expected wins) / (expected wins^2 - wins) Using Remi's notation, expected wins = gamma*sum(C/E) Regardless of if someone else plays with the alternate equation, I'll be playing with both after the holidays. I'd also be curious what thoughts people have about this. To derive this, I applied the Newton-Raphson method to find where the partial derivative of the log-evidence is zero (AKA, where log-evidence is maximized). If L = log evidence, and *L = 1st partial derivative of L with respect to gamma and **L = 2nd partial derivative of L with respect to gamma, then new gamma - gamma = *L/**L. ___ 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] ELO Ratings of move pattern
On Dec 20, 2007 11:43 AM, Jason House [EMAIL PROTECTED] wrote: I seem to have more time to think than to code lately. I believe I've derived an alternate update method. Thinking more, I realize I messed up a three things... For one, Newton-Raphson requires new gamma - gamma = -*L/**L instead of new gamma - gamma = *L/**L Another, 1/sigma^2 = -**L instead of 1/sigma^2 = **L Finally, **L = sum[ (selection probability)^2 ] - wins instead of **L = (estimated wins)^2 - wins Using Newton-Raphson method, I derived fractional change = (estimation error) * (fractional uncertainty)^2 new gamma = gamma * (1 + fractional change) A less intuitive form is: fractional change = (wins-expected wins) / (expected wins^2 - wins) Using Remi's notation, expected wins = gamma*sum(C/E) This becomes: fractional change = ( wins - sum(selection probability) ) / ( wins - sum((selection probability)^2) ) selection probability = gamma*C/E ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] ELO Ratings of move pattern
On Dec 20, 2007 5:39 PM, Álvaro Begué [EMAIL PROTECTED] wrote: I was trying to come up with my own algorithm to maximize likelihood and I am having a hard time getting it all in my mind. I managed to write a working algorithm for the case of logistic regression, but it was kind of brittle and I didn't know how to extend it to the softmax case, which is what I wanted. Over lunch I thought of another way of doing it that would be very general and easy to implement. Basically, I can compute the log-likelihood for a particular setting of the weights, and I can compute the gradient and the Jacobian matrix (the derivative with respect to each weight or pair of weights, respectively). Then I can approximate the function I am minimizing using a paraboloid computed from that data, compute the minimum of the paraboloid and take that point to be the new setting of the weights. Has anyone tried something like this? It seems like the natural way to do it to me. My knowledge of the Jacobian matrix is limited. http://en.wikipedia.org/wiki/Jacobian seems to imply that your definition of the Jacobian matrix is unusual. To fit a paraboloid, don't you need the 2nd derivative as well? I'd assume you'd fit a parabola in each direction (for each gamma) and then sum them together into one paraboloid Interestingly enough, I believe assuming a paraboloid is equivalent to assume a linear first derivative (which is what I did). Of course, I have no idea how the Jacobian comes into play, so I assume I'm missing a few things. Is it possible to share a bit more of your final method? Anyway, I would really appreciate if other people that are trying this kind of thing could exchange some test datasets with me to see if I get to similar weights. I think I will make the code available for anyone to use after I get it to be satisfactory enough. I'm not that far yet. I'll share when I have it, although I plan to try and use the same starting data set (games) as Remi. I have yet to code calculation of some of the features. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] ELO Ratings of move pattern
On Dec 20, 2007 10:36 PM, Jason House [EMAIL PROTECTED] wrote: On Dec 20, 2007 5:39 PM, Álvaro Begué [EMAIL PROTECTED] wrote: Over lunch I thought of another way of doing it that would be very general and easy to implement. Basically, I can compute the log-likelihood for a particular setting of the weights, and I can compute the gradient and the Jacobian matrix (the derivative with respect to each weight or pair of weights, respectively). Then I can approximate the function I am minimizing using a paraboloid computed from that data, compute the minimum of the paraboloid and take that point to be the new setting of the weights. Has anyone tried something like this? It seems like the natural way to do it to me. My knowledge of the Jacobian matrix is limited. http://en.wikipedia.org/wiki/Jacobian seems to imply that your definition of the Jacobian matrix is unusual. Ooops! It's been too long since I learned these things. What I meant to say was the Hessian matrix ( http://en.wikipedia.org/wiki/Hessian_matrix ), which does contain the second derivatives. You are right that assuming the derivative changes linearly and using a paraboloid are the exact same thing. So we are probably thinking of the same method, although I think I can code it in very elegantly (maybe slow too?). Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
