Re: [computer-go] Is skill transitive? No.

[Vlad Dumitrescu]

Hi,

On 1/30/07, Don Dailey <[EMAIL PROTECTED]> wrote:

It would be interesting if it would be possible to construct a 2
dimensional
model statistically.   A 2 dimensional system would not be a perfect fit
either,
but would simply be a better approximation.So in some way a players
"strength" could be expressed by 2 numbers instead of 1,  and the 2
numbers
together would predict your chances of beating another (2 dim) player
more accurately that a 1 dimension system could.   And of course you
could
extend this.   But I don't have a clue how one would construct such a
system
or if it's even possible - but it seems like more information should be
better
than less.


Unfortunately, having more than one dimensions makes comparisons
impossible - if an ordering relation is defined over the domain, then
this domain is "one-dimensional" with regard to that relation.

In other words, one can't compare vectors, just scalars. So the
multi-dimensional "strength vector" has to be turned into a scalar (by
for example a weighted sum) and we're back where we started...

best regards,
Vlad (master of the obvious :-)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Ordering of moves with UCT

[Vlad Dumitrescu]

Hi all,

I wonder if anybody has some data (or a theory) about how valuable a
good preordering of the children of a node would be, when UCT. This
might take the form of having nodes start with non-null values for the
'won_simulations' and 'played_simulations' fields.

Or maybe this could work only if combining UCT with some kind of alpha-beta?

best regards,
Vlad
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Scaling monte carlo up to 19x19

[Daniel Burgos]

I'm working now in a similar idea.

As yours, it will play only in one zone using MC. It will start on 7x7
sub-boards but they will grow once they become full of stones.

I will normalize the sub-board results using its area. It will help me to
compare the different sub-boards.

Once all the sub-boards get evaluated, it will play in the sub-board with
less winning moves (first the urgent, then the important).

But the main idea is the same as yours: scale breaking the board down.

2007/1/30, Dave Dyer <[EMAIL PROTECTED]>:



Here's an idea for scaling up, which should result in "only" factor
of 10 slower speed.   To scale from 9x9 to 19x19, subdivide the
board into four, overlapping 10x10 boards.   Run a standard 9x9
monte carlo up to the 90% full stage on each of the four boards,
then run a full board monte on the whole board remaining.

Treat the ovelapping stripes as edges in a slightly more sophisticated
way than usual, becuase you might be connecting to liberties by playing
in the stripe.

To avoid artifacts caused by the location of the overlaps: the number
of zones, and the location of the stripes, is also subject to
randomization.

It might be interesting to try this on a 9x9 board using a 5x5 zone
to begin with.

___
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] Ordering of moves with UCT

[Magnus Persson]

Quoting Vlad Dumitrescu <[EMAIL PROTECTED]>:


I wonder if anybody has some data (or a theory) about how valuable a
good preordering of the children of a node would be, when UCT. This
might take the form of having nodes start with non-null values for the
'won_simulations' and 'played_simulations' fields.


I have been thinking about this but not done anything empirical about it. Here
are some thoughts: there are two ways for move ordering a) static (such as
pattern matching) and b) dynamic (killer heuristic/history heuristic as for
alpha-beta).

The problem with static move ordering that it must be really good it to be
useful, and it migh be computationally expensive if it is really good.

The problem with dynamic move ordering where the search results from 
one part of

the tree is applied to a new part of the tree is the nature of UCT itself.
Alpha-beta has systematic search so when a subtree has been evaluated we can
know for sure if the move was a killer move or not. With UCT the entire 
tree is

updated in an unpredictable manner, a move thats look like a killer move might
suddenly become refuted, but how would we then keep track of all places in the
tree this move has affected the move ordering? This happens in alpha-beta too
but with iterative deepening everything all nodes are visited again in an
orderly manner where fresh killer moves are used.



Or maybe this could work only if combining UCT with some kind of alpha-beta?


I used alpha-beta with MC evaluation for Viking5. Only a few 100 simulations
where used at terminal nodes for evaluation and then UCT would not be much
different from plain MC. And since evaluation is at terminal nodes we cannot
know well how to order the moves, unless static move ordering is used.
Implicitely this is done by having improvements to the simulations.

-Magnus
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Scaling monte carlo up to 19x19

[Benjamin Teuber]

Funny thing, I also just thought about this as a friend of mine had an 
idea similiar to Dave's.
I guess it might be a good idea to make your zone-partitioning (or 
zone-merging, when you start from 1x1-boards) dependant of the current 
board configuration. That is, some clever algorithm (probably another 
kind of MC) might judge the "interdependencies" over the board graph and 
decide what is better dealt with together and what might be looked at alone.


Of course, everything depends on how you can deal with the boarders - 
how about some monte-carlo-simulations over the possible 
boarder-configurations?

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[Nick Apperson]

I feel that what we need essentially is a set of functions that tell us
expected winning percentages with certain matchups.  In an extreme example,
we could imagine 3 rock, paper, scissors players.  One always plays rock,
one always scissor and one always plays paper.  In this case, we would be
able to define a ranking function as a relative ranking, but absolutre
ranking would not exist.  And this is consistent with our whole approach
here that skill is not transitive.  A simple 2D ranking system could work
like this:

let W = chance that player 1 will beat player 2
1-W = chance that player 2 will beat player 1

our skill is expressed in R and T (for theta)

ELO = (R1-R2)+k*sin(T1-T2)   where k is some constant, R1, R2, T1, T2 are R
of player 1 and 2, theta of player 1 and 2 respectively


This would result in a  nontransitive 2D skill map.  There are many, more
compex functions that could be worked out and this has the nice property
that it easily collapses into a 1D map by merely setting everyone's theta to
the same value.  Essentially R is "general skill" and theta is a rock paper
scissor type thing where one strategy is better against certain other types
of strategies.


On 1/31/07, Vlad Dumitrescu <[EMAIL PROTECTED]> wrote:


Hi,

On 1/30/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> It would be interesting if it would be possible to construct a 2
> dimensional
> model statistically.   A 2 dimensional system would not be a perfect fit
> either,
> but would simply be a better approximation.So in some way a players
> "strength" could be expressed by 2 numbers instead of 1,  and the 2
> numbers
> together would predict your chances of beating another (2 dim) player
> more accurately that a 1 dimension system could.   And of course you
> could
> extend this.   But I don't have a clue how one would construct such a
> system
> or if it's even possible - but it seems like more information should be
> better
> than less.

Unfortunately, having more than one dimensions makes comparisons
impossible - if an ordering relation is defined over the domain, then
this domain is "one-dimensional" with regard to that relation.

In other words, one can't compare vectors, just scalars. So the
multi-dimensional "strength vector" has to be turned into a scalar (by
for example a weighted sum) and we're back where we started...

best regards,
Vlad (master of the obvious :-)
___
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] Re: Scaling monte carlo up to 19x19

[Dave Dyer]

>
>Of course, everything depends on how you can deal with the boarders - how 
>about some monte-carlo-simulations over the possible boarder-configurations?

My thought is that one thing you could easily get from the rollouts
is a good estimate of the status of each string of stones currently
on the board, and the eventual owner of each empty space.

In the zone logic, stones adjacent to the border would count the border
as friendly or unfriendly based on the best estimate of that status.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Ordering of moves with UCT

[Don Dailey]

I have experimented a little with getting moves that are likely
to be best first in the list - and in come cases giving them
extra weight so that quickly get expanded early.   However, I
never showed a measurable improvement but I didn't stick with
it long enough to develop the idea fully.  

My basic experiment was to place captures first and moves that
avoided or put the opponent into atari, nothing very sophisticated
and no patterns or general ordering.  

- Don



On Wed, 2007-01-31 at 10:22 +0100, Vlad Dumitrescu wrote:
> Hi all,
> 
> I wonder if anybody has some data (or a theory) about how valuable a
> good preordering of the children of a node would be, when UCT. This
> might take the form of having nodes start with non-null values for the
> 'won_simulations' and 'played_simulations' fields.
> 
> Or maybe this could work only if combining UCT with some kind of alpha-beta?
> 
> best regards,
> Vlad
> ___
> 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] Is skill transitive? No.

[Don Dailey]

My basic idea, which is undeveloped is rather like this - you partition
all players into 2 (or more) broad styles.  One of the variables in the
rating
tells you how much (from 0 to 1) he plays at one extreme.   The rating
system itself somehow determines which style you are and it's an
abstract
quality that we don't necessarily have to understand.   (sort of like
learning algorithms that build neural networks that we don't understand
but it works.)

In chess, which I use as an example because I understand it much better,
there are kinds of playing styles that interact.  You can have very 
good tactical players (who love gambit play sometimes) and you have
very slow positional style.   Some very good players are not
particularly
good at tactics.   I don't know what conclusions you can draw about
who is expected to win matches between various styles,  but I'll bet
there is a measurable non-transitive relationship somewhere there.

Of course an outright learning algorithm,  if given enough games,
might be able to predict winning expectancy better than straight
ELO.   

- Don


On Wed, 2007-01-31 at 05:54 -0600, Nick Apperson wrote:
> I feel that what we need essentially is a set of functions that tell
> us expected winning percentages with certain matchups.  In an extreme
> example, we could imagine 3 rock, paper, scissors players.  One always
> plays rock, one always scissor and one always plays paper.  In this
> case, we would be able to define a ranking function as a relative
> ranking, but absolutre ranking would not exist.  And this is
> consistent with our whole approach here that skill is not transitive.
> A simple 2D ranking system could work like this: 
> 
> let W = chance that player 1 will beat player 2
> 1-W = chance that player 2 will beat player 1
> 
> our skill is expressed in R and T (for theta)
> 
> ELO = (R1-R2)+k*sin(T1-T2)   where k is some constant, R1, R2, T1, T2
> are R of player 1 and 2, theta of player 1 and 2 respectively 
> 
> 
> This would result in a  nontransitive 2D skill map.  There are many,
> more compex functions that could be worked out and this has the nice
> property that it easily collapses into a 1D map by merely setting
> everyone's theta to the same value.  Essentially R is "general skill"
> and theta is a rock paper scissor type thing where one strategy is
> better against certain other types of strategies. 
> 
> 
> On 1/31/07, Vlad Dumitrescu <[EMAIL PROTECTED]> wrote:
> Hi,
> 
> On 1/30/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> > It would be interesting if it would be possible to construct
> a 2
> > dimensional
> > model statistically.   A 2 dimensional system would not be a
> perfect fit 
> > either,
> > but would simply be a better approximation.So in some
> way a players
> > "strength" could be expressed by 2 numbers instead of
> 1,  and the 2
> > numbers
> > together would predict your chances of beating another (2
> dim) player 
> > more accurately that a 1 dimension system could.   And of
> course you
> > could
> > extend this.   But I don't have a clue how one would
> construct such a
> > system
> > or if it's even possible - but it seems like more
> information should be 
> > better
> > than less.
> 
> Unfortunately, having more than one dimensions makes
> comparisons
> impossible - if an ordering relation is defined over the
> domain, then
> this domain is "one-dimensional" with regard to that
> relation. 
> 
> In other words, one can't compare vectors, just scalars. So
> the
> multi-dimensional "strength vector" has to be turned into a
> scalar (by
> for example a weighted sum) and we're back where we
> started... 
> 
> best regards,
> Vlad (master of the obvious :-)
> ___
> 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: Scaling monte carlo up to 19x19

[Don Dailey]

On Wed, 2007-01-31 at 04:00 -0800, Dave Dyer wrote:
> >
> >Of course, everything depends on how you can deal with the boarders - how 
> >about some monte-carlo-simulations over the possible boarder-configurations?
> 
> My thought is that one thing you could easily get from the rollouts
> is a good estimate of the status of each string of stones currently
> on the board, and the eventual owner of each empty space.

Monte Carlo is quite good at this - and Botnoid uses this information to
modify it's move choices to a certain extent and it gives it a pretty
good boost in strength.  

I think you have to do more than just partitioning,  you might have to 
assign the stones on the borders of the partition some status such as
"never die" or something.A string that straddles a partition may
have only 1 liberty in the other partition so perhaps just allowing
simple captures outside your partition would be a big improvement.

I think this is worth pursuing - but it's going to very tricky getting
it right.

- Don




> In the zone logic, stones adjacent to the border would count the border
> as friendly or unfriendly based on the best estimate of that status.
> 
> ___
> 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] Is skill transitive? No.

[Richard Brown]

Vlad Dumitrescu wrote:


Unfortunately, having more than one dimensions makes comparisons
impossible - if an ordering relation is defined over the domain, then
this domain is "one-dimensional" with regard to that relation.

In other words, one can't compare vectors, just scalars. So the
multi-dimensional "strength vector" has to be turned into a scalar (by
for example a weighted sum) and we're back where we started...


While that is true, as stated, it is also the case that this is exactly
the sort of thing at which artificial neural networks excel.

Given multiple "inputs" (a d-dimensional vector), the "squashing functions"
in the "layers" of the network in fact reduce the "output" to a single number.

Neural networks are excruciatingly well-documented, as is their use in
a wide variety of domains, even on the web.  [By that I mean, you needn't
buy a book to discover how powerful "multi-layer perceptrons" can be.]

So, while it's correct that "one can't compare vectors, just scalars"
one can compare the _output_ of a vector-massaged-by-a-neural-net
against the _output_ of a vector-massaged-by-a-neural-net.

I think Vlad knows this, of course, as he said, 'the multi-dimensional
"strength vector" has to be turned into a scalar'.  [I'm just here to
clarify one common method of doing that.]

The tough part is deciding what to measure, in your original vector.

I'm sure I don't know what variables one would use, but I agree with
Don:  "the 2 numbers together would predict your chances of beating
another (2 dim) player more accurately that a 1 dimension system could."

I further agree:  "And of course you could extend this."  Which is to say,
there is no reason to stop at two.  [Although there is something called
"the curse of dimensionality", which prevents a too-large dimensionality:
See   .]

In practice, the "feature extraction" phase is crucial.  Deciding what to
measure, finding the right number of items to measure, scaling them properly
(e.g., multiplying a vector element by a constant), not measuring irrelevant
items:  All these things are exceedingly crucial (and often difficult) when
constructing a useful, effective, neural net.

So, I'm stumped.

In theory though, if one measures the right variables, and collects
enough data (sometimes a surprisingly small amount is sufficient!) a
neural network could be trained to recognize and predict the strength
of go-players; witness the (excruciatingly well-documented!) success
of neural networks in a wide variety of domains.

--
Rich
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Scaling monte carlo up to 19x19

[Jacques Basaldúa]

Nick Apperson wrote:


> There are certain times when this technique is highly useful. ...
> imagine a board with two walls down the middle bordering on each other

I agree. We have to divide the board to create strong programs!
But division is a very complicated subject. In the isolated areas UCT
can be a very strong tool. But if you divide the board using a ruler,
just like Africa was divided some time ago, you only create more
problems. Division has to be done with great understanding of the
position and using natural and foreseeable borders.

Jacques.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[Jacques Basaldúa]

Don Dailey wrote:


It would be interesting if it would be possible to construct a 2
dimensional model statistically. A 2 dimensional system would not 
be a perfect fit either, but would simply be a better approximation.


And another constraint is, it must be supported by evidence. I think
this precision is required because, most sources of intransitivity are
very subjective. Player A feels insecure when B opens at tengen, etc.
Normally, it is because a player knows strategies that "hurt" another
player, although they are not very strong against correct defense.

I don't know if this may help, but its and idea:

If instead of assuming a player's performance follows a symmetrical
probability distribution function (the normal in the case of Elo),
assume the p.d.f is asymmetric, e.g. triangular. If player's have
p.d.fs which are increasing, decreasing or rectangular, wouldn't
that produce intransitivity? I don't know if it is the case, but 
simulation should make it clear. If this is the case, the advantage 
is it can be created only from the results of matches and not 
judging a player's ability for this and that.



Jacques.


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[Tapani Raiko]

> If instead of assuming a player's performance follows a symmetrical
> probability distribution function (the normal in the case of Elo),
> assume the p.d.f is asymmetric, e.g. triangular. If player's have
> p.d.fs which are increasing, decreasing or rectangular, wouldn't
> that produce intransitivity? I don't know if it is the case, but simulation
> should make it clear. If this is the case, the advantage is it can be created
> only from the results of matches and not judging a player's ability for this
> and that.

Even if each player's performance is asymmetrical but identical, the 
difference of performance becomes symmetrical again. But still, 
intransitivity can be seen from results of matches. If one has enough 
results of N people playing against each other, one could use the vector 
of performances against each opponent as an input to some machine learning 
method, such as a neural network or principal component analysis. I would 
assume that the first principal component would represent strength and the 
second would give some kind of intransitivity. If someone has result data 
with dense enough pairings, I could run some experiments.

BTW, I also have some ideas on how to make UCT work on the big board. They 
are partly published in a paper using games of Y and Hex as examples (it 
did not use UCT, though).

T. Raiko. Higher Order Statistics in Play-out Analysis. In the proceedings 
of the Scandinavian Conference on Artificial intelligence, SCAI 2006, pp. 
189-195, Espoo, Finland, October 25-27, 2006.
http://www.cis.hut.fi/praiko/papers/scai06.pdf

Tapani

--
 Tapani Raiko, <[EMAIL PROTECTED]>, +358 50 5225750
 http://www.cis.hut.fi/praiko/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[dhillismail]

  
   To gain some intuition re. what level of intransitivites are present on 
CGOS, it would be interesting to see the cross-scores of all (or some...) of 
the bots in a big table. A less obvious refinement is to add color coding to 
make it easier to read. Here's an example from the game of Corewars.
  
http://www.koth.org/lcgi-bin/hugetable.pl?hill94nop
  
   The numbers look a little strange and it's not symetric because Corewars 
is a non-zero sum game. For CGOS, the numbers along the edge would, presumably 
be the the ELO rating and the numbers/colors in the boxes would be for percent 
wins. In Corewars, non-transivity is a very big part of the game. It might be 
interesting to look at the actual win percentages for each pairing against 
those predicted by the ELO differences.

 - Dave Hillis
 
-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Wed, 31 Jan 2007 7:57 AM
Subject: Re: [computer-go] Is skill transitive? No.


My basic idea, which is undeveloped is rather like this - you partition
all players into 2 (or more) broad styles.  One of the variables in the
rating
tells you how much (from 0 to 1) he plays at one extreme.   The rating
system itself somehow determines which style you are and it's an
abstract
quality that we don't necessarily have to understand.   (sort of like
learning algorithms that build neural networks that we don't understand
but it works.)

In chess, which I use as an example because I understand it much better,
there are kinds of playing styles that interact.  You can have very 
good tactical players (who love gambit play sometimes) and you have
very slow positional style.   Some very good players are not
particularly
good at tactics.   I don't know what conclusions you can draw about
who is expected to win matches between various styles,  but I'll bet
there is a measurable non-transitive relationship somewhere there.

Of course an outright learning algorithm,  if given enough games,
might be able to predict winning expectancy better than straight
ELO.   

- Don


On Wed, 2007-01-31 at 05:54 -0600, Nick Apperson wrote:
> I feel that what we need essentially is a set of functions that tell
> us expected winning percentages with certain matchups.  In an extreme
> example, we could imagine 3 rock, paper, scissors players.  One always
> plays rock, one always scissor and one always plays paper.  In this
> case, we would be able to define a ranking function as a relative
> ranking, but absolutre ranking would not exist.  And this is
> consistent with our whole approach here that skill is not transitive.
> A simple 2D ranking system could work like this: 
> 
> let W = chance that player 1 will beat player 2
> 1-W = chance that player 2 will beat player 1
> 
> our skill is expressed in R and T (for theta)
> 
> ELO = (R1-R2)+k*sin(T1-T2)   where k is some constant, R1, R2, T1, T2
> are R of player 1 and 2, theta of player 1 and 2 respectively 
> 
> 
> This would result in a  nontransitive 2D skill map.  There are many,
> more compex functions that could be worked out and this has the nice
> property that it easily collapses into a 1D map by merely setting
> everyone's theta to the same value.  Essentially R is "general skill"
> and theta is a rock paper scissor type thing where one strategy is
> better against certain other types of strategies. 
> 
> 
> On 1/31/07, Vlad Dumitrescu <[EMAIL PROTECTED]> wrote:
> Hi,
> 
> On 1/30/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> > It would be interesting if it would be possible to construct
> a 2
> > dimensional
> > model statistically.   A 2 dimensional system would not be a
> perfect fit 
> > either,
> > but would simply be a better approximation.So in some
> way a players
> > "strength" could be expressed by 2 numbers instead of
> 1,  and the 2
> > numbers
> > together would predict your chances of beating another (2
> dim) player 
> > more accurately that a 1 dimension system could.   And of
> course you
> > could
> > extend this.   But I don't have a clue how one would
> construct such a
> > system
> > or if it's even possible - but it seems like more
> information should be 
> > better
> > than less.
> 
> Unfortunately, having more than one dimensions makes
> comparisons
> impossible - if an ordering relation is defined over the
> domain, then
> this domain is "one-dimensional" with regard to that
> relation. 
> 
> In other words, one can't compare vectors, just scalars. So
> the
> multi-dimensional "strength vector" has to be turned into a
> scalar (by
> for example a weighted sum) and we're back where we
> started... 
> 
> best regards,
> Vlad (m

Re: [computer-go] Is skill transitive? No.

[Stuart A. Yeates]

On 1/31/07, Tapani Raiko <[EMAIL PROTECTED]> wrote:



Even if each player's performance is asymmetrical but identical, the
difference of performance becomes symmetrical again. But still,
intransitivity can be seen from results of matches. If one has enough
results of N people playing against each other, one could use the vector
of performances against each opponent as an input to some machine learning
method, such as a neural network or principal component analysis. I would
assume that the first principal component would represent strength and the
second would give some kind of intransitivity. If someone has result data
with dense enough pairings, I could run some experiments.



Would the results of kgs (or similar) games being appropriate if one
considered only un-handicapped games?

I imagine that the most significant intransitivity would be would be in
relation to the bots (principally GnuGo?), because some players have played
dozens (maybe hundreds) of games against these bots and their playing style
is likely to have been modified by the experience.

cheers
stuart
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[Tapani Raiko]

> Would the results of kgs (or similar) games being appropriate if one
> considered only un-handicapped games?

Yes, I think so. At least when considering only those who have played lots 
of games against lots of opponents.

> I imagine that the most significant intransitivity would be would be in
> relation to the bots (principally GnuGo?), because some players have played
> dozens (maybe hundreds) of games against these bots and their playing style
> is likely to have been modified by the experience.

True. Another effect that might appear is if part of the players are 
developing in skill and at the same time switching to stronger opponents. 
Or perhaps some are better in changing their style (risk level) according 
to opponent strength.

Maybe CGOS data would be the best: lots of games between a limited number 
of stable players.

Tapani
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[Stuart A. Yeates]

On 1/31/07, Tapani Raiko <[EMAIL PROTECTED]> wrote:


> I imagine that the most significant intransitivity would be would be in
> relation to the bots (principally GnuGo?), because some players have
played
> dozens (maybe hundreds) of games against these bots and their playing
style
> is likely to have been modified by the experience.

True. Another effect that might appear is if part of the players are
developing in skill and at the same time switching to stronger opponents.
Or perhaps some are better in changing their style (risk level) according
to opponent strength.

Maybe CGOS data would be the best: lots of games between a limited number
of stable players.



"Best" for proving beyond a shadow of a doubt that intransitivity exists in
game playing? yes.

"Best" but not necessarily best for proving that intransitivity exists in
ways that matter to most users of ELO-type systems? no.

cheers
stuart
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is skill transitive? No.

[Don Dailey]

All the data for cgos is available as files zipped up by month.  So
any kind of study is possible.  

- Don


On Wed, 2007-01-31 at 10:44 -0500, [EMAIL PROTECTED] wrote:
>   
>To gain some intuition re. what level of intransitivites are
> present on CGOS, it would be interesting to see the cross-scores of
> all (or some...) of the bots in a big table. A less obvious refinement
> is to add color coding to make it easier to read. Here's an example
> from the game of Corewars.
>   
> http://www.koth.org/lcgi-bin/hugetable.pl?hill94nop
>   
>The numbers look a little strange and it's not symetric because
> Corewars is a non-zero sum game. For CGOS, the numbers along the
> edge would, presumably be the the ELO rating and the numbers/colors in
> the boxes would be for percent wins. In Corewars, non-transivity is a
> very big part of the game. It might be interesting to look at the
> actual win percentages for each pairing against those predicted by the
> ELO differences.
> 
>  - Dave Hillis
>  
> -Original Message-
> From: [EMAIL PROTECTED]
> To: computer-go@computer-go.org
> Sent: Wed, 31 Jan 2007 7:57 AM
> Subject: Re: [computer-go] Is skill transitive? No.
> 
> My basic idea, which is undeveloped is rather like this - you partition
> all players into 2 (or more) broad styles.  One of the variables in the
> rating
> tells you how much (from 0 to 1) he plays at one extreme.   The rating
> system itself somehow determines which style you are and it's an
> abstract
> quality that we don't necessarily have to understand.   (sort of like
> learning algorithms that build neural networks that we don't understand
> but it works.)
> 
> In chess, which I use as an example because I understand it much better,
> there are kinds of playing styles that interact.  You can have very 
> good tactical players (who love gambit play sometimes) and you have
> very slow positional style.   Some very good players are not
> particularly
> good at tactics.   I don't know what conclusions you can draw about
> who is expected to win matches between various styles,  but I'll bet
> there is a measurable non-transitive relationship somewhere there.
> 
> Of course an outright learning algorithm,  if given enough games,
> might be able to predict winning expectancy better than straight
> ELO.   
> 
> - Don
> 
> 
> On Wed, 2007-01-31 at 05:54 -0600, Nick Apperson wrote:
> > I feel that what we need essentially is a set of functions that tell
> > us expected winning percentages with certain matchups.  In an extreme
> > example, we could imagine 3 rock, paper, scissors players.  One always
> > plays rock, one always scissor and one always plays paper.  In this
> > case, we would be able to define a ranking function as a relative
> > ranking, but absolutre ranking would not exist.  And this is
> > consistent with our whole approach here that skill is not transitive.
> > A simple 2D ranking system could work like this: 
> > 
> > let W = chance that player 1 will beat player 2
> > 1-W = chance that player 2 will beat player 1
> > 
> > our skill is expressed in R and T (for theta)
> > 
> > ELO = (R1-R2)+k*sin(T1-T2)   where k is some constant, R1, R2, T1, T2
> > are R of player 1 and 2, theta of player 1 and 2 respectively 
> > 
> > 
> > This would result in a  nontransitive 2D skill map.  There are many,
> > more compex functions that could be worked out and this has the nice
> > property that it easily collapses into a 1D map by merely setting
> > everyone's theta to the same value.  Essentially R is "general skill"
> > and theta is a rock paper scissor type thing where one strategy is
> > better against certain other types of strategies. 
> > 
> > 
> > On 1/31/07, Vlad Dumitrescu <[EMAIL PROTECTED]> wrote:
> > Hi,
> > 
> > On 1/30/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> > > It would be interesting if it would be possible to construct
> > a 2
> > > dimensional
> > > model statistically.   A 2 dimensional system would not be a
> > perfect fit 
> > > either,
> > > but would simply be a better approximation.So in some
> > way a players
> > > "strength" could be expressed by 2 numbers instead of
> > 1,  and the 2
> > > numbers
> > > together would predict your chances of beating another (2
> > dim) player 
> > > more accurately that a 1 dimension system could.   And of
> > course you
> > > could
> > > extend this.   But I don't have a clue how one would
> > construct such a
> > > system
> > > or if it's even possible - but it seems like more
> > information should be 
> > > better
> > > than less.
> > 
> > Unfortunately, having more than one dimensions makes
> > comparisons
> > impossible - if an ordering relation is defined over the
> > domain, then
> > this domain i