[computer-go] Re: Open source real time Go server

[Jacques Basaldúa]

Petr Baudis wrote:

> This seems like not very productive line of argumentation unless
> preceded with more exact definitions of strong.

My only claim is that "it is a hard problem". That is unobjectionable
no matter how you define strong (obviously: random < strong < perfect)
I can't understand why you object on this.

> Actually, there is a thread about exactly this on fuego-devel

In fact it is not "exactly this" it is a different approach.
The post in fuego-devel tries to determine the status of each
point of the board. That is not a good idea with or without MCTS
because go is about trading. (Furikawari)

My different approach is determining by "how many points" the
simulated games are won. Only in yose the IQR becomes narrow
enough to see how much territory is still in dispute.

Stefan Kaitschick wrote:

> If resources were no problem, the best way to estimate the score
> would probably be to have an MC program find the komi that results
> in a 50% winrate.

Yes! That is my proposal. Saying an MCTS program is happy (60%)
or unhappy (32%) does not inform too much to non-computer-go
observers. If you talk about "winning rate" they understand
"the probability that the program wins" which is not the case.

Telling them the program is happy, but would end being happy
if it had to win by 20 additional points is crystal clear.

The "correct" way to determine the komi shift would be to try
all possible values. Since that is expensive, my proposal
estimates the komi shift from one single 20K run by studying
the distribution. Of course, it is only an estimation and the
other method would be more accurate. Additionally, the estimator
gives a confidence interval or remembers the observer that score
estimation in move 60 is a fallacy.

We have to live with the two facts:

* Each board position has a value. (The game satisfies the
conditions of the minimax theorem.)

* Pretty much every position has a value that is computationally
untreatable. And this applies to human estimators as well. They
only score according to established practice, which is something
that is revised as new empirical evidence shows up.

Scoring at move 60 is just an educated guess. (Of course people
will more likely accept the guess of a 9d than the guess of a 15k.)

The "cool" part is the estimator can tell you the difference when
it is just making an educated guess and when most of the territory
is already "sold out" with few points in dispute.

Jacques.

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

[computer-go] Re: Open source real time Go server

[Jacques Basaldúa]

Hi

1. Just a small precision first:

Ingo Althöfer wrote:

> Terry McIntyre wrote:
> > ... My pet peeve is the KGS "score estimator", which is often wildly
> wrong

> As explained by others a "strong SE for ALL positions" is equivalent
> to a strong program.

This is only true if you replace the word “strong” by “perfect”. It is
trivial, that a perfect evaluation function gives a perfect player using
a 1-ply search, but that is not true for strong evaluation functions.
Converting a strong evaluation function into a strong program is still
a hard problem. “Almost” good moves are frequently worse than random
moves. (E.g. a move that “almost saves” a group that cannot be saved
or “almost kills” a group that cannot be killed gives one prisoner to
the opponent and wastes one turn. This is worse than pass while random
moves are with a high probability better than pass.)


2. Now my proposal: An MC based SE (Score Estimator).

Use a strong MCTS program unmodified, except in a small detail to collect
data about by how many points each simulation is won. Play a feasible
number of simulations like 20K. Build the distribution of the result
(= The histogram counting how many wins were found by each result).
Otherwise, let the program follow the tree as it does unmodified. In
this distribution find the 3 quartiles (the komi shift that produces
Q1 25%-75%, Q2 50%-50% and Q3 75%-25% wins for each).

If IQR (Interquartile range) = Q3-Q1 > some threshold (say 25 points)

output: Q2 as “B+3.5 with large error margin”

else

output: Q2 + IQR as “B+3.5 IQR(W+1.5, B+11.5)”

This would be a state of the art SE and the number of simulations could
also be a parameter controlled by the user to adapt the precision to his
hardware and patience.


After all, it is easier to get a SE from a strong program than the other
way round ;-)


Jacques.


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

[computer-go] Fuego 04 native Windows

[Jacques Basaldúa]

Michael Williams

> It has been some time since you made this.

It was last summer (2009). I needed a strong program to test an idea on it
that worked well on a weaker program. I haven't shared this with the list
yet, because I am now modifying it and cannot spend as much time as I
would like. What I need to prove is that Fuego + mod wins against
Fuego without mod. I do not plan to continue using Fuego after that
since I have my own platform.

> Did you have to make changes to any of the original Fuego files?

Yes. You can sort the files by date to see which have been.
I think all modifications have the remark // WinFuego04
(At least it should be so.)

Most of the modifications are:

1. Adding an explicit (type) to make the compiler accept a flexible
use of different types. Of course, I assume the original programmer
did that on purpose and the program is debugged, so I is just
telling the compiler to ignore it.

2. Adding a #pragma to ignore a warning for the same reason.

3. Includes to "WinFuego_linux2win" because the time library
used is not the same a the libraries available in MS c++
This translates some functions I couldn't find directly to
their Windows API equivalent.

I don't remember if there are more, but none is functional. I mean
I did not change the behavior of the program in any way. (I did so
later after studying what the program did when I could run it.)

> I'm asking because I'm trying to figure out what would go wrong
> if I dumped current Fuego files into the Windows-buildable source
> that you provided.

If the new Fuego does not use more boost functions, the subset
of boost libraries included should be enough. Otherwise you should
find the missing boost files from the same version of boost.

If you try to compile the new files, assuming the architecture of the
program did not change, you will get the same (or similar) errors
and warnings I got and you have my files to see how I corrected
it. It is a tedious work but it can be done since I did that already.

Jacques.


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

[computer-go] Biasing nodes according to pattern gammas

[Jacques Basaldúa]

> Petr Baudis wrote:
> > I wonder now, do you use separate set of gammas for simulations and 
node
> > biasing? Since I've found that the performance seems very bad if I 
don't

> > include some time-expensive features, since the gammas are then very
> > off; I will probably simply generate two gamma sets, but perhaps it's
> > enough to do some trick like merging features by computing weighted
> > (geometric?) averages?

> Rémi Coulom answered:
> I learn two sets of gammas separately for the two sets of features.

I don't get it. Why do you need two sets one for the tree and one
for the playouts? To learn gammas, I use a database of games.
The patterns compete, some of them win. This is computed using a
Bradley-Terry model. At that time moves are just moves, not tree moves
or simulation moves. When that offline learned model 'best' fits the
moves played (55000 games x 100 moves each in my case) I am done, I
have a set of gamma values.

I use these for playouts and biasing the tree. What else are you doing?
How do you compute a set for the playouts and a set for the tree?
Do you adjust gamma values one by one playing games?

Of course, I guess this is not very useful for 9x9 that's why I took
the (probably wrong) decision to work in 19x19 only.


Jacques.

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

[computer-go] Kinds of Zobrist hashes

[Jacques Basaldúa]

Álvaro Begué wrote:

> The legal moves might be the same now, but they might be
> different after I perform a particular move.

You are right. Looks like my solution is not perfect, but it
works good enough. I have seen trouble, before I implemented
it, because the transposition table identified the same
position in different situations. My solution worked, but,
as you say it may not be perfect. Anyway, it is good enough
for ko and my version of superko is a simplification restricted
to the last 8 moves. Basically, triple ko and double ko
of a group with one eye are the only superko sequences I have
seen in serious games.

I though it was good, now I have added a remark to the source
code just in case some weird behavior appears. Thanks.

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

[computer-go] Kinds of Zobrist hashes

[Jacques Basaldúa]

1. The 3 hashes:

As Eric Boesch and Álvaro said, you can get the same codes
as in the Black[], White[], Empty[] scenario using only 2
BlackXorEmpty[] and WhiteXorEmpty[]

2. What does make sense is making a difference between a
POSITIONAL hash and a SITUATIONAL hash.

The positional hash is the typical Zobrist hash of just the stones.

The situational hash is the XOR of the positional hash and
all moves forbidden by ko or superko (if any). I use another
table of 361 64 bit codes for each forbidden move. At least,
the tree search must have this in consideration, because
the same stones but different legal moves, it is not the
same position.

I guess most programs do this one way or another.

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

[computer-go] Fuego parameter question

[Jacques Basaldúa]

To run Fuego in Windows, there the build I posted in:

http://www.mail-archive.com/computer-go@computer-go.org/msg12208.html

There is both source and binary. It is 40% faster than the cygwin version
and more efficient in all senses, just because it is a native build.

cygwin has serious limitations. When I did a lot of evaluation using Mogo as
an "oracle" I finally had to use a Linux box, because cygwin is not able to
run more than 15M sims (from Mogo) reliably. (If you run less than 15M
kill the process and run it again you can use it without limits.)

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

Re: [computer-go] still an outstanding command

[Jacques Basaldúa]

I think it is OK to lose the one game where it crashes, but it should  
be able to restart for new games at least.



Martin


You can restart everything Ok, but you have to kill the process java.exe
and then run kgsgtp again.

When the program crashes, the clock is still running, I think.
If it is so, I think it is correct to be able to continue the game.
You lose the time involved and any online learned info. Looks fair to me.

Jacques.

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

[computer-go] [Fwd: Announcement ICGA Events 2010]

[Jacques Basaldúa]

Is it possible to participate in these tournaments remotely? I think I
would like to start participating in these, but I certainly have no
budget (or time) to travel outside of Europe. :-(

Petr "Pasky" Baudis


For the ICGA Computer Olympiad, there should be no problem.

This year all participants except myself used remote computers. I 
carried my i7 to the competition facilities. (I do live in Spain, but

over 2000 Km away from Pamplona in the Canary Islands, so it was
complicated to fly with the computer 3 times.)

Hideki Kato operated his computer in Japan remotely and was also
operator for Zen in communication with Yamato who was in Japan. Fuego 
used a computer in New York (maybe not for all the games), Mogo used 
the Huygens cluster and Professor Chen had his students operating in

the US.

Neither will I be able to travel to Japan (unless I find a sponsor ;-))
and I also expect to participate again with better results, of course. 


Jacques.

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

[computer-go] Fuego 04 native Windows

[Jacques Basaldúa]

I have made a native Windows Fuego build compiled with MS Visual Studio 
2008.


Thanks to the Fuego team for making such a nice program free software !!

I will use it to measure some tree metrics to tune my own program and 
for a validation
experiment for an evaluation function I have developed. I will post 
results when I have any.


To test the binary I made it play on todays KGS tournament and won 1 
game of 3 against

MFOG and 1 game of 3 against Aya + all the other games.

It was running on an overclocked (3.6 GHz) i7.

The settings were:

uct_param_search max_nodes 1250
uct_param_player reuse_subtree 1
uct_param_player ponder 1
go_rules kgs
sg_param time_mode real
uct_param_search number_threads 8
uct_param_search lock_free 1
uct_param_search virtual_loss 1
uct_param_search number_playouts 2

The binary does around 36k games/sec in the opening rising to 50-60k 
later. Which is a lot
more than the 23.5K of the cygwin version. AFAIK it works Ok with 
multithreading with

and without locking. It is also much smaller and has no .dll dependencies.

If someone wants to test it more, it is here:

http://www.dybot.com/fuego04nw/fuego.zip

And the source code Windows developers always dreamt of but were too shy 
to ask ;-)


(All relevant parts of boost included, 0 static lib dependencies, 0 
dynamic lib dependencies,

compiles with MS Visual Studio 2008 0 errors 0 warnings.)

http://www.dybot.com/fuego04nw/fuego.7z

(Compressed with 7z. 7z is free software available at: 
http://www.7-zip.org/
The command line version is the best option if you don't like programs 
integrating in Explorer.)



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

Re: [computer-go] Rules for remote play at the Computer Olympiad

[Jacques Basaldúa]

> About the "thinking process" log.

Enabling debugging options can result in serious performance loss. In my 
system
only the "admin thread" can do such things as tree dumps and that makes 
all other
"pawn threads" idle. I don't think such preventive measures are 
justified. In case
of doubt, it should be enough if the author can show that the program 
can repeat
any suspectful move (even if it does not always play the same move, the 
played
move should at least be among the best). If the program is local that 
should be

enough. Remote programs cannot be controlled anyway. I think adding
constraints to local programs makes the unfairness vs remote programs even
worse. In case something has to be implemented it must be announced in 
advance.


Questions:

1. What are the time settings for 19x19?

2. What are the days for 19x19?

3. Is hardware available from the organizers? At least, monitors and 
keyboards to

avoid flying with non-critical and voluminous equipment.


Jacques.

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

[computer-go] [Fwd: ICGA Events 2009 in Pamplona]

[Jacques Basaldúa]

Good news!

I am very happy the ICGA has chosen Pamplona. Other destinations (e.g. 
Beijing)
are more attractive, but way out of my reach. I can travel to Pamplona 
easily, but
cannot find the details. The website at http://www.icga.org/ is not 
updated and the
attached .eml file contains 2 .pdf files coded by some mail protocol, 
but no mail
program (Mozilla, Outlook) I have tried is able to extract them to .pdf 
files.


Can someone place the .pdfs somewhere for download? Thanks.

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

[computer-go] MoGo v.s. Kim rematch (Jason House's paper)

[Jacques Basaldúa]

> "The approach of this paper is to treat all win rate estimations as 
independent estimators with

additive white Gaussian noise. "

Have you tried if that works? (As Łukasz Lew wrote "experimental setup 
would be useful") I guess
there may be a flaw in your idea, but I am not a specialist. I will try 
to explain it.


If it wasn't for the fact that the tree is learning, the probability of 
a playout through a node to win
would be constant each time the node is visited. This is, of course, a 
simplification because the tree
does learn, but, at least between playouts that are not very distant in 
time, it is true. So my argument
holds to some (I guess, much) extent. The same applies to the RAVE 
estimator which is also the result
of counting wins (assume P(win|that move) = constant) and dividing by 
some appropriate sample size.
Therefore, these estimators follow a binomial distribution. It does 
converge to the normal, but with
some fundamental caveat: Unlike the normal in which mean an variance are 
independent, in this case

the variance is a function of p.

The variance of the binomial = n·p·(1-p) is a _function of p_.

Therefore, the variance of the normal that best approximates the 
distribution of both RAVE and

wins/(wins + losses) is the same n·p·(1-p)

If this is true, the variance you are measuring from the samples does 
not contain any information
about the precision of the estimators. If someone understands this 
better, please explain it to

the list.

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

[computer-go] Counting the final score with seki

[Jacques Basaldúa]

Hi all,

When you detect self atari in the playouts (something I haven't tried 
yet, but
from recent posts in this group I am convinced that it is an important 
issue)

a new problem arises: How can you score the board _fast_ at the end?

My previous version killed all groups in seki and scanned starting from 
a stone

in zig-zag:


<---<-
>^
<---(X)···

and

(X)-->
<|
|>

If the stone is black/white, it starts counting for +1 or -1 and changes 
the sign
when the stone color changes. (Starting from a stone is easy because I 
keep lists
of chains, while starting from a corner would require to find out who it 
belongs

first.)

This way of counting does not require looking for any neighbors and is 
really fast.


But when self atari is avoided in the playouts, groups live in seki and 
counting
dame points really fast is required. Of course, I can imagine how to do 
it using
floodfill, what I want to know is if someone wants to share some better 
approach

if there is one.

Jacques.



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

Re: [computer-go] 10k UCT bots

[Jacques Basaldúa]

Don Dailey wrote:


[EMAIL PROTECTED] wrote:


For those currently coding this up, I think the most important thing 
about this playout algorithm is that it is *temporary*. You will 
almost certainly be?replacing it with something different and better 
just a little bit down the road. So you probably don't want to worry 
about hair-splitting tweaks except as an academic exercise.
  


Yes,  I agree. Also  my hair brained scheme of pre-generated tables of 
list traversal orderings was just an academic exercise as you say. 


But the problem is that when you do heavy playouts you have the same
problem except that the probabilities of the legal moves are no longer 
equal. Unless, of course, the board system keeps a list of legal moves, 
not just empty points and own eyes in playout mode have zero score which

is the same as if they were illegal moves. Am I the only one doing this?

I don't know if the impact is measurable in strength or not. But as the
game advances, the own eyes are found in the root position. When that
happens, the bias applies to the same move in all the playouts. In this
case the program is favoring systematically the exploration of a move
for no reason at all and it is always the same move. Since the number 
of simulations is limited, that pays less attention to other moves.

I don't know if it is bad, but at least it is ugly. ;-)

Jacques.

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

Re: [computer-go] Paper for AAAI (David Silver) PDF problem

[Jacques Basaldúa]

Thanks, Hideki

> I have the same problem with version 7.0.7 of Adobe Reader but
> version 8.1.2 works fine.

That was the problem. I used the automatic upgrade "feature", but that
only upgrades to the latest 7.xx version not to version 8.xx.

Don Dailey wrote:

"... this general distaste of feeling like a sucker for Microsoft."

That's the real problem with Windows. I need a double boot, place the OS
on a FAT32 partition and have a copy of every file + an image of the 
installed

partition. Every day I fight against the operating system I have paid for
and if the OS doesn't let me change it the nice way I have to do it the
hard way. If I was starting now, I would be a Linux user.

Unfortunately, there is not much I can do with incompatible systems.
From time to time I install wine to see how far they are. If it can be used
or not.

Windows 95 could be purchased in floppy disk and that was 30 floppies
the operating system of my dreams is Windows 95 bug free in 20 floppies ;-)

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

Re: [computer-go] Paper for AAAI (David Silver) PDF problem

[Jacques Basaldúa]

Hi David

http://www.cs.ualberta.ca/~silver/research/publications/files/MoGoNectar.pdf

Your paper has a PDF problem concerning "embedded font BXGQFO+CMR12". I 
have used
different versions of Adobe Reader. I even updated one of the computers 
to the latest version
and I still cannot read any mathematical expressions. I guess this 
applies to all Windows users.


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

Re: [computer-go] State of the art of pattern matching

[Jacques Basaldúa]

Jonas Kahn wrote:

> I guess you have checked that with your rules for getting probability
> distributions out of gammas, the mean of the probability of your move 1
> was that that you observed (about 40 %) ?

If I understand your post, there may be a misunderstanding by my fault.
Here gamma is not a gamma function nor a gamma distribution but a constant.
It is just the same Greek letter. I don't remember if it was in 
Crazystone's

description or in some other paper I read to understand what Bradley Terry
models are, I just got used to that notation.

The best thing of BT models (for me) is the extreme simplicity at runtime
(calibration may have more black magic) so:

  prob of move i = gamma[i] / SUMj gamma[j]

where gamma[·] is a constant each pattern has. Setting those constants is
the learning process.

The 40% is obtained between move 20 and 119 of over 55K games. That is more
than 5 M competitions. The patterns are learned for other move numbers as
well. It considers the urgency modified by the first time the pattern 
appears.

Also ko, but ko is learned to (hopefully) find ko threats, its impact on
guessing is less important. It counts the number of times the first move
was the right move, then the first + second, etc.

The reason why two different ways of measuring the same:

a. Probability expected for each move.
b. Number of guesses of the best move, 2nd best, 3rd best, etc.

don't match is mainly academic, because form a practical point of view, the
important is to have a good move generator and (even more important) to
understand its limitations. It cannot be considered as the only source of
moves, but the first moves in terms of urgency are moves that should be
paid attention.

I admit, that what I call a probability distribution over the legal moves,
is not really balanced I don't understand why, but, nevertheless, in terms
of urgency, better moves get higher urgency. This is all I really need.
Of course, I would welcome an explanation on why the 2 things don't match
or if someone else can verify if his patterns give correct values.


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

Re: [computer-go] State of the art of pattern matching

[Jacques Basaldúa]

Hi Lukasz

In Rémi's paper about Bradly Terry models he found a way to give a
comparable gamma score to things that were different, for instance:
capturing a stone v.s. a given 3x3 pattern.
His model is much more general, but has less patterns (not at all
around 200K patterns of my system). Additionally, my mask pattern
only system has a reasonable a priori value:

times_played / (times_played + times_postponed).

But there is an additional issue handled by Rémi's system that is
ignored by the naif system: The fact that some competitions are
much harder than others. If the sum of concurrent scores to the
average competition is, say 100, the value of winning a competition
of sum 40 is obviously much less than winning one of sum 300. That
is not included in the simple formula. Therefore, a simple intuitive
idea if adding more for a the hard competition 300/100 and less for
the easy one 40/100. Because there is a feedback as when you change
the scores you are also changing the sums of concurrent scores, there
are so many variables to adjust ~200K and the a priori values are
already reasonable, I prefer to adjust doing small steps since
this is an offline process and speed is irrelevant.

The hits of each move don't change that much.

At the beginning of the adjustment:

Hits of move 1 = 0.382405 acc = 0.382405
Hits of move 2 = 0.113530 acc = 0.495935
Hits of move 3 = 0.067430 acc = 0.563365
Hits of move 4 = 0.048055 acc = 0.611420
Hits of move 5 = 0.036304 acc = 0.647725
Hits of move 6 = 0.028978 acc = 0.676703
Hits of move 7 = 0.023769 acc = 0.700472
Hits of move 8 = 0.019793 acc = 0.720264
Hits of move 9 = 0.016693 acc = 0.736957
Hits of move 10 = 0.014164 acc = 0.751121


At the end of the adjustment: (Additional steps don't
improve further, some value may even decrease.)

Hits of move 1 = 0.409278 acc = 0.409278
Hits of move 2 = 0.115598 acc = 0.524877
Hits of move 3 = 0.062659 acc = 0.587536
Hits of move 4 = 0.044014 acc = 0.631550
Hits of move 5 = 0.033681 acc = 0.665230
Hits of move 6 = 0.027696 acc = 0.692926
Hits of move 7 = 0.022885 acc = 0.715811
Hits of move 8 = 0.019029 acc = 0.734840
Hits of move 9 = 0.015758 acc = 0.750598
Hits of move 10 = 0.012886 acc = 0.763484

What I call the distribution is this: The gamma value of each legal
move defines a probability distribution function over the legal moves.
If we had no information (uniform random distribution) we would expect
that with 20% of the legal moves we hint 20% of the times, etc. So
for 0.1, 0.2 .. 0.9 of the legal moves we hit around 0.1, 0.2 .. 0.9.
Now, what happens when we use our pdf over the legal moves? We can
get 10%, 20% 30%, etc with very few move candidates. But, if the
first move has say 0.17 and the 1+2 = 0.21 and I want to get 0.2
If the first is a match, count 1, if the second is a match count
3/4 = (0.2 - 0.17)/(0.21 - 0.17) if any other move is a match count 0.
Do I really get 0.1, 0.2, .. 0.9, of course, with much less moves ?

No. for a reason I don't understand, I get something like:

Distribution fit expected 0.1 found 0.153164
Distribution fit expected 0.2 found 0.298602
Distribution fit expected 0.3 found 0.433074
Distribution fit expected 0.4 found 0.551575
Distribution fit expected 0.5 found 0.651135
Distribution fit expected 0.6 found 0.727419
Distribution fit expected 0.7 found 0.776876
Distribution fit expected 0.8 found 0.804008
Distribution fit expected 0.9 found 0.823292

So my distribution is distorted, when I try to get 30% of
the "guessing chance" I get 43.3%, but when I try to get
90% I get 82.3%. I don't know why.


Jacques.

Łukasz Lew wrote:


On Sat, Mar 29, 2008 at 3:47 PM, Jacques Basaldúa <[EMAIL PROTECTED]> wrote:
 


Mark Boon wrote:

> I suppose there's no reason why  it has to be assembler,
> you could just as well generate C-code.

I don't think so. But I don't write that much asm as it may appear.
I see what the compiler writes when I debug and write critical
parts only. And automatically generated code.


> I don't see yet how you go from there to finding patterns.

Depending on the mode, it computes either the hash or the mask.
That mask has to be translated into urgency by a table search.

(Btw. urgency is not just:

  times_played / (times_played + times_postponed)

but that value is used as an a priori value for Bradley Terry
models as Rémi introduced. My adjustment is not as advanced
as what Rémi describes. I just give a weight to a competition
based on the sum of the competing gamma values, and that gives
me another point:

SUM weights_of_played / SUM weights_of_played + weights_of_postponed
   



Can you tell how you came with such an equation?
Does it improves much?

Thanks
Lukasz

 


And I advance a step (like 1/4 of the distance) in that direction
and use the new point as the current value. Iterating this way
improves the wins of the best move but distorts the distribution
(I extract lots of statistics at

Re: [computer-go] State of the art of pattern matching

[Jacques Basaldúa]

Mark Boon wrote:


>There are 16 4-distance points, so if you spill ino that by one
> point you get 315 or a little over 14 million patterns. Multiplied
> by 3 for every don't-care point within less than 4 distance. Ouch.

True, but the number of patterns is learned automatically. When I
first learn the 55K+ games, there are so many patterns that I can
only create a pattern file of less than 2000 games. I create 32
such files an call "importance" the number of files in which each
pattern is found. (a value from 1 to 32). The number of patterns
are:

# of imp = 32   97132  (97132)
# of imp = 31   26493  (123625)
# of imp = 30   21460  (145085)
# of imp = 29   19335  (164420)
# of imp = 28   18415  (182835)
# of imp = 27   18703  (201538)
# of imp = 26   18619  (220157)
# of imp = 25   19345  (239502)
# of imp = 24   20390  (259892)
# of imp = 23   21611  (281503)
# of imp = 22   22959  (304462)
# of imp = 21   24675  (329137)
# of imp = 20   26808  (355945)
# of imp = 19   29081  (385026)
# of imp = 18   31938  (416964)
# of imp = 17   35319  (452283)
# of imp = 16   39188  (491471)
# of imp = 15   43899  (535370)
# of imp = 14   50391  (585761)
# of imp = 13   57259  (643020)
# of imp = 12   67062  (710082)
# of imp = 11   79013  (789095)
# of imp = 10   95292  (884387)
# of imp =  9  117109  (1001496)
# of imp =  8  147810  (1149306)

Depending on the threshold value used (and also the number
of times the pattern is seen) I can create databases from about
100K patterns to 1M patterns, more than that means including
patterns that are too seldom, their urgency information won't be
very accurate either due to the small sample size.

Jacques.

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

Re: [computer-go] State of the art of pattern matching

[Jacques Basaldúa]

Mark Boon wrote:

> I suppose there's no reason why  it has to be assembler,
> you could just as well generate C-code.

I don't think so. But I don't write that much asm as it may appear.
I see what the compiler writes when I debug and write critical
parts only. And automatically generated code.

> I don't see yet how you go from there to finding patterns.

Depending on the mode, it computes either the hash or the mask.
That mask has to be translated into urgency by a table search.

(Btw. urgency is not just:

   times_played / (times_played + times_postponed)

but that value is used as an a priori value for Bradley Terry
models as Rémi introduced. My adjustment is not as advanced
as what Rémi describes. I just give a weight to a competition
based on the sum of the competing gamma values, and that gives
me another point:

SUM weights_of_played / SUM weights_of_played + weights_of_postponed

And I advance a step (like 1/4 of the distance) in that direction
and use the new point as the current value. Iterating this way
improves the wins of the best move but distorts the distribution
(I extract lots of statistics at each step) so I stop rather early.)

The macro for searching in an ordered list is an efficient
implementation of the "canonical method".



void locate(float xx[], unsigned long n, float x, unsigned long *j)
{
   unsigned long ju,jm,jl;
   int ascnd;
   jl=0; //Initialize lower
   ju=n+1; //and upper limits.
   ascnd=(xx[n] >= xx[1]);
   while (ju-jl > 1) { // If we are not yet done,
   jm=(ju+jl) >> 1; //compute a midpoint,
   if (x >= xx[jm] == ascnd)
   jl=jm; // and replace either the lower limit
   else
   ju=jm; // or the upper limit, as appropriate.
   } // Repeat until the test condition is satisfied.
   if (x == xx[1]) *j=1; // Then set the output
   else if(x == xx[n]) *j=n-1;
   else *j=jl;
} // and return.



Improvement 1: Instead of if/else, use conditional moves.

Improvement 2. Since when the value is not found, the while
loop has a fixed number of iterations for a fixed table size,
unroll the loop as a sequence of iterations. As mentioned,
an iteration has only 8 instructions.

Improvement 3: When the value is found, break.
(That wouldn't come for free in C it would
require a additional "if (x = xx[jm] )" )

   moveax, ebx
   addeax, ecx
   shreax, 1
   andal,  0fch   ;; Align to a valid pointer
   cmpedx, [eax]
   jz&name&out
   cmovc   ecx, eax;; This is true if [eax] > value
   cmovnc  ebx, eax;; This is true if the previous is false

Here ecx is a pointer to xx[jl], ebx is a pointer to xx[ju],
edx is x and eax is a pointer to xx[jm].

> I assume you allow some of the points to be undefined
> (also called 'don't care points') but I don't see how. And
> if you allow undefined points, why would you need masks
> of smaller manhatten distances?

I don't use don't care. I mask code in 2 bits: void, own,
opponent, out_of_board. This produces bigger database size,
because the only way to introduce "don't care" is to repeat the
pattern. Since my patterns are learned automatically and database
size is not a problem at all, I didn't see the need of don't care.

The bigger patterns have the disadvantage that around move 150
2/3 of the legal moves have unknown patterns. The smaller distances
improve this. I don't know yet if that is required, because patterns are
mainly intended to break the ice, when complex  shapes emerge, the
moves suggested by the search may be much better candidates.

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

Re: [computer-go] State of the art of pattern matching

[Jacques Basaldúa]

terry mcintyre wrote:


It is possible to get some remarkably high correlation
between the moves played by pros and a predictor - yet
still not have a good program. Why?



We have a random variable, the place at which a player
plays, and some variables that we can compute. The
distribution of the random variable, depends on this 
variables. Our variables are shape urgency and life.


Of course, I agree that it would be great to include
life in our statistical model. It would be a much better 
model. The problem is we can compute shape in few clockcycles

but we cannot compute life/death. (The revised Benson methods
are of no use in real games because they detect life/death 
when it way too late.)


All the pattern logic is not intended to determine what
move has to be played, but only to select candidates for 
later methods. Also, it is not about what a player did

once, but what is statistically sound in over 10 M positions.
We ignored life/death when learning and we ignore it
when we just suggest the best moves in terms of shape.
That is fair, but, of course, the interaction between 
shape an life would change things for better.


UCT methods are (among other reasons) strong in 9x9 
because a random move (not in the first 2 lines in the 
beginning) is a reasonable move, and then the stochastic

parts of the search finds good candidates (RAVE and similar).

But in real go, there are 361 legal moves for move 1!

And CrazyStone (as far as I know still the strongest 19x19 
program) is "still" 2 kyu. That is the state of computer go 
in 2008, not the remark made by a pro about how hard it was

to beat mogo by 9 stones.

Most people in this list seem to be against human learned 
shape, but the truth is that we don't know if it is useful
or not. That depends on the price we pay for urgency. In 
terms of RAM it is a couple of tenths Mb, that's nothing 
today, it was a lot years ago. Some people assume that you 
can predict what airplane society would be without building 
an airplane. Just move people in a bus, the airplane is the 
same only faster. That's not how things work. Unfortunately, 
you have to build an airplane to see what it can or cannot do.

Some call it overengineering, but if it is not fast, then
I agree it will be useless almost for sure.


Jacques.

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

Re: [computer-go] State of the art of pattern matching

[Jacques Basaldúa]

Mark Boon wrote:

Sorry, without a bit more explanation, the assembler code is very  
hard to understand. What exactly does it do?


The first source code was just an example to see what kind of code
is generated. The second is useful, if you understand asm you should 
understand it. The board has 4 modes, as far as patterns are concerned.
So the following applies for each mode and for each possible mapping 
scheme. When 40 neighbors are used, (i.e. Manhattan distance 4) there 
are 81 possible situations (all the cells of a 9x9 board are different 
as far as board limits are concerned). On bigger boards, each cell maps 
one of the 81 possible 9x9 cells. The board system cannot play on less 
than 9x9. And for each of these 4x(maximum)81 (some board modes have 
smaller distance) the generator writes 2 functions: one for creating 
the mask/hash from scratch and an other to update all masks/hashes 
in the neighborhood of a new stone.



Does it relate to a pattern? 


Yes the complete pattern is:

   +---+
   | 4 |
   +---+---+---+
   | 4 | 3 | 4 |
   +---+---+---+---+---+
   | 4 | 3 | 2 | 3 | 4 |
   +---+---+---+---+---+---+---+
   | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
| 4 | 3 | 2 | 1 | · | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
   | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
   +---+---+---+---+---+---+---+
   | 4 | 3 | 2 | 3 | 4 |
   +---+---+---+---+---+
   | 4 | 3 | 4 |
   +---+---+---+
   | 4 |
   +---+

Justification of this shape:

1. It includes all standard nobi, iken tobi, niken tobi, kosumi, 
keima & ogeima relations (+ double iken tobi + double kosumi)
2. It detects if a pattern is at the 4-th line or the 4x4 corner 
(and below obviously). Less than that is too small.
The 4-th line is too different from the center. 
3. It is a nested structure, {dist12, dist12 + dist3} are both usable.

4. It has reasonable size for the information it contains.
5. The bit arrangement is optimized for 90 deg rotation.

Additionally, I keep urgency information for: normal, the pattern
shows up for the first time and urgency in a ko.



Did you write a paper or post explaining this in more detail?


Not yet.



Do I understand correctly that you generate this code automatically?


Yes. It would be a nightmare to write about 70K lines by hand and 
debugging would be hard as well. Although what the functions do is

simple enough to create a test that verifies 100% of the cases.


You are talking about updating 40 hashes. Does it mean your patterns  
have fixed size? 


Yes. 3 sizes: Manhattan distance 2, 3 and 4


In the 500 nanoseconds, how many patterns do you compare? 


That was updating (max) 40 hashes in the neighborhood of a newly 
placed stone. The precise number of hashes depends on the board
coordinate and the surrounding stones although that is achieved 
without a single conditional jump. (It is a very conservative 
estimation for approx 140 instructions in a jump free sequence. 
The typical case is probably more like half of that.) But, as 
mentioned, it does not include neither the board logic nor the

search that translates hash -> urgency.


How about rotations and color inversions? 


In the slowest mode the pattern is rotated using macros like this 
one (that rotates a 40 neighbor pattern)


   asm
   mov edx, eax// @jm
   mov eax, [edx + 8]  // jm.mask4
   rol eax, 8
   mov [edx + 8], eax  // jm.mask4

   mov eax, [edx + 4]  // jm.mask3
   shl eax, 6
   mov ecx, eax
   and eax, 0ffh
   rol ecx, 8
   or  al, cl
   mov [edx + 4], eax  // jm.mask3

   mov eax, [edx]  // jm.msk12
   mov ecx, eax
   shl eax, 4
   rol cl, 2
   mov al, cl
   mov ecx, eax
   shr ecx, 16
   and eax, 0ffF0FFh
   and ecx, F00h
   or  eax, ecx
   mov [edx], eax  // jm.msk12
   end

and converted to canonical. Color inversion is automatic
because the pattern is own/opponent instead of black/white.

In the fastest mode, the hash table has x8 size and includes
the hashes of the rotated patterns.


Jacques.



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

Re: [computer-go] State of the art of pattern matching (Oops)

[Jacques Basaldúa]

"Santiago" wrote:

... Oops, wrong name ...

(Santiago is my official name, because I was born in a dictatorship that 
did not allow foreign names. After that, I was too lazy to change it.

Jacques, like my French grandfather, is my real name.)


Jacques.


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

Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])

[Jacques Basaldúa]

> Petr Baudis wrote:

> >> MoGo can indeed play out some rather spectacular ko fights;
> >> unfortunately, I couldn't find any quickly, so here is at least an
> >> example of a shorter one.

> I see you made the following comment in that game record, which seems
> relevant to recent discussions here.

> | mogo excels at reducing clear winning positions to close games they
> | lose because of botched up tsumego

> Is it mogo botching up the tsumego or its opponents? Do you have any
> example game records for this?

You won't find that in computer vs computer games, because "tricking" the
strong programs requires some go skill and it only works if you wait long
enough before you "solve" the position. But if you search KGS (LeelaBot,
CrazyStone, CzechBot) for even games where the bot lost against a kyu
players you will find many. All go more or less like that:

A 4-6 kyu human is behind by 10-15 points in the midgame (at that stage the
probability of winning is correlated with territory, so the MC bot is
building fine.) He creates a 12-16 point worth nakade trick in a corner
and does not solve it.The bot is happy, it thinks a bulk five is alive or
something like that. Perhaps the human sacrificed another 15 points
somewhere to create the trick so he should be dead lost. But, he only
has to play on, reduce, etc. As the endgame approaches, the MC bot
allows the reduction only until the territorial balance would change the
winner. The player is happy, he turned a 25 points loss into a 1.5 point
loss (assumed by the program) and has a 12 point surprise.
At the end, when the whole board is decided, the player kills
the bot's group and the bot turns a sure win into a sure loss and resigns.

Because the trick can only be played by similar strength players (much
weaker players can't build something like that, much stronger don't need 
it)
it affects the rating of the bots. I guess CrazyStone could be near KGS 
1dan
with that solved. It is 2k now. But, of course, the solution may not 
come at

the price of making the program weaker. That is the difficult part.


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

Re: [computer-go] Way MC plays

[Jacques Basaldúa]

Don Dailey wrote:


I personally have serious doubts about knowledge extraction from human
games, but I hope you have success.I think you can get more from
computer games of strong players even though the level is weaker. Here
is why I say that:



1.  A strong computer still plays a lot of good moves - so the delta
between human and computer games is not as high as you think.


2.  A certain consistency in computer games that humans don't possess. 



3.  You have access to the internals, such as a score that quantifies
moves.


My idea combines offline knowledge with MC methods. So there is a lot
of online computer generated knowledge. I don't pretend to make a dumb
savant program, just playing the only move it finds in a joseki database.
But if the program considers the joseki stored in (state, action[i-1]) 
-> action[i] records. It will immediately start searching a tree whose

first move at all depths is the joseki sequence. If the joseki depends
on a ladder, it will find that ladder much earlier and if it is not good
it will hopefully play something else. At blitz time settings, playing 
the wrong  joseki is bad but not terrible. That would be about the level 
of a human dan making a mistake in a blitz game, still better than current 
programs.


In this context, human knowledge produces a priori values for UCT. (The 
exact formula of the MC tree search is not yet decided.) There is enough
computer generated knowledge in the search. When the end of the game 
is still 200+ moves ahead, the search alone does not find enough 
difference between good and not so good moves.


The knowledge, I think, makes sense to extract is:

1. (state, last move) -> (next moves list) records (joseki or places
to play when the last move is somewhere else.)
2. urgency of shapes
3. distribution of statistics (e.g. proportion of times tenuki is played 
at move n) that helps making playouts more humanlike while still fast.
I finally abandoned full board Bradley-Terry scored random playouts. I 
draw a random number to decide if tenuki should be played, if true I 
invent a random move and use it as if it was the previous move. Else,
I play a Bradley-Terry scored random move in the 40 neighbors of the 
last move. That is almost immediate in my hologram board system because

I store the mask. On other implementations it may not be so good.

About urgency of shapes:

The urgency of a BT adjusted 40 neighbors shape hits 40% in a 10 M+ sample 
with about 160 K patterns. (Overlearning should not be very important

given the lack of degrees of liberty.) It hits 66% with the first 5 moves.

Hits of move  1 =  0.402048 acc =  0.402048
Hits of move  2 =  0.117102 acc =  0.519151
Hits of move  3 =  0.065450 acc =  0.584600
Hits of move  4 =  0.045592 acc =  0.630193
Hits of move  5 =  0.035190 acc =  0.665382

That sounds great news. But there is bad news of course. That doesn't go any 
further. To reach 80% it needs 14 moves


Hits of move 14 =  0.006206 acc =  0.801095

And to reach 90% it needs 96 moves!

Hits of move 96 =  0.001323 acc =  0.900994

Shape is a factor that explains, perhaps 2/3 of the moves (shape alone about 
40%, but shape "in the right place" a little more than 66%). Not less and
_not more_ than that. It is naive to think that the 12th move in terms of 
shape is better than the 50th. But, imagine there are 250 legal moves, the 
248th is a really bad move. 

Can shape make a difference? I don't know. If its slow, surely not. If it 
is almost free in terms of performance as in my board system, I hope it does.



Jacques.


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

Re: [computer-go] Way MC plays

[Jacques Basaldúa]

Jonas Kahn wrote:

> I mean, if Crazy Stone played against himself from the position where
> Katsunari was thought to be ahead, would he win with its original color,
> or with Katsunari's ?

That is a very big question. I hope it would win with Katsunari's stones 
*if*

Katsunari was really ahead. I have been now working for some months in
knowledge extracted from over 50K games played by pros and high dan
players (both players), enough time, no handicap. I don't know for sure
if that was not in vane yet, that's why I write "I hope".

I certainly don't have a high opinion on any of the strong program's fuseki.
These programs are not strong for their fuseki, I think, they are strong 
for

many reasons and their fuseki is not really as bad as it looks. But I guess
there is a lot of margin for improvement there.

After the success of MC based programs some people argue that
computers should play intrinsically different from humans and that
computer play is superior. I don't share that opinion. I think that all
what humans have elaborated on fuseki makes a lot of sense, when
you apply it, you improve a lot. I don't see a reason why that would
not apply to computers.

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

[computer-go] Re: 19x19 Study. Nakade is difficult

[Jacques Basaldúa]

I mentioned nakade in a list including "not filling own eyes". Perhaps,
not "filling own eyes" is a simpler example:

| . . . . . . .
| . # # . # . .
| . O # . # . .
| O O O . # # .
| # # O O O # .
| . # # . . . .
 ---

(Unless I made a mistake: Black to play and a1 is the only move killing
white.)

All MC programs avoid eye filling. I am not claiming that this is a wrong
decision. It has been tested, it is the correct decision. It is not a bug
that can't be fixed, either. If white is blind to the a1 move, then it is
happy with this position because it thinks it is unconditionally alive.
Therefore, it should not be impossible to force white to make this shape
because white likes it.

If no program understands this, white is alive and the game continues as
if a1 was illegal. A program that finds a1 changes all.

It is not a question of limiting the move in the playouts or in the tree.
The playouts make an evaluation function, if they are systematically wrong
the tree won't expand in that direction in advance. Playing go is about
reading the problems before they happen. A program that does the playouts
systematically wrong and the tree right, may be a good tsumego solver, but
not necessarily a good player, because it won't see it coming.


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

Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study

[Jacques Basaldúa]

Dave Hillis wrote:

> I've noticed this in games on KGS; a lot of people lose games
> with generous time limits because they, rashly, try to keep up
> with my dumb but very fast bot and make blunders.

What Don says about humans scaling applies to humans making
an effort to use the time they have, but when we play on KGS
after a hard work day, we (I guess a lot of people like myself,
including my opponents and the players I watch) play for
pleasure. We avoid too fast settings, because it introduces
unnecessary pressure, and we hate too slow because it makes
the game endless. We play _independently of the remaining time_.
Most moves fast, and from time to time we ponder 10 to 20 seconds.

That's why KGS time settings for humans have to be taken with a
grain of salt.


About Don's arguments on self testing:

I would agree at 100% if it wasn't for the known limitations:
Nakade, not filling own eyes, etc. Because the program is blind
to them it is blind in both senses: it does not consider those
moves when defending, but it does not consider them when attacking
either. Your programs behave as if they were converging to perfect
play in a game whose rules forbid those moves. But these moves are
perfectly legal! At weak levels, there are more important things
to care about, but as the level rises there is a point at which
understanding or not understanding these situations makes
the difference. A program that understood these situations,
but had some other small weakness could have strong impact
in the ratings. Perhaps, Mogo12 and Mogo16 would not be so
different in their chances of beating that program as they
are in beating each other.


Jacques.

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

Re: [computer-go] New scalability study : show uncertainty ?

[Jacques Basaldúa]

I don't think "only uniformly random playouts will scale to 
perfection" because what we need for playouts is not just a simple 
average of final scores but a maximum (in negmax sense) score.  It 
should be the perfect evaluation function.


In other words, as MC simulation is a way to get an average of a 
value, when applying it to optimization problems we need some way to 
focus the simulations to the _peak_ in a state space.


It may be obvious when one consideres L&D problems where the best move 
that leads to the maximum score (live) is only one and all other moves 
are bad.  At such positions it's almost no sense to simulate all legal 
moves with same probability.  So, IMHO, biasing simulations is not 
just a speed-up technique but is essentially important.


I agree, but what I meant about uniformly random playouts is the following:
What makes a move outstanding is being unpredictable. For a total novice,
playing at the key point of a bulky five may look like a touch of genius,
but when you learn a little, its an obvious move. The difference between a
5p and a 9p may be one or two moves nobody can predict (except a 9p). When 
we add knowledge we find the _ordinary_ good moves faster, we make weaker 
moves less probable, but that comes at a price, the price of making outstanding 
unpredictable moves less probable also. Perhaps that introduces a ceiling. 
I thought that was what you were also pointing. Of course, I don't claim 
uniformly random playouts are good, I just claim that they should (just as an 
infeasible theoretic argument) scale to perfection, of course that scaling 
doesn't have to be linear.


Jacques.


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

Re: [computer-go] mathematical morphology

[Jacques Basaldúa]

Erik van der Werf wrote:


You may also be interested in my
article on estimating potential territory 


I am. Can you post a link, please.

Jacques.

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

Re: [computer-go] New scalability study : show uncertainty ?

[Jacques Basaldúa]

Hideki Kato wrote:


It's rather odd.   I'm checking the log file and then I will check the
source code to see if I have some artificial limits in there.



Why odd?  It all depends on the bias or policy of simulations.  If 
there is a flaw in the policy, the score will converses to the score 
with some error, which will introduce some limit of scalability, isn't 
it?


That is a very good point. Perhaps it is not the case with FatMan, 
but that may surely happen. In this study no program is playing with 
uniformly random playouts and perhaps only uniformly random playouts

will scale to perfection. Of course, I can imagine that reaching the
strength of Mogo_13 with uniformly random playouts can require a 
number of simulations that is not feasible. So I don't have any idea

about how to improve the study, but this is a serious limitation that
has to be considered: If you find some ceiling, the ceiling may be 
attributed to the playout policy, not to UCT.


Jacques.

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

Re: [computer-go] 19x19 cgos ranking page

[Jacques Basaldúa]

Olivier Teytaud wrote:

> the 19x19 CGOS ranking page is back (but might be still unstable)
> and Leela seemingly performs quite well.

> The crosstables will come back soon also.

The crosstables are back, but the sgf archives ar not.

I get:

"Forbidden

You don't have permission to access /~teytaud/SGF/2008/01/19/12664.sgf 
on this server.
Apache/2.2.3 (Debian) mod_python/3.2.10 Python/2.4.4 PHP/5.2.0-8+etch9 
Server at persowww.lri.fr Port 80"


When fixed, please keep last week's games for a while. I was looking for 
game 12338 (I am not sure if that number is correct)

and don't know the day it was played either.

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

Re: [computer-go] Suicide question

[Jacques Basaldúa]

Hi Michael


Another cost is undo. Superko requires undo, unless
you want store a hash value with each chain of stones.
I am not sure exactly what undo costs, but lets say
5% to 10%.


Well, every implementation is different. In its slowest 
mode, my board stores information about neighbor stones 
in each cell. It has a stack of boards and each board has
a pointer to its parent. In that mode superko can be 
detected. There is also a faster mode for MC playouts
that does not support superko. But it could also be 
possible to maintain a stack of previous hashes i.o.

complete boards, that would not be very expensive.

Jacques.


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

Re: [computer-go] Suicide question

[Jacques Basaldúa]

Michael Wing wrote:


In my program (which implements undo), the cost of
for suicide detection is around 1%, which means it
would lose 1.5 ELO points.


In programs that somehow maintain lists of legal moves
or even probability distribution functions over the legal 
moves, avoiding suicide is free. I fact, adding the 
suicide move to the list would cost.



On the other hand detecting superko costs more like
6% or so, which costs 9 or more ELO. So a benefit
of 1 ELO for doing superko right may not be worth
the cost.


I guess you mean a bullet proof test from the beginning
of the game. I only test the last 7 moves (if enabled, 
it can also be disabled) and that does not cost much.


The reasons why I use 7 moves are 2:

* I have never found among strong players a need for
repetition other that triple ko and double ko on a 
group with no eyes. (Both are 6 moves long.) My point
is: If the program is so weak that it does silly 
repetitions, improve something else. If it is so strong

that it has the same problems as strong humans, detect
superko.

* My hash system can use only half of the hash (32 bits)
and detect the collision with probability 1. (Because of
the properties of the keys, you need at least 8 keys 
for a combination of keys giving zero.)


A reason I can figure for ignoring repetition in the 
playouts is: If the playouts are random, it won't happen 
much anyway. The probability of a repetition of 6 random 
moves is too small to care about. But in real play it is

frequently a fight for the game. The player forced to
avoid the repetition will resign if it is about the 
life of a big group.



Jacques.


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

[computer-go] Suicide question

[Jacques Basaldúa]

Gian-Carlo Pascutto wrote:

> Multi-stone suicide is allowed, single stone not.

I hadn't even considered suicide.(It would be a major change for me,
as neither my Gui nor my board system allow such moves.)

The question is Why do you do it?

a. Just in case you wanted the entire program to support suicide go

or

b. Because that has some advantage as a random playout.

If it was b, can anyone explain why suicide is a better evaluation for
a normal (non suicide) game.

Jacques.


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

Re: [computer-go] cgos from windows

[Jacques Basaldúa]

I think you are right about the tclkit exe.  I used the one that the
instruction page linked, which does throw up a GUI if you run it with
no args.



I wonder if it even works.



It appears to be a way to cripple the server.


It does work. I have played over 600 games with it. It does not write
any log files. If your gtp interface can do it, that's not a major problem.

Jacques.

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

Re: [computer-go] How to get more participation in 19x19 CGOS?

[Jacques Basaldúa]

Don Dailey wrote:

My suggest to Olivier is to compromise and set time 
control 20 minutes per side and give 1 second gift.


That's good for me. Until now, I have been running tests 
and gnugo clones just to support the server, but I will

start serious work soon. I have some time for computer
go at last! I cannot use the 9x9 server, because my 
approach is very knowledge oriented. 


Jacques.

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

Re: [computer-go] Is CGOS sending TIME_LEFT?

[Jacques Basaldúa]

Hi Don

> I noticed that your list is upper-case. This might be the problem. I
>don't remember if GTP is case sensitive or not, but I'm pretty sure
> cgos requires lower case in these commands.

Thank you. That was the problem. It was uppercase. To make it
case insensitive, I convert all input to uppercase when I preprocess.
So my names are declared uppercase. A stupid example of trying
to amend something and actually breaking it. It works fine now.

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

Re: [computer-go] Is CGOS sending TIME_LEFT?

[Jacques Basaldúa]

Hi Don


The client does not sent time_left unless time_settings is also
implemented.So your engine must also implement time_settings which
is needed to inform your program of the level it will be playing at.


I do implement time_settings. The server only sends a list_commands at the
beginning and sends no time_settings either. What you can see in the logs is 
all I get, except the first list_commands. That is called only once, when

the tcl interpreter loads the gtp end. I do not implement any KGS
specific extensions, no undo, no handicap, no debugging functions 
(the gui already has debugging utilities). Is any of that required?


Jacques.


This is my complete list of commands:

list_commands
= BLACK
BOARDSIZE
CAPTURES
CLEAR_BOARD
ECHO
ESTIMATE_SCORE
FINAL_SCORE
FINAL_STATUS_LIST
GENMOVE
GENMOVE_BLACK
GENMOVE_WHITE
GET_KOMI
KNOWN_COMMAND
KOMI
LIST_COMMANDS
NAME
PLAY
PROTOCOL_VERSION
QUERY_BOARDSIZE
QUIT
TIME_LEFT
TIME_SETTINGS
VERSION
WHITE

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

[computer-go] Is CGOS sending TIME_LEFT?

[Jacques Basaldúa]

Hi..

My gtp program does not receive any "time_left" commands. I have checked 
that the command is listed without mistakes in list_commands. I even 
tried CGOS 9x9 and I get the same sequence.


Jacques.

--
This is a 19x19 game start (after the first list_commands) Ignore the 
lines containing GoKnot, that is the communication between the gtp end 
and the gui.


 42.842 |- server -> "boardsize 19\cr\lf"
 43.152 # -> GoKnot8 [13 00 00 00 00 00 02 00]
 43.242 # GoKnot -->   4 [ff 00 00 00]
 43.242 |- gkGTP --> "= "
 43.242 |- gkGTP --> "\cr\lf\cr\lf"

 43.312 |- server -> "clear_board\cr\lf"
 43.332 # -> GoKnot8 [13 00 00 00 00 00 02 00]
 43.443 # GoKnot -->   4 [ff 00 00 00]
 43.443 |- gkGTP --> "= "
 43.443 |- gkGTP --> "\cr\lf\cr\lf"

 43.533 |- server -> "komi 7.5\cr\lf"
 43.563 # -> GoKnot8 [00 00 f0 40 00 00 03 00]
 43.623 # GoKnot -->   4 [ff 00 00 00]
 43.623 |- gkGTP --> "= "
 43.623 |- gkGTP --> "\cr\lf\cr\lf"

 45.836 |- server -> "genmove b\cr\lf"
 45.896 # -> GoKnot8 [ff ff ff ff 00 00 0c 00]
 45.976 # GoKnot -->   4 [ff ff 00 00]
 45.976 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 46.036 # GoKnot -->   4 [ff ff 00 00]
 46.086 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 46.126 # GoKnot -->   7 [ff 00 03 00 72 31 36]
 46.126 |- gkGTP --> "= "
 46.126 |- gkGTP --> "r16\cr\lf\cr\lf"

 46.968 |- server -> "play w D17\cr\lf"
 47.018 # -> GoKnot8 [00 00 03 10 00 00 06 00]
 47.038 # GoKnot -->   4 [ff 00 00 00]
 47.038 |- gkGTP --> "= "
 47.038 |- gkGTP --> "\cr\lf\cr\lf"

 47.228 |- server -> "genmove b\cr\lf"
 47.338 # -> GoKnot8 [ff ff ff ff 00 00 0c 00]
 47.468 # GoKnot -->   4 [ff ff 00 00]
 47.468 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 47.538 # GoKnot -->   4 [ff ff 00 00]
 47.589 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 47.629 # GoKnot -->   6 [ff 00 02 00 64 34]
 47.629 |- gkGTP --> "= "
 47.629 |- gkGTP --> "d4\cr\lf\cr\lf"

 48.620 |- server -> "play w Q3\cr\lf"
 48.660 # -> GoKnot8 [00 00 0f 02 00 00 06 00]
 48.740 # GoKnot -->   4 [ff 00 00 00]
 48.740 |- gkGTP --> "= "
 48.740 |- gkGTP --> "\cr\lf\cr\lf"

--
This is a 9x9 game start (after the first list_commands)

 14.331 |- server -> "boardsize 9\cr\lf"
 14.371 # -> GoKnot8 [09 00 00 00 00 00 02 00]
 14.471 # GoKnot -->   4 [ff 00 00 00]
 14.471 |- gkGTP --> "= "
 14.471 |- gkGTP --> "\cr\lf\cr\lf"

 14.551 |- server -> "clear_board\cr\lf"
 14.581 # -> GoKnot8 [09 00 00 00 00 00 02 00]
 14.671 # GoKnot -->   4 [ff 00 00 00]
 14.671 |- gkGTP --> "= "
 14.671 |- gkGTP --> "\cr\lf\cr\lf"

 14.751 |- server -> "komi 7.5\cr\lf"
 14.771 # -> GoKnot8 [00 00 f0 40 00 00 03 00]
 14.852 # GoKnot -->   4 [ff 00 00 00]
 14.852 |- gkGTP --> "= "
 14.852 |- gkGTP --> "\cr\lf\cr\lf"

 20.640 |- server -> "genmove b\cr\lf"
 20.680 # -> GoKnot8 [ff ff ff ff 00 00 0c 00]
 20.780 # GoKnot -->   4 [ff ff 00 00]
 20.780 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 20.870 # GoKnot -->   4 [ff ff 00 00]
 20.920 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 20.960 # GoKnot -->   6 [ff 00 02 00 66 36]
 20.960 |- gkGTP --> "= "
 20.960 |- gkGTP --> "f6\cr\lf\cr\lf"

 22.843 |- server -> "play w C6\cr\lf"
 22.883 # -> GoKnot8 [00 00 02 05 00 00 06 00]
 22.973 # GoKnot -->   4 [ff 00 00 00]
 22.973 |- gkGTP --> "= "
 22.973 |- gkGTP --> "\cr\lf\cr\lf"

 23.194 |- server -> "genmove b\cr\lf"
 23.234 # -> GoKnot8 [ff ff ff ff 00 00 0c 00]
 23.264 # GoKnot -->   4 [ff ff 00 00]
 23.264 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 23.384 # GoKnot -->   4 [ff ff 00 00]
 23.524 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 24.165 # GoKnot -->   4 [ff ff 00 00]
 24.215 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 24.275 # GoKnot -->   4 [ff ff 00 00]
 24.325 # -> GoKnot8 [03 00 00 00 00 00 0e 00]
 24.365 # GoKnot -->   6 [ff 00 02 00 66 34]
 24.365 |- gkGTP --> "= "
 24.365 |- gkGTP --> "f4\cr\lf\cr\lf"

 36.563 |- server -> "play w E5\cr\lf"
 36.583 # -> GoKnot8 [00 00 04 04 00 00 06 00]
 36.693 # GoKnot -->   4 [ff 00 00 00]
 36.693 |- gkGTP --> "= "
 36.693 |- gkGTP --> "\cr\lf\cr\lf"

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

Re: [computer-go] Please have your bot resign, for your own good

[Jacques Basaldúa]

The problem is avoiding that an inferior program wins a lost position
on time extending the number of moves. If you could choose, what side
would you prefer to be? As a human, there is no doubt. But as a program
it is even better: the strongest program. Because computers can play faster
than humans.

It is so much easier to make a strong program manage its time better
than to make a weak and fast program stronger. Therefore, I propose
a silly idea:

Introduce a bot (I suggest the name "mosquito") *intentionally* that
tries to exploit time weakness. Just an ultra blitz player that plays some
good looking move at 1 ply without search and never resigns. If your
program loses games against mosquito you have to improve your time
management.

If there is a mosquito (annoying but otherwise harmless insect) always
present in the system, serious programs will have extra motivation
to care about time management.

Of course, its only a half serious proposal. And the problem with the
Philippines won't be solved, perhaps it just a mater of increasing the
1/4 sec extra time to 1/3 or something like that. Of course that is not
fair, because it is an advantage for those with better connections, but
that cannot be avoided. Working with 16 cores is a much bigger
advantage and is not avoided either.

Jacques.

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

RE: [computer-go] misconception about game(?)

[Jacques Basaldúa]

Forrest Curo wrote (quoting David Fotland):


for example, go books make a big deal about where to extend along the
side, or when to play in one corner or another, but the difference between
these various moves is usually only a few points.


The difference between similar-appearing various moves may well be one  
of efficiency--and that translates into sente or control of the game.


A typical technique of human analysis is to consider the shape of a  
position: If the same moves had been made in a different order, would  
all of them be necessary or even justifiable? "Good shape" normally  
gives you a stable, highly defensible position with the minimal number  
of moves and hence the best chance of keeping-or-recovering sente.



I think David means in the fuseki. And that sounds right to me, because 
fuseki moves can be used for so many different purposes that they are 
seldom really bad. When a move is bad according to tewari analysis it 
sometimes happens that ten moves later another move makes the bad move 
very good. This is related with the remarks 9 dan Tei Meikou commented 
on final Katsunari vs. Crazy Stone (see Hiroshi Yamashita's recent post).


He states "White first 3 moves are 10kyu player's move." 

According to orthodox fuseki theory we must agree. MC programs show no 
respect for the rule: "First the corners, then the sides and only then, 
the center." But the truth is they play the strongest computer go nowadays. 
Many human players also start at tengen at high dan level and win their games. 

Really bad fuseki moves do exist. There are: too low, too concentrated, 
creating weak groups for no reason at all, reinforcing the opponent. 
(This list probably represents a high percentage of really bad fuseki 
moves.) But MC programs don't play any of these really bad moves.


The other moves are not really bad and they serve some purposes
that may not be as obvious as: "First the corners, then the sides and 
only then, the center." but they are justifiable and later, they may

even become good moves.

Of course, I would welcome the opinion of stronger players on this. But 
the impression I have after replaying Katsunari vs. Crazy Stone is: 
Neither Crazy Stone weak moves are so weak, nor its pro moves are a 
surprise. I guess a pro would have found a *moment* to play that sequence 
that does not turn it into a compensation for ignoring a reduction threat 
at D11, but makes both objectives compatible: defending against D11 and 
killing at bottom right. I know Crazy Stone doesn't care about winning big, 
but I like it. ;-)


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]

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]

Ben Lambrechts wrote:


What is the Zobrist Hash of the following board?


You have to create a table of *random* numbers (typically unsigned 64 bit) lets 
call the type int64.

Your table is:

CONST   BlackH  : array [0..19*19 - 1] of int 64 = ($badf00dcafebabe1, .. // 
361 entries
WhiteH  : array [0..19*19 - 1] of int 64 = (// a different set of 
361 entries

The Zobrist hash of a board is the xor of all the moves

Example (a board with 3 stones):

black (3, 4)// assume coordinates are zero-based 19x19
white (5, 7)
black (3, 2)

Hash = BlackH[19*3 + 4] XOR WhiteH[19*5 + 7] XOR BlackH[19*3 + 2];

Of course, it represents the position and is independent of the order. If you 
ignore
the move history, you can just compute the stones in any order.

The hash of the transformed black move transformed by (y, inv X) where (x=3, y=4) 
is BlackH[4, (19-1) - 3]


The hash of a transformed board is the hash computed transforming all the moves.

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.


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]

Ben Lambrechts wrote:


Now I got the following problem: how to rotate/mirror the board for a 
unique representation.


Both are the same board, but has anyone made an algorithm that rotates 
the board or an area of the board in a unique way?

I don't need the move order, just the "snapshot" of the board.


Compute the the min(8 Zobrist hashes for all mirror/rot combinations)

(x, y), (inv Y, x), (inv X, inv Y), (y, inv X), (inv X, y), (inv Y, inv X), 
(x, inv Y), (y, x).


Call the smallest of the 8 hashes the "canonical hash".

Make a database of "canonical hashes". Since Zobrist hashes can be updated
incrementally, checking over the legal moves is just xoring the 8 hashes of 
the each legal move (with a given mirror/rot) to the hashes of the current 
position in that same mirror/rot. You store 8 hashes for the current position
(=without the move) and compute the 8 hashes of the next position. The 
smallest of these is the canonical of the next position. This is repeated
for each legal move. Its simple, but perhaps my explanation makes it sound 
more complicated than it is ;-)



Jacques.

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

Re: [computer-go] A thought about Bot-server communications

[Jacques Basaldúa]

Nick Wedd wrote:

In one of the British Championship Match games, a bit over ten years 
ago, Zhang Shutai made an illegal ko move against Matthew Macfadyen, and 
immediately conceded that he had lost the game.


Is the game record available? I am interested because I have only found 2
situations in real games:

a. Triple ko
b. Double ko when the group sharing the kos has nothing better than life in 
seki.

Both have cycles smaller than 8 ply and my software doesn't check longer cycles.

I guess any human player would recognize these situations. So if a strong player
didn't it must be something more complicated.


Jacques.

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

Re: [computer-go] Microsoft Research Lectures: Akihiro Kishimoto

[Jacques Basaldúa]

Thank you, Harri.


It sounds promising. I will have a look at that.


Jacques.


I coded algorithm based for that representation, it really looks another 
awesome thing worth of investigating.
Planning to use that for at least small board search investigations as it has 
quite much power.
That is included lates version pf http://sourceforge.net/projects/narugo I 
am happy to hear some feedback if that TsumeGoMoveGenerator has some bugs by 
the way.
It is first version of that, so propably it has some bugs left. But first 
impression about algorithm wou, impressed as it answered easy tsumego 
problem immediately,
it has much potential to extend other kind of problems, not only life-and 
dead problems.



t. hArri


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

[computer-go] Microsoft Research Lectures: Akihiro Kishimoto

[Jacques Basaldúa]

David Stern wrote:


Akihiro's talk has finally been put online at:



http://content.digitalwell.washington.edu/msr/external_release_talks_12_05_2005/15004/lecture.htm


Good lecture. 

Is there a link to a binary (or source code) somewhere ? 


I can't find any TsumeGo Explorer website. At least, not in English.

Jacques.
*
*

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

[computer-go] Re: The global search myth

[Jacques Basaldúa]

Dave Dyer wrote:

In cases where the good moves are the "obvious" ones, 
you've found them anyway.  


Ok. Here I agree.

In other cases, you prune them away.   


You are not really pruning, just postponing. Of course
you may overlook moves of genius, who doesn't? But
if your probabilities are correct you may be emulating
what a human does.


You DO get wrong answers much faster this way though.


Why? I don't see why. I see this order as the most 
human like way of searching. As any incomplete search,
it can blunder, but why more than any other incomplete 
search?



Jacques.


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

[computer-go] Redirecting i/o in the Windows version of Mogo (Was in Re: Update of MoGo binary ..)

[Jacques Basaldúa]

Edward de Grijs wrote:


Can someone help me with this problem, for which I cannot
find a solution: I am trying to run MoGo in an automatic 
way, using the cygwin toolkit.


I guess you are trying to do this in Windows and using
the Windows binary. If this is the case, you don't need
any library. I did it and it works.

Now, Linux supporters will enjoy this ;-), even as a 
Windows programmer I must admit that redirecting

console i/o is one of the weirdest Windows "features".

The official Win32 reference example explaining how to do 
this has 245 lines of code!! (although many are remarks)


If you have the Win32 reference in .hlp format search
an article titled "Creating a Child Process with Redirected 
Input and Output". If you don't, it must be public at MSDN.



Jacques.

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

[computer-go] ELO Ratings of move pattern

[Jacques Basaldúa]

Lars wrote:

> Anyone of you have similar or other experiences with the algorithm?

I use at runtime the same Bradley-Terry formulas Remí introduces
in his paper. That is a huge advance compared to "naif urgency"
scores because it gives a measure of how hard it was to "win"
for a move candidate. But I use a much simpler offline learning
algorithm: Compute the "naif" score just as standard:

 sc[0] = (times played)/(times played + times postponed)

Use this as an a priori value of the score. Then, iterating through
all the games many times, create a compensation weight CW
rewarding scores winning positions with high total of concurrent
scores and diminishing those won "too easily". Since the
efficiency of the offline part of the program is not an issue,
I make these in small steps iterating many times until they
do almost nothing. Each time, I compare observed versus
expected number of right guesses to see if it improves or not.

   sc[i] = CW*sc[i - 1]  // * is elem by elem mul of a vector

I guess it gets to more or less the same. Sure Remí's solution
is more efficient and elegant.


2 more issues I am concerned about patterns:


MIAI URGENCY: When two (or maybe more) moves are
extremely urgent, but it is not important which of the two
because they are equivalent. In this case the high urgency
is masked by the fact that it is divided between two moves.


IMPLICITLY CHECKED URGENCY: When an urgent
pattern was already on the board and was not played its
score is overestimated. Imagine threatening a bamboo joint,
preserving the connection may be a huge point when it saves
a big group without eyespace. But it may also be worth nothing
when both groups are dead. When it first appears, there is
a high probability that it is big and, therefore, its urgency should
be high. But, if it wasn't played, then it is probably not big.
The next times it has to be considered much less urgent than
the first time.


Jacques.


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

Re: [computer-go] erm...

[Jacques Basaldúa]

Don Dailey wrote:


The assumption is that 1 Dan 19x19  =  1 Dan
9x9  and on average this will be true. 


That is precisely my point. It is a very strong assumption because
19x19 has lots of things: joseki study, global board evaluation, etc.
that do not exist in 9x9. This assumption is only an approximation. It 
is  like  guessing that a world champion 100 meter runner will also be 
a world champion long jump athlete. That may happen (Carl Lewis), but 
usually it is not the case,  although the correlation is evident. 
Perhaps the word champion in 19x19 is in the top-50 at 9x9. Nobody will 
be surprised if a 3 dan beats a 5 dan consistently in 9x9, because it 
is a different game, but of course, a 10 kyu won't have a chance.


The correct answer should be: dan does not exist for board sizes other 
than 19. And it is impossible to define a consistent scale made of 30

levels for 9x9. Perhaps 9x9 has only 10 or 12 levels. Defining a step
in level as being a standard deviation above the other player in the 
normal distribution that justifies the Elo system.


(BTW. The best proof that the 19x19 level does not match the 9x9
level are the UCT programs themselves.)

Jacques.

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

Re: [computer-go] New engine? From a Chess programmer perspective.

[Jacques Basaldúa]

Christoph Birk wrote:

I don't think 2200 ELO on the 9x9 CGOS is equivalent 
to 'high dan-level' play.


Neither do I. In fact the whole kyu/dan rating system applies
only to 19x19. 9x9 is not deep enough to have have so many ranks.
On a 9x9 board an average amateur beats a pro with handicap 3.
That amateur would be crushed by the pro with handicap 9 in 19x19.

Jacques.

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

Re: [computer-go] Drunken sailor on payday

[Jacques Basaldúa]

Raymond Wold wrote:


Do you have anything to back this up? I was under the impression that
most decent assembly programmers agreed that they can't compete with the
best C compilers.


Absolutely NOT. 

"Only" the typical, perhaps 99.9% of the programs, made of: transfers, 
conditionals, integer arithmetic and _non-parallelizable_ floating
point arithmetic are efficient when compiled in C (or Pascal which 
compiles to the same binary and creates the same compatible .obj as C). 
In these cases, writing in assembly is both less efficient (because the 
compiler finds optimizations the programmer won't find) and harder to 
maintain.



BUT

Programs with bitmaps, bit manipulation, masks, etc. Which are really 
useful in go, are (sometimes x4) more efficient written in assembly. The 
same was the case when Chen Zhixing wrote Handtalk in assembly. The same 
happens in any cryptographic, binary image compression/decompression, 
application today and forever etc. Compilers optimize "vulgar" programs, 
because that is what most programs are. Please, understand "vulgar"

as defined above, we all write lots of vulgar programs, it is not
an insult.


Programmers should view the code they are generating and _only_ that 
should tell them what is worth writing in assembly and what isn't. 
The best programming language is the language that lets you write 
assembly language hacks clean and easily using the high level symbols.



It is fine to use "cool feature" languages on the base that your 
priorities are different and you don't care about the binary, but
you shouldn't claim that you can have both "coolfeatureness" and 
efficiency, because that is simply not true.



Of course, what is "cool" is very subjective debate: Some people
find it cool to depend on runtimes that increase at mega/month 
rate, do what the API already does only much worse, gift the user 
with "the gray rectangle experience" even on a quad-core. After 
two seconds of gray rectangle they paint something that does not 
properly support clipboard operation, replaces the system's file 
dialogs for dialogs in which you have to manually type: *.sgf, 
*.SGF, *.Sgf, .. (to see all your .sgf files), that never remember 
last folders, etc. All this annoyance just because someone bought 
the "platform independence fallacy" from a company (Sun microsystems) 
that never cared a bit about compatibility. I am still waiting to 
meet the first person who answers affirmatively to the question: 
"Have you ever paid for a program written in Java?"

Simple question, everybody I ever met answers no. Guess why.


Jacques.

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

[computer-go] CGOS 19X19 is down

[Jacques Basaldúa]

Hello

I was waiting till someone restarts, but nobody seemed to notice.
CGOS was hanging yesterday morning (European time) with 3 games
4849..4851 where no black engine placed any stone.
If black restarted (one of the black bots was mine) it lost on time because
the 30 minutes had been used. Black lost on time without even getting
a gen_move command.

For about 36 hours now, game 4851 is still waiting for black to start.

Jacques.

PD I don't know who is in charge of CGOS, Don, Olivier or Jason.
If this is not the right place to post CGOS incidents, tell us where.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Language

[Jacques Basaldúa]

Don Dailey wrote:

> My Go program doesn't use any libraries except the standard C
> libraries.

I agree at 99.9% !! The only exception in my case is SFMT.
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
SFMT is 100% clean C software, easy to compile, easy to use and free.
A good RNG makes a huge difference.

> We all called his software "buzzword compliant" because he admitted
> that he wanted to "try out" several new technologies.

Ha, ha. These guys exist in all latitudes. I've met a few ;-)

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

Re: [computer-go] [OT] All-integer scalable distribution algorithm.

[Jacques Basaldúa]

Mike Hill wrote:

The essence of my idea is that I want a psuedo-random algorithm which 
takes as a parameter a 'degree-of-randomness' value.  Something along 
these lines:


int choose( int range, int degree-of-randomness)

Returns an integer in [0-range] distributed depending on the value of 
degree-of-randomness.  At degree-of-randomness 100, I want the 
distribution to be uniform.  At degree-of-randomness 0, I want the 
distribution to be  -- I don't even know what to call this -- 
half-of-a-normal-distribution  with the steepness proportionately 
related to degree-of-randomness.


As mentioned, you can make your distribution parametric 
(depend on degree-of-randomness). The standard deviation is the 
right choice for that, but you have to trim results outside [0-range].


Or ..

You can perform a random experiment to mix both:

pseudo code:


if Uniform(0, 100) >= degree-of-randomness 
then 
return Normal (range/2, sd)

else
return Uniform(0, range)


Jacques.


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

[computer-go] Connecting a gtp engine to CGOS 19x19 using Windows OS

[Jacques Basaldúa]

Here are the steps:
---


1. Get TCL. There are many "flavors" with GUI, debugger etc.
  The simplest, when you just need to run a Tk application
  is something like:

  http://www.equi4.com/pub/tk/tclkit-win32.upx.exe

  This .exe is all you need, about 1M and without any annoyances,
  installation, registry etc.

  For simplicity: Rename tclkit-win32.upx.exe as tcl.exe


2. Get the .tcl client from CGOS.

  http://cgos.boardspace.net/public/cgos3.zip


3. Modify the .tcl script to use the 19x19 server

   # ... set server cgos.boardspace.net
   set server cgos.lri.fr

   # ... set port   6867
   set port   6919

   No other modification is necessary.


4. Create an account in CGOS. I remember having read that when you
  use one for the first time, any name and password are valid
  and then, you have to use the same password to continue using it.

  So, for testing purposes, I use the account:

  name: testingTCL
  pass: password


5. Using gnugo for the sake of simplicity (just for the test),

  gnugo37 --mode gtp --chinese-rules --capture-all-dead

  should be a valid setting to play on CGOS.

  Remember that you will loose lots of won games if your
  program does not capture all the opponent's dead stones.

  Chinese rules is mandatory as well.


6. Create a .bat file with:

  tcl cgos3.tcl testingTCL password "E:\\GO\\PROGRAMS\\GnuGo\\gnugo37
--mode gtp --chinese-rules --capture-all-dead"


7. Run the .bat file wait for the next round. Your program should be
   playing.


8. To supervise your program:

   Download cgosview.exe from

   http://cgos.boardspace.net/public/cgosview-windows.zip

   You don't need to specify the arguments for the 19x19 server,
   that is the default so for 19x19.

   Just run:   cgosview.exe


Jacques.


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

Re: [computer-go] Connecting a gtp engine to CGOS 19

[Jacques Basaldúa]

Solved!

It is working now. The problem was the tcl script does not
pass all remaining parameters to the called application
(gnugo in the example). To solve this, the command line
should be delimited with a quote " char.

tcl cgos3.tcl testingTCL password "E:\\GO\\PROGRAMS\\GnuGo\\gnugo37 
--mode gtp --chinese-rules --capture-all-dead"


instead of:

tcl cgos3.tcl testingTCL password E:\\GO\\PROGRAMS\\GnuGo\\gnugo37 
--mode gtp --chinese-rules --capture-all-dead



I repeat the corrected post:



1. Get TCL. There are many "flavors" with GUI, debugger etc.
  The simplest, when you just need to run a Tk application
  is something like:

  http://www.equi4.com/pub/tk/tclkit-win32.upx.exe

  This .exe is all you need, about 1M and without any annoyances,
  installation, registry etc.

  For simplicity: Rename tclkit-win32.upx.exe as tcl.exe


2. Get the .tcl client from CGOS.

  http://cgos.boardspace.net/public/cgos3.zip


3. Modify the .tcl script to use the 19x19 server

   # ... set server cgos.boardspace.net
   set server cgos.lri.fr

   # ... set port   6867
   set port   6919

   No other modification is necessary.


4. Create an account in CGOS. I remember having read that when you
  use one for the first time, any name and password are valid
  and then, you have to use the same password to continue using it.

  So, for testing purposes, I use the account:

  name: testingTCL
  pass: password


5. Using gnugo for the sake of simplicity (just for the test),

  gnugo37 --mode gtp --chinese-rules --capture-all-dead

  should be a valid setting to play on CGOS.

  Remember that you will loose lots of won games if your
  program does not capture all the opponent's dead stones.

  Chinese rules is mandatory as well.


6. Create a .bat file with:

  tcl cgos3.tcl "testingTCL password E:\\GO\\PROGRAMS\\GnuGo\\gnugo37
--mode gtp --chinese-rules --capture-all-dead"


7. Run the .bat file wait for the next round. Your program should be
   playing.

8. To supervise your program:

   Download cgosview.exe from

   http://cgos.boardspace.net/public/cgosview-windows.zip

   Call it with these args: cgosview.exe cgos.lri.fr 6919


Jacques.

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

[computer-go] Connecting a gtp engine to CGOS 19

[Jacques Basaldúa]

I am trying to make a description of all steps required. But
it still doesn't work. So please, say what am I doing wrong.


1. Get TCL. There are many "flavors" with GUI, debugger etc.
  The simplest, when you just need to run a Tk application
  is something like:

  http://www.equi4.com/pub/tk/tclkit-win32.upx.exe

  This .exe is all you need, about 1M and without any annoyances,
  installation, registry etc. For the following, I rename it as tcl.


2. Get the .tcl client from CGOS.

  http://cgos.boardspace.net/public/cgos3.zip


3. Modify the .tcl script to use the 19x19 server

   # ... set server cgos.boardspace.net
   set server cgos.lri.fr

   # ... set port   6867
   set port   6919

   Use # to change the original lines into remarks and add new lines.

   AFAIK no other modification is necessary. Please, confirm.


4. Create an account in CGOS. I remember having read that when you
  use one for the first time, any name and password are valid
  and then, you have to use the same password to continue using it.

  Now I can't find where I read that. Please, confirm.

  So, for testing purposes, I use the account:

  name: testingTCL
  pass: password


5. Using gnugo for the sake of simplicity (just for the test),

  gnugo37 --mode gtp --chinese-rules --capture-all-dead

  should be a valid setting to play on CGOS.


6. I create a .bat file with:

  tcl cgos3.tcl testingTCL password E:\\GO\\PROGRAMS\\GnuGo\\gnugo37 
--mode gtp --chinese-rules --capture-all-dead



7. I run the .bat file and that launches both tcl.exe and gnugo37.exe I 
don't

   get any info from neither. I can't see my program when I use:
   E:\TEMP\cgosview.exe cgos.lri.fr 6919
   to see what is happening on the server.
   I have waited for many rounds to finish, but my program never plays
   if it is connected at all, something I don't know.


8. Shouldn't there be log files somewhere? Where? I don't mean .log files
   with gtp info. I can do that myself. I mean log files giving some 
info about

   the communication and the state of the server.


Jacques.

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

Re: [computer-go] 19x19 CGOS

[Jacques Basaldúa]

Don Dailey wrote:

> There is no simple way to fake it with combinations of pass
> moves with programs cooperating. Probably most programs
> won't pass on the first 20 moves or so, but we can't count on
> that behavior because it's incorrect. You should always pass
> immediately if it wins the game outright.

Probably right. There is probably no simple idea that works
with arbitrary handicap and any player, but what I suggested
does work for white giving 3 stones (or less). The server
should still understand that the program is special in the sense
that it should always play white. I guess that shouldn't require
a lot of work.

What John Tromp suggests works for higher handicaps, but
not for 3. And it is a bad idea for black. Just imagine:

1 c4 ..
2 .. f3
# Now B encloses W as John Tromp suggested:
3 e3 ..
4 .. pass
5 f4 ..
6 .. pass
7 g3 ..
8 .. pass
9 f2 ..
# The white stone is captured
10 .. q16

And now black's advantage is small for a handicap 3 game.
Black could lead in 3 corners, one of them with shimari after
move 9 and what did he get attacking? One corner.

Jacques.

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

Re: [computer-go] 19x19 CGOS

[Jacques Basaldúa]

Don Dailey wrote:

Of course that's better,   but I'm talking about a quick and 
dirty solution. I may never implement handicap games since it's 
tricky with ELO ratings.


This can also be done by the programmers. E.g. If CrazyStone is 
too strong, Rèmi can introduce a CrazyStoneH3 which passes 3 times

at the beginning. But not at the first move, to avoid smart tricks.

If CrazyStoneH3 is given white and plays: 2. whatever 4. pass 
6. pass 8. pass. Black cannot pass and win the game because of komi.


This way you are not forcing programs to accept handicap (some may 
suffer more than others). It is just a program who always gets

white and does not play against other handicap programs.

Just an idea.

Jacques.

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

RE: [computer-go] XML alternatives to SGF

[Jacques Basaldúa]

Bob Myers wrote:


Many of those complaining about XML don't seem to really know too much about it.


That is exactly my point. I don't know and I don't want to know!

SGF is fine. It has been stable for years because there is no problem at all.
Should we find a problem, there is a straightforward solution: a new SGF 
version.

At the end, either creating your own XML parser (by experience, the best option) 
or entering the nightmare of depending on someone else's library, bugs, updates, 
limitations, etc. costs A LOT OF TIME.


For what?

For nothing. Again, sgf works fine. Nothing would be as stupid as having go 
games
split in 2 incompatible formats. Two formats for the same thing is just a tax on 
go development: Its not enough with one effort for making your program compatible

you have to do it twice. Who wins anything with that? I can't guess.

Jacques.

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

Re: [computer-go] XML alternatives to SGF

[Jacques Basaldúa]

Heikki Levanto wrote:

Even if a new proposed standard would have many benefits, 
obvious to everyone (which I have not yet seen), I would 
stuill urge people to consider those benefits carefully, 
and to weigh them against the problems that arise from

having two incompatible standards.


I agree 100%. 


Unfortunately we (all of us, I guess) all have few time
for go programming. The most crazy idea to invest that time
in is yet another file format. Personally, I won't do 
anything against sgf. I just expect that the XML idea 
fails. If it doesn't, that may be a problem in a few years.


Jacques.

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

[computer-go] Random move selection (was) Crazystone patterns

[Jacques Basaldúa]

Dave Hillis, wrote:

Suppose I can generate scores for all of the moves quickly enough. 
I still face the problem of quickly choosing a move biased by the 
scores. Tournament selection is fast, but that is a function of 
relative ranking of the scores, not the values of the scores. 
Roulette wheel selection gives me an answer, but it is slow slow 
slow, the way I implement it anyway. Can anybody describe a good 
way to do this?


We posted about that before this summer when I was implementing it.
I proposed a "ticket based lottery", but that, of course, restricts
the difference to small values. It can be implemented using a linked
list so that each extra ticket allocation cost few clock cycles (I don't 
remember exactly how many, but less than 10 asm instruction for sure).


My final version uses 2 values for the tickets HI and LO where

1 HI = 32 LO

The default (when the pattern is not in the database) is 1 HI.

The score goes from 1 (= 1 LO) to 1024 (= 32 HI). If you round the scores
it the database to avoid such values as 927 (= 28 HI, 31 LO) and round 
it as 928 (= 29 HI) you can have a nice dynamic range from default/32 to

default*32 having not too many tickets to allocate.

Jacques.

PD. Search the threads (about May-June 2007) because other good ideas 
were proposed. Binary trees, etc.



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

Re: [computer-go] Re: Most common 3x3 patterns

[Jacques Basaldúa]

Cenny Wenner wrote:

>Care to elaborate on what you mean by scores here and how they are
>similar to the 9x9 equivalence?

I guess Dave is using Bradley Terry scores. This idea was introduced by 
Rémi Coulom in
"Computing Elo Ratings of Move Patterns in the Game of Go" The paper is 
available on the
web (finding link left to the reader ;-). This idea outperforms previous 
approaches.


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

Re: [computer-go] Update of MoGo binary release, and windows version available!

[Jacques Basaldúa]

Thank you Sylvain!

It works fine for me. A very good sparring strong and so different in style!


You mean that with the .dll in WINDOWS\system32 that goes further? I
thought that the .dll in the same directory as the .exe was enough.


Copy/pasting from Microsoft's API reference:

" The function searches for the file in the following sequence: 

1. The directory from which the application loaded. 
2. The current directory. 
3. Windows 95: The Windows system directory. Use the GetSystemDirectory function to get the path of this directory.

  Windows NT: The 32-bit Windows system directory. Use the GetSystemDirectory 
function to get the path of this directory. The name of this directory is 
SYSTEM32.

4. Windows NT: The 16-bit Windows system directory. There is no Win32 function 
that obtains the path of this directory, but it is searched. The name of this 
directory is SYSTEM.
5. The Windows directory. Use the GetWindowsDirectory function to get the path of this directory. 
6. The directories that are listed in the PATH environment variable. "


The priority is only important if there is more than one version of the file.

Placing the "file that works ok" in the same path as the application is good 
practice. This makes the program work fine without modifying the system anyhow.


Jacques.

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

Re: [computer-go] Binary release of MoGo

[Jacques Basaldúa]

Hi Sylvain,

Any news about the Windows release? It doesn't need to be fast. It 
doesn't even need
to be multithreaded. It is for research only. We can believe that on a 
quad core it takes

1/4 of the time, that's not important.

BTW. Windows has a 15 year old bulletproof multithreading API  from 
which you only
need 3 functions in a typical case, (CreateThread, EnterCriticalSection, 
LeaveCriticalSection)
and just one if you create your own semaphores. The best multithreading 
library is, probably,
none at all. That's probably much easier than trying to see what's the 
problem with pthread.


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

Re: [computer-go] playing strength of programmers

[Jacques Basaldúa]

I agree with all those who say it is important, but there is some 
precision to be made:


As a player you are as strong as your weakest link because you are 
punished for your mistakes.


As a programmer you are a strong as your strongest link. You know that 
mistakes are just mistakes, as long as you can identify them, your 
program won't do them.


My advice is: Read about advanced strategical concepts (in books, not 
only sensei) and watch dan players until you understand what they do. 
Don't worry about your own level. It will increase anyway, but you will 
still be beaten by players who know less than you but are way more solid.


Understanding dan level play is some orders of magnitude easier than 
playing dan level.


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

[computer-go] Go in hardware

[Jacques Basaldúa]

Hi Chrilly:

You have mentioned go in hardware twice recently and I have, knowing
that you have experience in hardware development, some questions:

1. What should be implemented? In your Hydra cluster I have read you
implemented mobility, and somewhere you proposed something like
influence. Can you explain it?

Here are questions for anyone how knows or has ideas:

2. My board system. I have Bradley Terry scores of patterns built of
the neighbors of all empty cells that translate to the legal moves
sorted by score.

I can update the 40 neighbor masks without any conditional jumps
in about 3 asm instructions per neighbor, say 2 ns at 3.4GHz.
In hardware you could do in parallel what I do sequentially (the 40
neighbors). But few stones have 40 empty neighbors because they
may be out of the board (I once explained how I do that) or not
empty, so a guesstimate of the gain for doing that in hardware is
x20 (i.e. x40). If your hardware technology runs at 3.4 GHz,
that's great! But if it runs at 200 MHz it is even.

Then, my software is multicore. I test it with 2 cores, but expect
to run in on 256 cores machines in the future. Can the hardware
support this?

3. My second problem. translating patterns to scores (database
search). I call it a database, but it is a set of sorted 32 bit masks
where I can find really fast without any conditional jumps using
cmovc instructions. So it is very similar to the previous case.
Hardware is better only if clock speed is high enough and it
supports multiple cores.

4. My "bottleneck": Sorting. Its not really a bottleneck because
sorting few values is fast, but it is the slowest part of my m-search.
(Sorting is not required for MC/UCT methods.) Is there hardware
for sorting?

In short:
 a) How fast can we expect hardware to be?
 b) Can you repeat the "hardware kernel" x times so that each
 thread own an independent kernel?
 c) Can you sort (in flash time) 19^2 integers?
 d) How many patterns could the hardware store?
 e) How much would it cost?

Of course, implementing in software has a wider market and
you should only implement something that proved to be valuable.
I am not claiming that my board is, but it is an interesting subject.

Jacques.

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

Re: [computer-go] Why Poker-GMs don't win at poker.

[Jacques Basaldúa]

>Poker can be analyzed well by (even naif) Monte Carlo methods.


How? 


Simulation! Whatever evaluation you need and don't know how to 
compute because it is too complex for easy formulas can be 
simulated.


This applies to the probability of winning, but also on the 
betting decisions (call, raise, etc.) and the amount in the pots

your own and your opponent's. Play it out randomly 10 times
and see how many times you win/loose. Whatever estimator you get
will be better than what a human can do just guessing.

I call it naif because its the first idea, like basic MC. Then,
knowing the problem better you can evolve to something like UCT
that favors more promising lines, etc.

Jacques.


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

[computer-go] Why Poker-GMs don't win at poker.

[Jacques Basaldúa]

Chrilly Donninger wrote:


I think poker is more difficult than Go and of course chess.


Poker can be analyzed well by (even naif) Monte Carlo methods.
Of course, the fact that you get a better estimate than any
human could dream of, won't necessarily make you win.

This common misconception can be found in many computer go
papers. People who train patterns to predict moves tend to 
think the more they predict the better. Some even claim 60%

prediction rates and higher. Of course, we all predict moves
as a play when we watch pro games and feel good when our guess 
is right. Two reasons make it easy to have "high" prediction 
rate: a. forced moves b. local play is easier to analyze than
the value of all possible tenukis. Usually, you don't do very 
wrong answering local and postponing other fights.


My case: I have to give Bradley Terry scores to 1/3 M patterns:

LoadJeitoLibRW_ByName() Importance of database loaded
# of imp = 32   91986  (91986)
# of imp = 31   25466  (117452)
# of imp = 30   20263  (137715)
# of imp = 29   18556  (156271)
# of imp = 28   17592  (173863)
# of imp = 27   17646  (191509)
# of imp = 26   17722  (209231)
# of imp = 25   18575  (227806)
# of imp = 24   19283  (247089)
# of imp = 23   20525  (267614)
# of imp = 22   21695  (289309)
# of imp = 21   23712  (313021)
# of imp = 20   25434  (338455)

Note: The importance of a pattern is the number of disjoint sets 
of games where the pattern is found if you divide the whole database

in 32 disjoint sets. E.g. A pattern of importance 28 is a pattern
found in 28 sets of about 1500 games but not found in 4 sets of the
same size. I don't collect data on the number of games in which each 
pattern is found. 

Note: These are the real untricked patterns. Then, I generate a 
crunched version that behaves "mostly" like the big one.


So I have 338455 patterns of importance 32 to 20 I could try to
maximize the probability of a guess, but I don't! 


What I really am interested in is _a probability distribution over
the legal moves_. I ask my HSB board to give me the _minimum number 
of moves_ that cover a 30%, 50%, 99% probability. (Note: This number 
is not an integer. Eg. If it is 3.17 -> If the winning move is in 
the 3 first, you add 1, if it is the fourth move you add 0.17 and 
else you add 0.) The legal moves are sorted in descending score. 
For adjusting my Bradley Terry models I have a loss function and 
a very naif method that corrects in small steps. (The good thing
of off-line learning is that you can implement junk because that 
does not go into the program. ;-) The program updates a pattern
and finds its score in two digit nanosecond times (< 400 clock 
cycles) if it may have changed, and 0 if it may not.)


My loss function evaluates (using a random sample from an independent 
test set) if: When I want 50% I really get 50% (and the same for

other values, of course.)

If I want 50%, getting 60% is as bad as getting 40%!! What I need
is a reliable distribution not a "thing that guesses many times".
And also, that this distribution contains the maximum information
(but that is another story).

This explains why when you watch the European Poker Tour on TV
and the journalist identifies half a dozen "legends" including
previous year's world champ, US guest don't-know-what-champion
Las Vegas, and all other "celebrities", none of the legends wins
except by a fluke just like anyone else.

Statistics is not about winning the lottery, its about getting 
good estimators. And computer poker programs do better than humans

but that does not make them win.

Jacques.


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

Re: [computer-go] Intelligence

[Jacques Basaldúa]

Hideki Kato wrote:

Creativity here is, to generate a new method by combining methods 
the system already has, in order to solve a problem.


That is creativity for the job of designing algorithms. Playing
go, creativity is finding moves _that work_ that nobody would have 
thought of.


I think there are two myths about creativity:

1. Creativity is always good.
2. Humans are more creative than computers.

1. Creativity has to do with exploring unexpected directions.
When you are subject to restrictions and have some measurable goal, 
there is an optimal amount of creativity for a given problem.

(Imagine creativity like a thermal energy in simulated Annealing.)
Too few creativity restricts you to an local minimum from which you
have not enough energy to escape. Too much creativity takes you outside
the goal maximization paths.

The most creative go player is the uniform random player, but that it 
uninteresting creativity the only interesting creativity is "creativity 
that works". Vomiting on a canvas and pretending to be an artist for that

is uninteresting creativity (aka stupidity).

2. For humans it is extremely difficult to simply "create" one hundred
uniformly random digits. Either you bias or, trying to compensate the
overall distribution, you fall into serial correlation. Computer creativity
is way easier, faster, measurable and reliable than human creativity.

Jacques.

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

Re: [computer-go] Slides for Villach-EC Lecture

[Jacques Basaldúa]

The word in AI I don't feel conformable with is Artificial, not 
Intelligence. I use _Abstract_ Intelligence (also AI) as a replacement. 
Have you ever heard of artificial aerodynamics (applicable to planes but 
not to birds) or artificial thermodynamics (the same). I understand that 
AI is the science of thinking machines and that, of course, applies to 
biological ones. Aerodynamics was not developed by ornithologists and 
neither will the theory of thinking machines be developed by any 
frog-rippers. Electrical engineers laugh at a joke in which someone 
pretends to have found The Physical Location Of The Notepad (all 
capitalization is insufficient to reach the pompous statements 
frog-rippers use to make) in the floppy disk. After a conclusive 
experience placing electrodes on different parts of a computer, it has 
been proved that the floppy disk unit triggers each time the application 
Notepad is launched. Of course, the reason behind the floppy access is 
the last file opened was "a:\readme.txt". All serious science is a part 
of Mathematics ( if not, Mathematics will absorb it ;-) ) and so is the 
science of thinking machines: AI.


Jacques.

PD. The only explanation I find to the "need" of the word artificial is 
the (for me totally unexplainable) respect educated Anglo-Saxons have 
for religion. This way, it looks compatible with religion, but of course 
it isn't. The soul of a thinking machine is an anti-scientific notion no 
matter what kind of thinking machine.



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

Re: [computer-go] Why are different rule sets?

[Jacques Basaldúa]

Jason House wrote:


I run some really dumb bots online that play perfectly fine blitz games
(10s/move) with Chinese rules and it still drives humans insane because the
computer doesn't stop playing.  People resign won games in endgame because
they can't take it.  There is some value in reducing the number of moves in
a game.


10 seconds/moves is not really blitz. If the program plays stupid invasions
(I don't know if its is the case of your program) that can be annoying if it
goes up to 50 unnecessary moves or more. As a user, I like to count. I don't
like computer resignation. It emulates human honor codes. For a human it is
very humiliating to be forced to play a losing game for a long time, but
computers have no honor, they should play _fast_ and without burning out
ko threats just because there is nothing to lose. My favorite computer
behavior as a user: gnugo with no resign at a fast level (max 2 sec/mov).

Jacques.

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

Re: [computer-go] UCT caveat (was in Explanation to MoGo paper wanted)

[Jacques Basaldúa]

Brian Slesinsky wrote:

And this would mean that a position where black is in trouble 
would look stronger than in a random playout (due to black 
playing well only for this kind of situation) which would make 
it harder to tell which positions are actually good.



Or in general, an improvement in play that only works for some
positions will tend to make those positions look good, and make it
hard to tell which positions actually are good.


That's what I mean. The defense favors one player (the one in 
danger) more than the other and these positions get a wrong

evaluation. That is dangerous and, in general, will weaken the
program. Maybe in a particular situation it is a good idea.
Sometimes breaking the rules is a good idea. ;-)

I like this example because it sounds very reasonable and it is not 
obvious that it is breaking the rules (the unbiasedness rule), but 
it is. 


Jacques.

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

Re: [computer-go] UCT caveat (was in Explanation to MoGo paper wanted)

[Jacques Basaldúa]

Brian Slesinsky wrote :


> When you favor defense (or attack) you may think: "This is unbiased
> since some times it favors black and other times it favors white" But
> the fact is when black is in danger at the root of the tree, it is in
> danger in most of the tree, therefore the trick gets the evaluation wrong.




Well, this is subtle enough that I don't understand it.  What are two
positions that it would compare incorrectly?



- Brian


It is not two positions. What I say is "the same applies" _obviously_ 
if it is the other color who is in danger.


I will try to explain it better: E.g. The game is in a position where black 
is in danger. That position is the root node. All stones in the root node

are inherited in any node below, except when they are captured. Your trick
pretends to favor defense. Therefore, black has higher probabilities of
survival than with uniformly random playouts. Since all nodes in the tree
have been inherited from root, they are mostly in the same situation.
The simulation is a stochastical estimator of either the territorial value
of the game or the percentage of win (which is determined by comparing
the former with some threshold). Since you are favoring systematically
one of the players (the one who is in danger at root is always the
same player) you are biasing the estimation. Because the variance of a
random playout is so big compared with the difference in conditional
probability: P(win | a good move) - P(win | a bad move) is a very
small number -> the smallest bias is too much bias -> the program gets 
weaker.


Jacques.

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

Re: [computer-go] Explanation to MoGo paper wanted.

[Jacques Basaldúa]

Hi, Don

I can find arguments to disagree. I think what makes humans "homo 
sapiens" is reasoning, not the ability to compute numerical simulations.

As a human (I am one) I feel disappointed when the explanation I get for
a best move is "after x millions of simulated matches it proved to be 
the best". If it is well done, I believe it, but I don't like it because

I cannot verify it by myself. Such a program will not improve my play
because it will not tell me what I do wrong or how I can improve. As
a user, I would rather pay for a program that makes me improve my play
than for the best program that only tells me moves are "simulation gospel".

On the other hand, I can imagine an old go sensei (I have never met
one, I imagine him from Kawabata's novel) like a virtuous piano player, 
imagine Arturo Benedetti Michelangeli or Tete Montoliú (I met him). These 
men had their brains and even their bodies transformed by a whole life

of study and improvement towards perfection. What they finally gained was
_gesture_. The way they put their hands on a piano keyboard or the way 
they read a go board was the result of a lifetime of training. What you

call "a dirty hack", patterns deeply implemented in their brains.

Gesture is what I expect from my programs. And a lifetime of training
may be 100 hours of computing. I call it "jeito". It sounds Japanese,
that is appropriate for go. Here, in the Canary Islands, the word
is used in the sense of a "skillful trick" and most people believe
it is a Canarian word. The truth is it is a Portuguese word and it 
means gesture.


Of course, this is just chatting. At the end the strongest program
decides who is right and who is wrong. ;-)


Jacques.


Don Dailey wrote:


What really irks me is that in most peoples minds, that is considered
the "elegant" approach - hard coding tons of fixed "knowledge" into the
program.  Nothing could be farther from the truth,  this is a dirty
shortcut, a hack.   There is nothing elegant whatsoever about  having a
huge database of patterns that tell the program what and what not to do
- then calling it "smart."



The reason UCT/MC is elegant is that it has a built in mechanism to
discover truth for itself.   It may not be the best way and perhaps
there is something better but at least it is a try.In a lot of ways
it mimics the human thinking process.   The MC play-outs is a crude
substitute for human experience (the experience is gained on the fly)
and UCT tree is a substitute for reasoning about characteristics of the
position, what does and doesn't work. 



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

[computer-go] UCT caveat (was in Explanation to MoGo paper wanted)

[Jacques Basaldúa]

Brian Slesinsky wrote:


Since the players in the playouts are so weak, it seems like the
improving the ability to defend a strong position from a
not-very-clever move (and not lose it via a blunder) should be more
important than improving the ability to find an attack.  If there are
two equally bad players that can easily attack each other but can't
defend, it seems like the results will be close to random, almost
regardless of starting position, unless it is very strong.  On the
other hand, if two bad players are somewhat better at defense but
lousy at seeing weaknesses in the other side, there will be less noise
and the one with more territory will tend to win, but an attack on a
mostly solid position will sometimes be found via a random move, and
given enough playouts, this will result in the probability of defense
with a weakness being slightly lower than a truly winning position.



It seems like this effect would be especially true of the endgame
where there aren't so many points to take, but a position could be
lost due to a blunder.



I'm not sure how useful that is, since to defend a position you need
to know how it might be attacked, but perhaps it leads somewhere?


This is a good example of something really dangerous. It is not obvious
why this is biased, but it is. In my previous post about bias, I did not
mention that: playouts must be unbiased _for all possible root positions_.

When you favor defense (or attack) you may think: "This is unbiased
since some times it favors black and other times it favors white" But 
the fact is when black is in danger at the root of the tree, it is in 
danger in most of the tree, therefore the trick gets the evaluation wrong.

And the same applies to white. What these tricks do is make the program
weaker. No matter who is in danger the evaluation gets wrong. And wrong
after a long random playout means _very wrong_.

Jacques.


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

[computer-go] SGF parsing

[Jacques Basaldúa]

Joshua Shriver wrote:


Any help is appreciated, trying to write a parse in C


There is free source code for that:

http://www.red-bean.com/sgf/sgfc/index.html

and GnuGo http://www.gnu.org/software/gnugo/

If you want to do something minimal for testing an engine,
you only have to find: board size SZ[] komi KM[] and
the moves ;B[];W[] the file should have only one starting
"(" and one final ")" i.e. no variations.

If you want to extract a variation from a file that contains
many, you can use GoKnot using "Save as" and the file type
"Smart Game Format (Current variation only)" i.o the default
"Smart Game Format (All variations)" 


Jacques.

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

Re: [computer-go] 9x9 games wanted and the next big challenge

[Jacques Basaldúa]

Except for the relation between not finding 9x9 games
which is *not* real go, you can find as many 19x19 games
as you want, I agree with Chrilly.

Let's accept it. We are amateurs, all except those who
are paid by some University to research on go. And even
some of them are, because a serious go project takes many
years and some have one semester. We have other jobs and
(at least myself) try to work less for the money and dedicate
20 hours per week to go programming. We would be very happy
to work 60 hours a week on go programming if someone else
paid the bills, but that's not the case. I my opinion, the
most important software project of the decade, i.e.
writing a non-Microsoft _compatible_ operating system, is
called wine http://www.winehq.org/ and also looks amateurish.
(I don't really know who works there.) 3D studio and other
successful projects started as amateur job, so there is nothing
wrong in being amateurs.

There is no program today which is so much better than free
programs that is worth paying for it, so we can't blame
the users. We should blame ourselves for not being able to
write a program that is worth its price.

Also, I don't even doubt that the day computer go can challenge
the strongest pro player, the media will understand the importance
of the event. (In fact, computer go is already in the media: The
Economist, The Times, Scientific American, Abcnews, Reuters, have
all written articles in 2007.) And companies will understand that
if they want their names related to a historical event like that
with no possible repetition in the future, something like the
first man on the moon, they will have to pay for it. The money
payed for deep blue will be like comparing 1950s with 2007s
football contracts. "Go is played only by a small freak community."
That's not true. Like chess players were admired in the previous
century as superintelligent human beings and today no one is
interested in chess except the chess community. Go still keeps the
"supreme form of intelligence" myth. And after go, there is void.
Of course, you can always invent new games, but you cannot invent
millenary games with millions of players.

Someone is going to make millions with this. Don't know when, don't
know how. I wish I knew ;-)


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

[computer-go] Re: computer-go Digest, Vol 36, Issue 6

[Jacques Basaldúa]

terry mcintyre wrote:

Lately, I've been studying joseki, and I find that it's hard to really 
know a joseki until you know why non-joseki moves are bad - and why moves 
which are locally joseki may be bad in relation to other stones on the 
board.


No doubt. That is the most complicated part. I have found nothing effective 
for that, although I have some ideas. Anyway, a program that "understands"

joseki well enough to play each corner correctly even if not in relation
with the other corners, is playing better than a program which does not
understand joseki at all.

Jacques.

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

Re: [computer-go] Explanation to MoGo paper wanted.

[Jacques Basaldúa]

Don Dailey wrote:


For instance, in a set of master games what feedback do I have about
each move other than that it was chosen?   How do I get the opinion of
the master player concerning the moves played and not played? 


Just an example: Search corner joseki sequences played often enough. 
Once you know where the player can play some alternative move (because
you only learn "popular" sequences found in many games) or play tenuki 
(in this context, tenuki is a move outside the corner we are studying) 
_then_ use UCT simulations (measuring territory differences, not % of 
wins) to determine the temperature of each move by comparing the 
simulation with the move and the simulation with a pass instead. 
(Of course, not for passing, but for playing elsewhere). Your joseki 
database will have: the moves, their alternatives and the price you play 
for abandoning the sequence at a given point.


Good style: In the case of good style, its is not really important 
to understand why good style is good. You will only study the move

before the others, you won't necessarily play it. With limited time
resources (i.e. always) studying good style moves before should give
the program better style, but as the result of search (i.e. online
knowledge). Again we integrate "human style" with what a computer
understands.


Far better, if you want to involve human players, is some kind of human
assisted learning where games are played and learning takes place by
trial and error and direct interaction with the "teacher." But this
isn't very practical for machine learning which likes thousands of
examples to work from.


Here and in the rest of your post, I agree. We have to learn from 
strong players but we do not talk the same language ( unless they write
programs, of course ;-) ). Their brain directs them to the good moves 
only. They filter bad moves so automatically, they don't realize that 
there are 250 stupid legal moves or more on a board and what consequences
this has. Handcrafted databases are not a good idea for statistical 
analysis, but of course they have other good uses. E.g. not filling 
your own eyes is easily implemented as a handcrafted database.



Jacques.


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

[computer-go] How can one possibly design an optimal playout agent

[Jacques Basaldúa]

Peter Drake wrote:

1) If the computation necessary to find better moves is too  
expensive, performing many "dumb" playouts may be a better investment.


2) If the playouts are too deterministic, and the moves are merely  
pretty good, the program may avoid an important move and thus  
misjudge the value of a position.


Chris Fant wrote:


IMO, this is the most interesting part of Computer Go today.  How can
one possibly design an optimal playout agent when making a playout
agent that plays strong is not the solution?  The only known method
seems to be trial and error.


That is the key question of UCT. I totally agree with Peter's conditions
and add another two: 3) (should be 1) _Unbiased_ ! The smallest bias 
ruins everything. and 4) Low variance.


Low variance is the clue for improvement.

A random move is almost as bad as a pass move. E.g. you can win against
a random player by passing your first 180 moves. (I did it with Idiotbot
which is not exactly a random player.) As an approximation, if you 
consider a random move as bad as a pass move, the blunder per move ratio

would be equal to the temperature of the game. You are evaluating the value
of the game real by summing:

v_eval = v_real + t1 - t2 + t3 - t4 + ...

The condition of no bias is:

E[v_eval] = E[v_real]  <=>  E[t1 - t2 + ...] = 0

If the playout was perfect, you would evaluate

v_eval = v_real + 0 - 0 + 0 - 0 + ...

and you would only need one playout.

The variance of the estimator strongly depends on the variance of the
Bernoulli process (= the "blunder per move ratio" if we put it that way)
in a way that produces v_eval -> 1/2 when |ti| grows or n grows.

It is not true that improving the playout is unimportant. Syvain does not
claim that neither. I have read him stating the it is important. But you
have to follow the rules:

  minimize "blunder per move ratio"

  subject to: The game is unbiased, fast and random enough

Some fast ideas could be favoring the moves near the precomputed
border of the territory to be defended (ownership maps) or similar
ideas that may be fast, unbiased and reduce "blunder per move ratio"

Jacques.

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

Re: [computer-go] Explanation to MoGo paper wanted.

[Jacques Basaldúa]

Don Dailey wrote:

I have posted before about the evils of trying to extract 
knowledge from human games. I don't think it is very effective 
compared to generating that knowledge from computer games for 
several reasons.


I would agree if we could have quality games played by computers.
In 19x19, of course. But because computer moves are so vulgar 
when they are tesuji it is because a search has found a killer 
move, not because the program has good style. The killer moves
only apply to that position exactly (or a local subgame whose 
limits are not trivial to determine). There is not much to learn

from killer moves. What programs need to learn is style and from
programs you only learn bad habits.

Jacques.

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

[computer-go] Re: computer-go Digest, Vol 36, Issue 5

[Jacques Basaldúa]

George Dahl wrote:

Is it still cheating if the program learns and discover's 
the patterns itself? Then isn't it just precomputing a few 
things?


I agree. Many chess and go grand masters, e.g. Capablanca
are supposed to have learned the game as children by watching 
others play. I do intensive research on my 50K masters games 
and for me, mastering the game by learning from the masters 
is the supreme form of intelligence. Except "copying" a full

board, of course. But full board databases also make sense
because they save time and avoid the "empty sheet syndrome"
(i don't know how that is called in English) writers suffer.
There in not much to reason about an empty board.

Jacques.

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

Re: [computer-go] Explanation to MoGo paper wanted.

[Jacques Basaldúa]

Hi, Magnus

Magnus Persson wrote:

Weak tactics is a problem of the playouts in my opinion. 
UCT as a general search method has thus little to do with 
ladders and other game specific details. If there are no 
tactical mistakes in the playouts the problems disappear. 
Also tactics has a large impact on where territory appears 
in the playout, since much of the noise in the playouts come 
from tactical mistakes near the end of the game.


I was meaning the specific problems already mentioned in this 
list where you should not start something (e.g. a ladder)

unless you a sure to win. The more you play (if you don't win)
the more you lose. The best move is "hidden" by the increasingly
negative evaluation of continuing the ladder another step and
losing it. In a 9x9 board, ladders may no be very long, but in
19x19 they can. Of course, in the case of ladders that has simple
solutions as forcing the playout to follow the atari-lines, but 
in more complex situations there is no known (to me) solution.
Of course, UCT would find the optimal solution with infinite 
time, but that is not the question. In fact, it is harder

to find the solution with UCT than with non stochastic methods.


Jacques.


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

Re: [computer-go] Explanation to MoGo paper wanted.

[Jacques Basaldúa]

chrilly wrote:

The results in Go are spectacular, because the quality of 
conventional evaluations is low.


There is more than that. As the proverb states "Go is a 
territorial game". You win a game of go by wining points
and at the end one point is one point no matter where it 
is. This accumulative nature of go is in the base of why

UCT works so well having some known inappropriate features
(E.g. ladders and many tactics, where the best move is 
found very late, if at all.) I don't think this applies to

chess, but I have never tried.

Jacques.

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

Re: [computer-go] correspondence or turn-based servers

[Jacques Basaldúa]

terry mcintyre wrote:

Computer Go play in general is nowhere close to dan-level play, 
but a computer program can read out smaller tactical problems 
with a very high level of accuracy.


That is true. Computers can analyze closed positions as Thomas 
Wolf's go tools at dan level, but ..


.. If in a real game you reach such a position (certainly not 
before move 100) and the game is still so close that the 
analysis matters, then you are as strong as your opponent. You
may win a game you wouldn't have won otherwise, but that gives 
you perhaps only 50 additional Elo points because it won't happen

frequently enough. Also, testing against the computer will reveal
some mistakes you may have overlooked and make your play a little 
stronger, but it is still = your level + something small.


Jacques.


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

Re: [computer-go] scalability study - final results

[Jacques Basaldúa]

Don Dailey wrote:

> I don't know if this is very popular any longer due to the
> Internet but I'm going back a few years.

I am afraid today a postal chess game is a computer analyst
against another computer analyst. An interesting challenge,
no doubt, but that has little to do with chess.

Another reason to prefer go. ;-)

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

Re: [computer-go] Congratulations to GNU and to MoGoBot19!

[Jacques Basaldúa]

steve uurtamo wrote:

> true, and a good point.  time management other than attempting
> to equally divide remaining time among the expected number of
> remaining moves (which itself isn't so easy to estimate) is
> complicated.

But that is so much better than human time management!

If the expected number of moves is based on applicable experience
(including, maybe other games with the same opponent) and is updated
as the move number increases, just the same as a 70 year old person
has a longer life expectation than a 10 y.o. just for having survived
70 years, it will not experience serious problems.

Humans, like myself, who do not take part in tournaments want to have
at least 1/3 of our time unused to avoid "time pressure". Competitors
may feel confident with just 5% of their time remaining, but that
forces errors that would not have been played otherwise.

Humans spend time looking at a clock, and are distracted by doing so.
If the remaining time is small, they "reschedule" looking at the clock
again soon, which adds extra pressure.

Computers feel comfortable with any time settings, and no matter how
naif the scheduling algorithm is, it will always be far better than
human scheduling. Computers can safely approach using 99.999% of their
time (asymptotically) and there is no other reason why a computer should
lose on time than net lag. The reason for extra time (of any kind) is
that humans are lost when they run out of time. Therefore, it clearly
favors humans, because they would have lost that game.


Jacques.

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

[computer-go] Opening

[Jacques Basaldúa]

Heikki Levanto wrote:

> I am sure there is a mathematically sound way to measure
> how symmetric the evaluation is, but my math is a bit rusty,
> so I am asking if someone can come up with a good way. After
> that, I'm asking if various programmers would be willing to
> run this test, and publish the results?

A simple idea:

 1. Even if you have 3 different types of symmetry ..

a. X symmetry (x,y) v.s. (bs+1-x, y)
b. Y symmetry (x,y) v.s. (x, bs+1-y)
c. Center symmetry (x,y) v.s. (bs+1-x, bs+1-y)

(bs+1 = board size + 1 assuming 1-based indices for clarity.)

.. it is clear from their expression that the third is implied
by the first 2.

 2. You could use a simple measure of skewness:

http://www.itl.nist.gov/div898/handbook/eda/section3/eda35b.htm

Note that skewness measures the *lack* of symmetry.

Two measures: One for X and one for Y

 3. Possible objections: Since these measures use the third
moment of a distribution, they are very sensible to the deviation
for the mean. In other words: skewness between the 2nd and 18th row
of a 19x19 board weight much more than between the 9th and 11th.
To compensate this, you can compute another estimator with the
rows (same for the columns) inverted in each half board.

Toggle columns:
 1 <-> 9 and 11 <-> 19
 2 <-> 8 and 12 <-> 18
  ...

so you would have 4 estimators: X-direct, X-inverted,
Y-direct, Y-inverted. Use the highest, i.e., the worst.


Jacques.

Java is a religion. Asm hackers don't spend valuable picoseconds
arguing with Believers.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] OSS or Free Engines

[Jacques Basaldúa]

Hola, Eduardo

Eduardo Sabbatella wrote:

> Take a look at:
> http://sourceforge.net/projects/javago

I get a "This project has not yet created any file
release packages." message at the mentioned URL.

In one of your recent posts you mentioned "data mining"
and that is what I am interested to see how and what
you had implemented.

Will that be part of your package? Will it be documented?

I also have many ideas from statistical analysis that I want
to test. In fact I am reformulating all my ideas that worked
well on selected endgame problems but could not handle
real games to statistical form. I have finally convinced myself
that in go when you have a certitude about whatever it is
always too late ;-) (Exaggerating, of course.)


Jacques.


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

Re: [computer-go] Efficiently selecting a point to play in a random playout

[Jacques Basaldúa]

Thank you for your ideas.

The shapes Rémi is using have values as high as 143473. Of course, that
would invalidate my idea. But I planned trimming the upper probability to
a reasonable number, say 100 as scaling everything to a 1..100 scale (in
the runtime database). I don't know yet if that makes any difference for
random playouts, but I suspect it doesn't. The real application of a good
distribution over the legal moves is searching, and that does not require
any trimming.

Rémi, are your values the result of learning in masters games?

I keep a "best quality" (= no tricks) database of urgencies and a compacted
one with rounded scores and some tricks for compacting it even more which
result in minor score differences.

I my case, Rémi's idea is not applicable because the size of the patterns
makes 9 lines ~ 50% of the board, while 40 neighbors are maximum 11%
of the board (in case they all were legal moves). 50% is not really too
different from rescanning everything (which is simpler).

> .. but adding knowledge and high-level algorithmic improvements
> is tremendously more profitable in terms of playing strength than
> finding tricks to accelerate playouts.

Of course. But one day you have to care about these things. If you
do it well, you will never have to look at that code again. If you
don't, you will have a known or ignored problem forever.

The main reason for caring about doing things the right way is
not having to care again. ;-) I am sure you agree because you
also took the time to find the best solution for your case.

Jacques.

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

[Jacques Basaldúa]

For the problem in which moves have probability in {0, 1/n} of
being selected (n = number of legal moves or empty points
depending on the approach), what Don does, i.e.:

Keeping a vector of selectable/not selectable points with a moving
limit: When you have to fill a gap, do it immediately by moving one
from the border to the selectable area, sounds the best for me.

But, how do you handle draws with different probabilities ??

Of course, it is trivial (but slow) if you add them all and keep an
array of accumulated probabilities.

I created something I call a ticket based lottery. Moves (legal in
my case) "buy" tickets. An average move buys, say 10 tickets,
the worst possible move buys just 1 and the most urgent buys
100. Of course these numbers should be tested empirically,
because, the higher, the slower. (About 20 clockcycles per
ticket. ~6ns·n is the difference between allocating 1 and allocating
n (5 asm instructions)).

And tickets are allocated in something similar to Don's idea.

I have also considered doing multiple tickets just like coins.
Having tickets of x1 and a separate tickets of x5 or some
other value.

Any ideas ?

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

[Jacques Basaldúa]

Hola, Álvaro:

Álvaro Begué wrote:

> "Could not compile libego" is not a very helpful error message. What
> exactly did the compiler complain about? My guess is that you don't
> have the required boost libraries installed.

Yes. It must be that. I didn't know about boost libraries. Where can I 
find that?


> Actually, in order to get the content of a
> particular point, we ask its neighbor on the right :) .

My biggest patterns are up to 40 neighbors (Manhattan distance <= 4) because
that includes all nobi, iken tobi, niken tobi, keima and ogeima 
relations (+ more)

and because it makes a difference between the third and the fourth line and
between the fourth line and above. But, as you do, I use the nearest 
neighbors
in the lower bits as indices of many LUTs that give immediate answers to 
lots

of questions.

> Oh, I would be curious to see how you remove a captured string with
> no loops.

So would I. I did not say that the whole program is in assembly language.
The assembly language parts are rather short and straightforward. I change
conditional jumps by table xlat or by conditional moves. For instance, a
function that computes a Zobrist hash of a mask, cmoves a zero and xors
zero rather than jumping around the xor instruction if there is no stone.

And of course, rather than writing something ridiculously academic, like:

Function DoWhateverWith40neighbors(x, y : integer)
for dx := -4 to 4 do begin
  for dy := -4 to 4 do begin
if (x + dx >= 0)
and (x + dx < 19)
and (y + dy >= 0)
and (y + dy < 19)
and (ABS(dx - dy) <= 4) do whatever
end everything

I keep 81 different asm functions for each possible mapping of the borders

Instead of calling a function:

  MyFun(x, y, a, b, c)

I call

  MyFun[wMv9x9](a, b, c)

where MyFun[wMv9x9] is a array of pointers to functions and x, y are
implicit in the function called.

Example:

UpNeib_NI[wMv9x9](byte(bijNP), longint(pS), CardinalsBPR);

is compiled to:

mov  esi,[esi*4+UpNeib_NI]
xor  eax, eax
mov  al, bl
mov  ecx, [CardinalsBPR}
mov  edx, [ebp-$30]
call esi

(It wouldn't be better with a call to a fixed address.)

And the function, instead of the ridiculous loops and conditions is,
(say 150 lines) of:

  or  [edi + 2], al
  shl al, 4
  or  [edi + 1 + 12], al
  mov al, [edx + ecx*2 - SizeOf_bccCell + 3]
  xlat
  shl al, 2
  or  [edi + 1 + 12], al
  shl al, 4
  or  [edi + 2], al
  mov al, [edx + ecx*4 + 3]
  xlat
  or  [edi + 4], al
  or  [edi + 4 + 12], al
  add edx, ecx
  mov al, [edx + ecx*2 + SizeOf_bccCell + 3]
  xlat
  shl al, 2
  or  [edi + 4], al
  shl al, 4
  or  [edi + 6 + 12], al
  mov al, [edx + ecx + 2*SizeOf_bccCell + 3]
  xlat
  shl al, 4

Now you understand why the board has over 80 000 lines of
asm source. Typical 40 neighbor functions have 81 clones and
150 lines.

It is only in these functions where there are no conditional jumps
or loops, not in the program. But I keep trying ;-)


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

Re: [computer-go] Efficiently selecting a point to play in a random playout

[Jacques Basaldúa]

Lukasz Lew wrote:

> Is libego too complicated? Do You have problems with compilation?
> Or You are not comfortable with the GNU license? Any other reason?

I only wanted to compare performance ( and see what good ideas
you had ;-) ) but could not compile libego. Neither with Microsoft
Visual Studio nor with Borland Turbo C++. I am 100% Borland
because of the ease of assembly language implementation. Borland
passes parameters in CPU registers in a documented way and has
an extremely straightforward use of local variables and record
structure from asm source code to write things easily that work
on the first run.

At least for Windows programmers, providing a solution that
compiles with major IDEs would help. I assume what you do is
"standard" in Linux, but the things the compiler did not understand
neither did I, and I could not find the time for "googleing".

Anyway, I think a go board system is way too important to be
universal. I already have a board system in GoKnot that surely
outperforms most of the current programs and my new board
system I call HBS (Hologram Board System) does not copy
a single line from the old one. I call it a hologram because, as
in a hologram, each part contains information about the whole
picture. In my board, each cell contains a mask of its nearest
neighbors. When you place a stone, everything is updated
by automatically written assembly language functions. These
functions do not have variables except CPU registers and the
board, do not have conditional jumps or loops, of course,
no stack frames, of course support multi-threading, etc. The
board is *never* rescanned whatever happens. Placing a
stone on a 31x31 board is not a clockcycle slower than on
a 9x9 board (these are my limits) assuming it "finds" the same
chains. Every bit of info on the board is only updated if it
may have changed and only once.

With this board I will be able to try things that cannot be tried
with libego, but as Don said, "If you have a hammer, everything
looks like a nail.", for lots of methods not using shapes my board
is way too heavy, (although possibly faster than most  in small
pattern modes) so I will write engines with shapes (and Statistics)
for a while.

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

[computer-go] June KGS Computer Go tournament: 19x19, an hour each

[Jacques Basaldúa]

We all think about UCT all day long, ;-) but universal time is called 
UTC. The acronym is far from obvious, because:


"The International Telecommunication Union 
 
wanted Coordinated Universal Time to have a single abbreviation for all 
languages. English  
speakers and French  
speakers each wanted the initials of their respective languages' terms 
to be used internationally: "CUT" for "coordinated universal time" and 
"TUC" for "temps universel coordonné". This resulted in the final 
compromise of using UTC." as I quoted from 
http://en.wikipedia.org/wiki/Coordinated_Universal_Time


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

Re: [computer-go] Progressive unpruning in Mango 19x19

[Jacques Basaldúa]

I am not an English speaker. I read both verbs for the first time in a 
mid-80s MS/DOS program called PC-Tools (Central Point Software). It was 
the first MS/DOS program that was able to move a complete directory from 
one path to another and it called that "pruning" and "grafting". Since 
then, many people I have read use "graft" as the opposite of "prune". In 
computing I thought that was the usual procedure. ( I also read the word 
"hardware" for the first time related with computers so my English 
perception may be a little focused ;-) )


Jacques.

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