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

[Rémi Coulom]

Jacques Basaldúa wrote:

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


Yes. I took data from a learning experiment based on very few games. So 
there may be a little overfitting. Still, the ratio between the 
strongest and the weakest patterns is always very big.


I'll run some experiments with more random simulations (by 
exponentiating the gammas by a constant < 1). Maybe it would produce 
better play.


Rémi
___
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

[Rémi Coulom]

Peter Drake wrote:

On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote:

Also, if you have a clever probability distribution, the range of 
values for each move will be very large. For instance, here are two 
3x3 shapes used by Crazy Stone (# to move):


 O O #
 # . .
 # O #
Gamma = 143473;

 . # #
 . . .
 . . .
Gamma = 20;

Playing in the empty corner has gamma = 1. So that would be a lot of 
tickets to distribute.


Is this distribution something like the number of times a given move was 
played in your training set?


No. It is explained in my Amsterdam paper:
http://remi.coulom.free.fr/Amsterdam2007/



Doesn't the "play in empty space" pattern swamp everything else?


No. Gamma = 214 for that one.

Rémi
___
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

[Rémi Coulom]

Darren Cook wrote:

I've been messing around with where to apply heuristics. Candidates
include:

1) In the UCT tree, since this is earliest in each playout.
2) In the moves beyond the tree ("heavy playouts"), since this is where
most of the moves happen. Because this part is so speed-critical, ...


Remi (using learned patterns instead of heuristics, but should be the
same) got dramatic improvements doing both (see quote below).

It is also my understanding that in Crazy Stone the patterns are being
used at every ply in the playouts; given that the program is being given
a constant time it seems the overhead of this is more than made up for
by the increase in strength.

Darren


Interestingly, I got no overhead when I added 3x3 patterns. It even made 
simulations faster, because detecting illegal moves or moves into eyes 
came for free.


Rémi
___
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

[Darren Cook]

> I've been messing around with where to apply heuristics. Candidates
> include:
> 
> 1) In the UCT tree, since this is earliest in each playout.
> 2) In the moves beyond the tree ("heavy playouts"), since this is where
> most of the moves happen. Because this part is so speed-critical, ...

Remi (using learned patterns instead of heuristics, but should be the
same) got dramatic improvements doing both (see quote below).

It is also my understanding that in Crazy Stone the patterns are being
used at every ply in the playouts; given that the program is being given
a constant time it seems the overhead of this is more than made up for
by the increase in strength.

Darren


--
In the computer-go "Amsterdam 2007 paper" thread, on 2007-05-18:

Here are tests of Crazy Stone at 90s/game 1CPU against GNU 3.6 level 10,
measured over about 200 games:
no pattern: 38.2% (version available on my web page)
patterns in simulations:68.2%
patterns for pruning and simulations:90.6%
I found these number in my history of Crazy Stone versions, so they may
not be extremely accurate, because other things have changed in between.
I will run cleaner tests for the final version of the paper. I will also
try to test what each feature brings.

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

Heavy playouts (was Re: [computer-go] Efficiently selecting a point to play in a random playout)

[Peter Drake]

Let me mildly retract this and say that method 2 appears to be better  
than method 1.


Peter Drake
http://www.lclark.edu/~drake/



On Jun 6, 2007, at 2:51 PM, Peter Drake wrote:

I assume you mean "...than finding tricks to accelerate RANDOM  
playouts".


I've been messing around with where to apply heuristics. Candidates  
include:


1) In the UCT tree, since this is earliest in each playout.
2) In the moves beyond the tree ("heavy playouts"), since this is  
where most of the moves happen. Because this part is so speed- 
critical, some trick often has to be used so that you don't  
evaluate every possible move on every simulated turn. Options include:
	2a) Pick N possible moves and choose the one the heuristic likes  
best. (N might be 3 or so.)
	2b) Only apply the heuristic on the first N moves beyond the  
fringe of the tree.


It currently looks like 2b is by far the best place to apply  
heuristics. Do others have conflicting results?


Peter Drake
http://www.lclark.edu/~drake/



On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote:

I am sure it could be made significantly faster, but adding  
knowledge and high-level algorithmic improvements is tremendously  
more profitable in terms of playing strength than finding tricks  
to accelerate playouts.


Rémi




___
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

[Peter Drake]

On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote:

Also, if you have a clever probability distribution, the range of  
values for each move will be very large. For instance, here are two  
3x3 shapes used by Crazy Stone (# to move):


 O O #
 # . .
 # O #
Gamma = 143473;

 . # #
 . . .
 . . .
Gamma = 20;

Playing in the empty corner has gamma = 1. So that would be a lot  
of tickets to distribute.


Is this distribution something like the number of times a given move  
was played in your training set?


Doesn't the "play in empty space" pattern swamp everything else?

Peter Drake
http://www.lclark.edu/~drake/



___
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

[Peter Drake]

Thanks for the tip. It does seem a bit faster (5% speedup of the  
program overall), and I'm willing to accept the consensus that the  
randomness is better.


Peter Drake
http://www.lclark.edu/~drake/



On Jun 6, 2007, at 2:15 PM, Graham Thomson wrote:

I would be weary of using java.util.Random - it is not that random:  
http://alife.co.uk/nonrandom/.


A drop in Mersenne Twister replacement for java.util.Random is  
available at http://cs.gmu.edu/~sean/research/.



Cheers,

Graham.

On 05/06/07, Peter Drake <[EMAIL PROTECTED]> wrote:
>
>
>
> Oddly, there doesn't seem to be much effect on speed whether I  
use a single random number generator (i.e., instance of  
java.util.Random) or one for each thread.

>
>
> Peter Drake
> http://www.lclark.edu/~drake/
>
>
>
>
>
>
> On Jun 5, 2007, at 11:59 AM, Jason House wrote:
>
>
>
>
>
> On 6/5/07, Peter Drake <[EMAIL PROTECTED]> wrote:
> >
> > On a multithreaded program like Orego (running on a multicore  
machine), it moves the nontrivial random number generation out of  
the synchronized part of the program and into the threads.

>
> I'm surprised to hear this.  Do you have a single random number  
generator?  In housebot, Each thread has its own random number  
generator instance.  Besides avoiding a bottleneck as each thread  
generates random numbers, it also opens the door for repeatable  
behavior in a single worker thread.

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

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


___
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

[Álvaro Begué]

On 6/6/07, Rémi Coulom <[EMAIL PROTECTED]> wrote:

Álvaro Begué wrote:
>
> Actually, John had a better idea to do this. In two words: binary
> tree. The root represents the whole board, and it contains the sum of
> the probabilities of all the points (you don't need to force this to
> be 1, if you use non-normalized probabilities). This node points to
> two nodes, each of which represents about half the board and contains
> the sum of the probabilities of all the points in its half. You keep
> going down the tree until eventually you get to nodes that represent
> individual points, with their probabilities. Picking a random move
> according to the desired distribution now takes O(log(board_size))
> (just toss biased coins at each level of the tree to decide whether to
> follow the left subtree or the right subtree). Updating the
> probability of a point also takes O(log(board_size)).
>
> I wonder if other people had thought about this before...
>
> Álvaro.

Yes, I did it in the beginning. But I found that it is faster to divide
by more than two. Currently, I keep the probability of the whole board,
each line, and each point. It is simple, and more efficient than a
binary tree.

Rémi


That makes perfect sense! We will try that scheme instead.

Thanks!
Álvaro.
___
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

[Peter Drake]

I assume you mean "...than finding tricks to accelerate RANDOM  
playouts".


I've been messing around with where to apply heuristics. Candidates  
include:


1) In the UCT tree, since this is earliest in each playout.
2) In the moves beyond the tree ("heavy playouts"), since this is  
where most of the moves happen. Because this part is so speed- 
critical, some trick often has to be used so that you don't evaluate  
every possible move on every simulated turn. Options include:
	2a) Pick N possible moves and choose the one the heuristic likes  
best. (N might be 3 or so.)
	2b) Only apply the heuristic on the first N moves beyond the fringe  
of the tree.


It currently looks like 2b is by far the best place to apply  
heuristics. Do others have conflicting results?


Peter Drake
http://www.lclark.edu/~drake/



On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote:

I am sure it could be made significantly faster, but adding  
knowledge and high-level algorithmic improvements is tremendously  
more profitable in terms of playing strength than finding tricks to  
accelerate playouts.


Rémi


___
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

[Rémi Coulom]

Jason House wrote:



On 6/6/07, *Rémi Coulom* <[EMAIL PROTECTED] 
> wrote:


 > I wonder if other people had thought about this before...
 >
 > Álvaro.

Yes, I did it in the beginning. But I found that it is faster to divide
by more than two. Currently, I keep the probability of the whole board,
each line, and each point. It is simple, and more efficient than a
binary tree.

Rémi


I'm not clear on how you efficiently index into which line to select.  I 
think the discussion here is still relevant to that.  If we take a 
simple example of a 5x5 board where the line weights are 
{15,10,30,20,25}, and I roll the dice and compute 44 (out of 100), I 
don't know to jump instantly to the 3rd entry; other information is 
needed if a sequential check is to be avoided.  Tokens of 5 could make 
it easy to pick a number from 1 to 20 and then jump to the row owned by 
that token, and a binary tree could result in ~3 comparisons... not much 
better than a sequential check at such a small number of lines.


I do a sequential check.

It is important to understand that it is worthless to be able to pick a 
move extremely rapidly, if updating the related data takes a lot of 
time. With 3x3 patterns, 8 points have their urgencies updated after 
each move. Updating the probability distribution is the time-critical 
part of the algorithm, not picking one move at random. With my 
algorithm, I have to update 3 values each time the urgency of a move 
changes. With a binary tree, I would have to update 8 in 9x9, and 10 in 
19x19.


Also, if you have a clever probability distribution, the range of values 
for each move will be very large. For instance, here are two 3x3 shapes 
used by Crazy Stone (# to move):


 O O #
 # . .
 # O #
Gamma = 143473;

 . # #
 . . .
 . . .
Gamma = 20;

Playing in the empty corner has gamma = 1. So that would be a lot of 
tickets to distribute.


Simple straightforward algorithms often work well. I do not do anything 
extraordinary in Crazy Stone, and, on 9x9 from the empty board, it still 
runs 21,700 simulations per second on a 2.6 GHz opteron (20,400 with the 
tree-search logic).


I am sure it could be made significantly faster, but adding knowledge 
and high-level algorithmic improvements is tremendously more profitable 
in terms of playing strength than finding tricks to accelerate playouts.


Rémi
___
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

[Graham Thomson]

I would be weary of using java.util.Random - it is not that random:
http://alife.co.uk/nonrandom/.

A drop in Mersenne Twister replacement for java.util.Random is available at
http://cs.gmu.edu/~sean/research/.


Cheers,

Graham.

On 05/06/07, Peter Drake <[EMAIL PROTECTED]> wrote:




Oddly, there doesn't seem to be much effect on speed whether I use a

single random number generator (i.e., instance of java.util.Random) or one
for each thread.



Peter Drake
http://www.lclark.edu/~drake/






On Jun 5, 2007, at 11:59 AM, Jason House wrote:





On 6/5/07, Peter Drake <[EMAIL PROTECTED]> wrote:
>
> On a multithreaded program like Orego (running on a multicore machine),

it moves the nontrivial random number generation out of the synchronized
part of the program and into the threads.


I'm surprised to hear this.  Do you have a single random number

generator?  In housebot, Each thread has its own random number generator
instance.  Besides avoiding a bottleneck as each thread generates random
numbers, it also opens the door for repeatable behavior in a single worker
thread.


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

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

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

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

[Jason House]

On 6/6/07, Rémi Coulom <[EMAIL PROTECTED]> wrote:


> I wonder if other people had thought about this before...
>
> Álvaro.

Yes, I did it in the beginning. But I found that it is faster to divide
by more than two. Currently, I keep the probability of the whole board,
each line, and each point. It is simple, and more efficient than a
binary tree.

Rémi



I'm not clear on how you efficiently index into which line to select.  I
think the discussion here is still relevant to that.  If we take a simple
example of a 5x5 board where the line weights are {15,10,30,20,25}, and I
roll the dice and compute 44 (out of 100), I don't know to jump instantly to
the 3rd entry; other information is needed if a sequential check is to be
avoided.  Tokens of 5 could make it easy to pick a number from 1 to 20 and
then jump to the row owned by that token, and a binary tree could result in
~3 comparisons... not much better than a sequential check at such a small
number of lines.
___
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

[Rémi Coulom]

Álvaro Begué wrote:


Actually, John had a better idea to do this. In two words: binary
tree. The root represents the whole board, and it contains the sum of
the probabilities of all the points (you don't need to force this to
be 1, if you use non-normalized probabilities). This node points to
two nodes, each of which represents about half the board and contains
the sum of the probabilities of all the points in its half. You keep
going down the tree until eventually you get to nodes that represent
individual points, with their probabilities. Picking a random move
according to the desired distribution now takes O(log(board_size))
(just toss biased coins at each level of the tree to decide whether to
follow the left subtree or the right subtree). Updating the
probability of a point also takes O(log(board_size)).

I wonder if other people had thought about this before...

Álvaro.


Yes, I did it in the beginning. But I found that it is faster to divide 
by more than two. Currently, I keep the probability of the whole board, 
each line, and each point. It is simple, and more efficient than a 
binary tree.


Rémi

___
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

[Álvaro Begué]

On 6/6/07, Jacques Basaldúa <[EMAIL PROTECTED]> wrote:

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 ?


Actually, John had a better idea to do this. In two words: binary
tree. The root represents the whole board, and it contains the sum of
the probabilities of all the points (you don't need to force this to
be 1, if you use non-normalized probabilities). This node points to
two nodes, each of which represents about half the board and contains
the sum of the probabilities of all the points in its half. You keep
going down the tree until eventually you get to nodes that represent
individual points, with their probabilities. Picking a random move
according to the desired distribution now takes O(log(board_size))
(just toss biased coins at each level of the tree to decide whether to
follow the left subtree or the right subtree). Updating the
probability of a point also takes O(log(board_size)).

I wonder if other people had thought about this before...

Álvaro.
___
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

[Peter Drake]

This sounds a lot like the "roulette wheel" selection scheme used in  
genetic algorithms. The idea is that each candidate has a different  
slice of a roulette wheel, with better candidates getting bigger slices.


Peter Drake
http://www.lclark.edu/~drake/



On Jun 6, 2007, at 2:07 AM, Jacques Basaldúa wrote:


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/


___
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

[Martin Møller Skarbiniks Pedersen]

-ansi -Wall -pedantic



Why not add -Werror so gcc rejects to compile code with warnings ?

Regards
Martin
___
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

[Don Dailey]

On Tue, 2007-06-05 at 13:12 -0700, Peter Drake wrote:
> > So I'm only temporarily maintaining a list of illegal but unoccupied
> > points - this list gets "discarded" as soon as a legal move is
> tried.
> 
> Does that mean you have to regenerate the list every move?

I keep the list of un-occupied points - but the tiny list of illegal
points
gets regenerated from move to move.

However, this list is so tiny that it rarely amounts to more than 0
moves.  Near the end of the game it could get bigger, but if it does it
is starting to save some real time.   I think this is win/win.

> > What you are doing is to avoid the call to the random number
> generator
> > by
> > trying the moves as a circular list.  This may be faster, but it's
> > biased,  perhaps the bias is insignificant enough that it doesn't
> have
> > an impact on the strength.
> 
> No, I pick a random point in the list every time, so there's still a  
> call to the random number generator. Just proceeding through the
> list  
> would be horribly biased (unless the list were pre-shuffled, as I
> was  
> doing previously). 

So it's possible that in a degenerate case you could pick many illegal
moves over and over again.   Technically, you could get into an infinite
loop if the period of your RNG was such that a legal move could not get
seen.   But I'm being really picky :-)

I am perhaps being too anal making sure I don't choose the same illegal
move twice.   However the code is trivial and it's not a major
difficulty managing. 

But I'm wondering if starting at a random point in a list of unoccupied
points and searching sequentially is really that terrible?Another
idea I have is that when you do hit an illegal point, swap it with a
random element so that this particular bias point is changed for the
next move, then continue to search sequentially for a legal move.   You
could eliminate most of the RNG calls and the swaps.   But there are
probably not that many anyway.

- Don




___
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

[Peter Drake]

On Jun 5, 2007, at 12:58 PM, Don Dailey wrote:


On Tue, 2007-06-05 at 12:28 -0700, Peter Drake wrote:

Don't maintain the list of legal moves -- maintain the list of vacant
points (almost all of which are legal). When it's time to pick a  
move,
pick a random point in the list and iterate through checking each  
move

for legality. As soon as you find a legal one, play it.


But you can do both.  It's simpler than it sounds.  I'm essentially
doing what you suggest, but it's perfectly random, no bias.   And I
doubt there is any cost that can be easily measured.

So I'm only temporarily maintaining a list of illegal but unoccupied
points - this list gets "discarded" as soon as a legal move is tried.


Does that mean you have to regenerate the list every move?


What you are doing is to avoid the call to the random number generator
by
trying the moves as a circular list.  This may be faster, but it's
biased,  perhaps the bias is insignificant enough that it doesn't have
an impact on the strength.


No, I pick a random point in the list every time, so there's still a  
call to the random number generator. Just proceeding through the list  
would be horribly biased (unless the list were pre-shuffled, as I was  
doing previously).



You might improve the bias by "shuffling on the fly", perhaps when you
find a legal move in the un-occupied point section of the list you  
could

do a swap with the first move and a random move.


I did something like this in an earlier version.


I'm wondering if the
biased ordering of the list persists from move to move?

Maybe I benchmark your idea at some point.


Feel free...

Peter Drake
http://www.lclark.edu/~drake/



___
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

[Don Dailey]

On Tue, 2007-06-05 at 15:58 -0400, Don Dailey wrote:
> You might improve the bias by "shuffling on the fly", perhaps when you
> find a legal move in the un-occupied point section of the list you
> could
> do a swap with the first move and a random move.   I'm wondering if
> the
> biased ordering of the list persists from move to move?   

With the presence of illegal moves, this is always biased even with some
shuffling (there is always some move more likely to be chosen that some
other move), but on the first pass (starting from a random list) it
doesn't matter, the bias itself is random (if that makes any sense.)
If the bias changes from move to move, then the whole thing is
effectively random.But it's not time-effective to scramble the
un-occupied points section after every move.

Interesting stuff.  If avoiding RNG is a big saver, then I don't know if
my incremental shuffle slows it down too much.  I also am not sure
whether it introduces enough randomness to make a big difference
(because it still doesn't make it truly random, it just introduces some
chaos to helps the situation.)   

- Don


___
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

[Don Dailey]

On Tue, 2007-06-05 at 12:28 -0700, Peter Drake wrote:
> Don't maintain the list of legal moves -- maintain the list of vacant
> points (almost all of which are legal). When it's time to pick a move,
> pick a random point in the list and iterate through checking each move
> for legality. As soon as you find a legal one, play it. 

But you can do both.  It's simpler than it sounds.  I'm essentially
doing what you suggest, but it's perfectly random, no bias.   And I
doubt there is any cost that can be easily measured.  

So I'm only temporarily maintaining a list of illegal but unoccupied
points - this list gets "discarded" as soon as a legal move is tried.

What you are doing is to avoid the call to the random number generator
by
trying the moves as a circular list.  This may be faster, but it's
biased,  perhaps the bias is insignificant enough that it doesn't have
an impact on the strength.   

You might improve the bias by "shuffling on the fly", perhaps when you
find a legal move in the un-occupied point section of the list you could
do a swap with the first move and a random move.   I'm wondering if the
biased ordering of the list persists from move to move?  

Maybe I benchmark your idea at some point.

- Don



> (My "legality" check does eliminate playing in a probable eye.) 

___
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

[Don Dailey]

On Tue, 2007-06-05 at 15:18 -0400, Jason House wrote:
> Do you eliminate all illegal/stupid positions?  Filling eyes? Suicide
> plays?  Disallowing suicides likely means you need a list for each
> color.  Sadly, if a move was rejected because it was an illegal
> suicide and then the enemy chain puts itself in atari, the simple
> capture move would have been pruned. 

There is just 1 physical list, but I maintain (with indices) 3 sublists:

   1) occupied points
   2) non-occupied points
   3) untried non-occupied points 

So if a point is not occupied but is not legal either,  I "put it behind
me" so it's not considered on this move.  Whenever a move is "put
behind" it is swapped with the current "cursor" and the cursor is
bumped.  So it stays in the non-occupied points section of the list but
still behind the untried section. 

When the move is found to be legal, it is put into the occupied points
section of the list with a swap operation and the index to the first
non-occupied point is incremented.  

When it's time to find the next move,  I start right at the non-occupied
point
section and essentially start rebuilding the short illegal move
section.  

Think of it this way:


| o o o o o o o | i i i | c c c c c c |

o = occupied points
i = illegal moves  (also non-occupied)
c = candidates (also non-occupied)

Both i and c are unoccupied points.

The counter for i and c are the same at the beginning of a search
for a new move.  The "i" list is often null.After a few moves
are played in a game, most of the illegal moves are probably near
the front of the non-occupied points.


It's simpler than my description sounds.   

- Don


___
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

[Peter Drake]

Don't maintain the list of legal moves -- maintain the list of vacant  
points (almost all of which are legal). When it's time to pick a  
move, pick a random point in the list and iterate through checking  
each move for legality. As soon as you find a legal one, play it.


(My "legality" check does eliminate playing in a probable eye.)

Peter Drake
http://www.lclark.edu/~drake/



On Jun 5, 2007, at 12:18 PM, Jason House wrote:




On 6/5/07, Don Dailey <[EMAIL PROTECTED]> wrote:
But if you are taking the vacant points out it is probably not
too biased as you say.

But what I do is pretty fast.  Always choose a random point but
keep shrinking the list.  When a point is occupied move it out
of the way so it's never selected again.   You have to do some
simple bookeeping - basically swapping the position of elements
and shrinking the list (in your terminology, maintaining a set
of empty points.)


Do you eliminate all illegal/stupid positions?  Filling eyes?  
Suicide plays?  Disallowing suicides likely means you need a list  
for each color.  Sadly, if a move was rejected because it was an  
illegal suicide and then the enemy chain puts itself in atari, the  
simple capture move would have been pruned.



I don't think this is any slower than what you are proposing.

I start a random game by collect vacant points - but after a
capture move you have to re-do this operation.   Still, it's 2X
faster to collect vacant points together like (even if you are
doing everything else this way.)


It's likely that you could do an incremental update after a capture  
instead of recomputing the entire list.  The only real issue is any  
moves pruned because of suicides (potentially far away from the  
captured chain, but guaranteed no more than one per neighboring chain)

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


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

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

[Peter Drake]

Oddly, there doesn't seem to be much effect on speed whether I use a  
single random number generator (i.e., instance of java.util.Random)  
or one for each thread.


Peter Drake
http://www.lclark.edu/~drake/



On Jun 5, 2007, at 11:59 AM, Jason House wrote:




On 6/5/07, Peter Drake <[EMAIL PROTECTED]> wrote:
On a multithreaded program like Orego (running on a multicore  
machine), it moves the nontrivial random number generation out of  
the synchronized part of the program and into the threads.


I'm surprised to hear this.  Do you have a single random number  
generator?  In housebot, Each thread has its own random number  
generator instance.  Besides avoiding a bottleneck as each thread  
generates random numbers, it also opens the door for repeatable  
behavior in a single worker thread.

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


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

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

[Peter Drake]

On Jun 5, 2007, at 11:57 AM, Don Dailey wrote:


But if you are taking the vacant points out it is probably not
too biased as you say.


Yes, that's the key point -- almost all vacant points are legal.


But what I do is pretty fast.  Always choose a random point but
keep shrinking the list.  When a point is occupied move it out
of the way so it's never selected again.   You have to do some
simple bookeeping - basically swapping the position of elements
and shrinking the list (in your terminology, maintaining a set
of empty points.)


If I understand you correctly, I'm doing the same thing --  
maintaining the list of vacant points incrementally. Whenever there  
is a capture, I just add the captured points to the list.


Peter Drake
http://www.lclark.edu/~drake/



___
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

[Jason House]

On 6/5/07, Don Dailey <[EMAIL PROTECTED]> wrote:


But if you are taking the vacant points out it is probably not
too biased as you say.

But what I do is pretty fast.  Always choose a random point but
keep shrinking the list.  When a point is occupied move it out
of the way so it's never selected again.   You have to do some
simple bookeeping - basically swapping the position of elements
and shrinking the list (in your terminology, maintaining a set
of empty points.)




Do you eliminate all illegal/stupid positions?  Filling eyes? Suicide
plays?  Disallowing suicides likely means you need a list for each color.
Sadly, if a move was rejected because it was an illegal suicide and then the
enemy chain puts itself in atari, the simple capture move would have been
pruned.


I don't think this is any slower than what you are proposing.


I start a random game by collect vacant points - but after a
capture move you have to re-do this operation.   Still, it's 2X
faster to collect vacant points together like (even if you are
doing everything else this way.)




It's likely that you could do an incremental update after a capture instead
of recomputing the entire list.  The only real issue is any moves pruned
because of suicides (potentially far away from the captured chain, but
guaranteed no more than one per neighboring chain)
___
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

[Jason House]

On 6/5/07, Peter Drake <[EMAIL PROTECTED]> wrote:


On a multithreaded program like Orego (running on a multicore machine), it
moves the nontrivial random number generation out of the synchronized part
of the program and into the threads.



I'm surprised to hear this.  Do you have a single random number generator?
In housebot, Each thread has its own random number generator instance.
Besides avoiding a bottleneck as each thread generates random numbers, it
also opens the door for repeatable behavior in a single worker thread.
___
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

[Don Dailey]

But if you are taking the vacant points out it is probably not
too biased as you say.

But what I do is pretty fast.  Always choose a random point but
keep shrinking the list.  When a point is occupied move it out
of the way so it's never selected again.   You have to do some
simple bookeeping - basically swapping the position of elements
and shrinking the list (in your terminology, maintaining a set
of empty points.)

I don't think this is any slower than what you are proposing.

I start a random game by collect vacant points - but after a 
capture move you have to re-do this operation.   Still, it's 2X
faster to collect vacant points together like (even if you are
doing everything else this way.) 



- Don

  

On Tue, 2007-06-05 at 14:45 -0400, Don Dailey wrote:
> On Tue, 2007-06-05 at 10:23 -0700, Peter Drake wrote:
> > While there is a bias in theory, I suspect that you are right that it
> > is not significant in practice if you maintain a list of vacant points
> > (as Orego now does), because almost all vacant points are legal.
> > 
> > 
> > In any case, switching to your technique (generating one random
> > starting point in the list when it's time to choose a random move
> > rather than shuffling the list at the beginning of the run) is a big
> > speed win. 
> 
> This is horribly non-random.To illustrate,  imagine that only 2 move
> are
> legal and they are right next to each other.   ALL random choices except
> one 
> would choose the move earliest in the list.
> 
> - Don
> 
> 
> 
> 
> > On a multithreaded program like Orego (running on a multicore
> > machine), it moves the nontrivial random number generation out of the
> > synchronized part of the program and into the threads. This one change
> > instantly got me 25-30% more playouts per second.
> > 
> > 
> > Thanks for the tip!
> > 
> > Peter Drake
> > http://www.lclark.edu/~drake/
> > 
> > 
> > 
> > 
> > 
> > On May 27, 2007, at 11:39 AM, Łukasz Lew wrote:
> > 
> > > Hi,
> > > 
> > > 
> > > I've tested many approaches, and the one I implemented is clearly
> > > the best.
> > > The bias that Peter Drake talks about is negligible and doesn't have
> > > a
> > > noticeable impact
> > > on playout results.
> > > (and uniformity of playout isn't something to fight for in MC Go)
> > > 
> > > 
> > > ...
> > > 
> > > 
> > > 
> > > Best Regards,
> > > Lukasz Lew
> > 
> > 
> > ___
> > computer-go mailing list
> > computer-go@computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> 

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

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

[Don Dailey]

On Tue, 2007-06-05 at 10:23 -0700, Peter Drake wrote:
> While there is a bias in theory, I suspect that you are right that it
> is not significant in practice if you maintain a list of vacant points
> (as Orego now does), because almost all vacant points are legal.
> 
> 
> In any case, switching to your technique (generating one random
> starting point in the list when it's time to choose a random move
> rather than shuffling the list at the beginning of the run) is a big
> speed win. 

This is horribly non-random.To illustrate,  imagine that only 2 move
are
legal and they are right next to each other.   ALL random choices except
one 
would choose the move earliest in the list.

- Don




> On a multithreaded program like Orego (running on a multicore
> machine), it moves the nontrivial random number generation out of the
> synchronized part of the program and into the threads. This one change
> instantly got me 25-30% more playouts per second.
> 
> 
> Thanks for the tip!
> 
> Peter Drake
> http://www.lclark.edu/~drake/
> 
> 
> 
> 
> 
> On May 27, 2007, at 11:39 AM, Łukasz Lew wrote:
> 
> > Hi,
> > 
> > 
> > I've tested many approaches, and the one I implemented is clearly
> > the best.
> > The bias that Peter Drake talks about is negligible and doesn't have
> > a
> > noticeable impact
> > on playout results.
> > (and uniformity of playout isn't something to fight for in MC Go)
> > 
> > 
> > ...
> > 
> > 
> > 
> > Best Regards,
> > Lukasz Lew
> 
> 
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

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

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

[Peter Drake]

While there is a bias in theory, I suspect that you are right that it  
is not significant in practice if you maintain a list of vacant  
points (as Orego now does), because almost all vacant points are legal.


In any case, switching to your technique (generating one random  
starting point in the list when it's time to choose a random move  
rather than shuffling the list at the beginning of the run) is a big  
speed win. On a multithreaded program like Orego (running on a  
multicore machine), it moves the nontrivial random number generation  
out of the synchronized part of the program and into the threads.  
This one change instantly got me 25-30% more playouts per second.


Thanks for the tip!

Peter Drake
http://www.lclark.edu/~drake/



On May 27, 2007, at 11:39 AM, Łukasz Lew wrote:


Hi,

I've tested many approaches, and the one I implemented is clearly  
the best.

The bias that Peter Drake talks about is negligible and doesn't have a
noticeable impact
on playout results.
(and uniformity of playout isn't something to fight for in MC Go)

...

Best Regards,
Lukasz Lew


___
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

[Don Dailey]

On Thu, 2007-05-31 at 12:44 +0100, Jacques Basaldúa wrote:
> I keep 81 different asm functions for each possible mapping of the
> borders

I had a really fast all-at-once move generator for chess that worked
like this.

For each piece type of each color on each square was a separate move
generator.
That's 64x6x2 different functions.   

The advantage was that almost all conditional branching was done away
with. Didn't have to test whether a pawn was on the second rank, seventh
rank, on the edge of the board, etc.   Further advantage is that use
constants instead of variables which was faster on the processors being
used back then (and I think still is.)

This requires (for sanity sake) to write a code generator - a special
program that wrote the code.If you wrote 768 routines by hand you
would be fighting bugs forever.  

This code was really fast back then, but it proved not to be very
efficient on later generation processors.   The concept was good but
this blew out the cache of the machines and it was very odd that it
either was super fast or super slow depending on the computer you
compiled and ran it on.  

Eventually this wasn't even feasible because the program got more
sophisticated and it was spending less and less time on move generation
anyway.

But for something like analyzing the neighborhood around a point this
could be a big win. 

- Don



___
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

[Darren Cook]

>> "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?

http://boost.org/
http://boost.org/more/getting_started/windows.html

Older versions of Borland compilers were notorious for poor standards
compliance. However I believe (as of a year or so ago) Borland had
started using compiling boost as one of their tests, so recent versions
should work well.

Darren


___
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

[Sylvain Gelly]

Hello,

When writing C/C++ for multi-platform student assignments using gcc,

we always used the args:

-ansi -Wall -pedantic



Maybe it depends on the gcc versions, but I always use "-Wall -W" rather
than only "-Wall". "-W" turns on (important) warnings which are not turned
on with only "-Wall", and as usual warnings are much more important than
errors :-).
I agree that it is not related to what is reported here, sorry :).
Cheers,
Sylvain
___
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

[Stuart A. Yeates]

When writing C/C++ for multi-platform student assignments using gcc,
we always used the args:

-ansi -Wall -pedantic

Literally "use the ANSI standard" "turn all warnings on" and "be
pedantic about warnings." This, of course, won't help with libraries
not being found.

cheers
stuart
___
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

[Álvaro Begué]

On 5/30/07, Berk Ozbozkurt <[EMAIL PROTECTED]> wrote:

Álvaro Begué wrote:

>>
>> 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".


Hey, I didn't write that! :)
___
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

[Berk Ozbozkurt]

Álvaro Begué wrote:



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".


With 1.08 version of lego and Turbo C++, there are too many errors 
related to namespaces, system libraries etc.


With *wx-Devcpp*  windows compilation is 
relatively straightforward. Create a new project file (main.cpp and 
gtp.cpp is enough for benchmarking), Replace get_seconds(), install 
boost library (a package is available at devpaks.org if you don't want 
to compile the library) and you are done.


---

float get_seconds () {
   return double(clock()) / double(CLOCKS_PER_SEC);
}

I know this is not a precise way of calculating time, but if it is good 
enough for fruit, it is good enough for me.

___
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

[Álvaro Begué]

On 5/30/07, Jacques Basaldúa <[EMAIL PROTECTED]> wrote:

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".


"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.



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.


Funny that. We store 16 bits per point, where the contents of the 8
neighbours is encoded. Actually, in order to get the content of a
particular point, we ask its neighbour on the right :). John came up
with this and other ideas, like a method to detect if a string is in
atari and to find its last liberty in constant time. We don't rescan
the board either. Well, only once per simulation, but that's not in
the critical section. The only thing you are doing that we are not is
using assembly, but I'd rather keep things flexible and portable at
this point.

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



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.


The reason we don't use libego either is similar. We need a completely
different underlying structure to be able to pick random moves
following the distribution we want. I don't think Lukasz can do
anything to his library so it would satisfy a significant fraction of
programmers, since we all have different needs.

Álvaro.
___
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/

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

[Christoph Birk]

On Sun, 27 May 2007, ?ukasz Lew wrote:

Jason, can You tell me why You don't want to use libego instead?
Actually this is open question to all comp-go readers.

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


I am a C-programmer and I don't like the GPL license.

Christoph

___
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

[Don Dailey]

But I remember thinking that it might still be useful for evaluation.  I
remember thinking that that if you compared pseudo liberties to real
liberties it might tell you something.   If the ratio was high (a lot
more pseudo liberties) it might indicate that the liberties are easy to
protect.   But there was a definite negative response to the idea that
they were useful in any way.

- Don

On Sun, 2007-05-27 at 23:54 -0400, Jason House wrote:
> Don Dailey wrote:
> > I remember that conversation and the negative response.  But to be fair
> > to the ones who were negative, you presented this as an evaluation
> > feature that could be calculated quickly,  not as a pure performance
> > optimization.   The negative response was in response to the suggestion
> > that it might be used as an evaluation feature instead of true
> > liberties.  
> >
> > At least that is how I remember it.
> >   
> 
> Oh, I definitely didn't mean to say or imply that those who gave a 
> negative reaction were wrong.  I apologize if anyone took my post that 
> way!  At the time, MC wasn't a big push in computer go, and I know I 
> wasn't thinking about rapid random games.  You're absolutely right that 
> I was looking to use it as some kind of quick and dirty evaluation 
> feature.  Honestly, I think the feedback was helpful too.  I ended up 
> making a concept of local liberties that were slightly smarter than 
> pseudo liberties and were much more useful for non-MC computations.

___
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

[Jason House]

Don Dailey wrote:

I remember that conversation and the negative response.  But to be fair
to the ones who were negative, you presented this as an evaluation
feature that could be calculated quickly,  not as a pure performance
optimization.   The negative response was in response to the suggestion
that it might be used as an evaluation feature instead of true
liberties.  


At least that is how I remember it.
  


Oh, I definitely didn't mean to say or imply that those who gave a 
negative reaction were wrong.  I apologize if anyone took my post that 
way!  At the time, MC wasn't a big push in computer go, and I know I 
wasn't thinking about rapid random games.  You're absolutely right that 
I was looking to use it as some kind of quick and dirty evaluation 
feature.  Honestly, I think the feedback was helpful too.  I ended up 
making a concept of local liberties that were slightly smarter than 
pseudo liberties and were much more useful for non-MC computations.

___
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

[Don Dailey]

I remember that conversation and the negative response.  But to be fair
to the ones who were negative, you presented this as an evaluation
feature that could be calculated quickly,  not as a pure performance
optimization.   The negative response was in response to the suggestion
that it might be used as an evaluation feature instead of true
liberties.  

At least that is how I remember it.

- Don



On Sun, 2007-05-27 at 20:28 -0400, Jason House wrote:
> Don Dailey wrote:
> > Lukasz Lew does something far more sophisticated and very fast using the
> > concept of pseudo liberties which you might want to look into.
> >   
> 
> Both pseudo liberties as well as disjoint set chain tracking.  Curiously 
> enough, they're both things I independently came up with when I was 
> designing HouseBot the first time around, but included neither in the 
> open source version.  Pseudo liberties had a very negative response on 
> the computer go mailing list at the time, so I chose something closer to 
> real liberty tracking.  When I implementing undo's I figured the 
> disjoint set stuff was too complex and might scare away developers on an 
> open source project (simple, easy to read code is a big plus).  I still 
> wonder if I was the original creator of either concept...

___
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

[Don Dailey]

On Sun, 2007-05-27 at 19:31 -0400, [EMAIL PROTECTED] wrote:
>  If I had it to do over again, knowing what I know now, I would not spend a 
> 
> lot of time optimizing random games. These optimizations don't make much
> 
> difference for heavy playouts and heavy playouts are better.
>  
> - Dave Hillis 

Yes, I absolutely agree with this.   It's probably best to save the
optimizations for specific versions - when you know what you want.   

With a program in constant development, it's not so easy to decide at
what point this makes sense.


- Don



___
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

[Jason House]

Darren Cook wrote:

Jason House also mentioned "hard coding to a set board size", I think
libego can be used at least up to 19x19, just by changing the
"board_size" setting in board.cpp (it also supports hexagonal boards).
Or did you mean being able to make one binary for all board sizes? I
feel that that flexibility doesn't justify the performance hit.
  


One binary for many board sizes is pretty easy and comes at nearly zero 
runtime cost... Templates could at least allow common cases such as 
running on KGS to work well (19x19, 13x13, 9x9)


template 
class board{
}

or the D equivalent...
class board(int boardsize){
}

___
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

[Darren Cook]

> Jason, can You tell me why You don't want to use libego instead?
> Actually this is open question to all comp-go readers.
> 
> Is libego too complicated? Do You have problems with compilation?
> Or You are not comfortable with the GNU license? Any other reason?

I've been studying and experimenting with libego. I will probably write
my own monte carlo implementation from scratch soon (though I intend to
follow many of your coding decisions). Two big reasons.

First I have a lot of C++ code (for patterns, tactical search, etc.)
that I still want to use. It is incompatible with libego at the low
level (e.g. way of describing board coords).

Second, the GPL virus license. If it was BSD-like I'd give more
consideration to switching to using libego at the low level, and alter
all my other code (because libego is quick, and because of all the usual
open source advantages, which could be summarized as: "it will only get
better"). I'd also be more likely to contribute code. However, I know my
views on BSD vs. GPL are stronger than most people.

Documentation is weak, but it only took me a handful of hours to go
through the code line by line, taking notes, to work out what was going
on. Being on sourceforge would be good. Removing all global variable
references would be good. Use of templates (i.e. policy helper classes)
instead of #defines would be good. None of these would stop me using
libego though.

Jason House also mentioned "hard coding to a set board size", I think
libego can be used at least up to 19x19, just by changing the
"board_size" setting in board.cpp (it also supports hexagonal boards).
Or did you mean being able to make one binary for all board sizes? I
feel that that flexibility doesn't justify the performance hit.

Darren

___
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

[Peter Drake]

I struggled with unto a lot, too. In the current version of Orego,  
there is no undo, just a way to copy a board relatively quickly. This  
falls under "keep the common case fast" again: you only "undo" once  
per playout, so it's faster to make a copy.


(For the "real" board, where actual games moves are played, maintain  
a stack of board state copies for undoing.)


Peter Drake
http://www.lclark.edu/~drake/



On May 27, 2007, at 5:28 PM, Jason House wrote:


Don Dailey wrote:
Lukasz Lew does something far more sophisticated and very fast  
using the

concept of pseudo liberties which you might want to look into.



Both pseudo liberties as well as disjoint set chain tracking.   
Curiously enough, they're both things I independently came up with  
when I was designing HouseBot the first time around, but included  
neither in the open source version.  Pseudo liberties had a very  
negative response on the computer go mailing list at the time, so I  
chose something closer to real liberty tracking.  When I  
implementing undo's I figured the disjoint set stuff was too  
complex and might scare away developers on an open source project  
(simple, easy to read code is a big plus).  I still wonder if I was  
the original creator of either concept...

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


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

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

[Jason House]

Don Dailey wrote:

Lukasz Lew does something far more sophisticated and very fast using the
concept of pseudo liberties which you might want to look into.
  


Both pseudo liberties as well as disjoint set chain tracking.  Curiously 
enough, they're both things I independently came up with when I was 
designing HouseBot the first time around, but included neither in the 
open source version.  Pseudo liberties had a very negative response on 
the computer go mailing list at the time, so I chose something closer to 
real liberty tracking.  When I implementing undo's I figured the 
disjoint set stuff was too complex and might scare away developers on an 
open source project (simple, easy to read code is a big plus).  I still 
wonder if I was the original creator of either concept...

___
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

[Jason House]

?ukasz Lew wrote:

Jason, can You tell me why You don't want to use libego instead?
Actually this is open question to all comp-go readers.

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


I probably have a lot of little reasons. When it first came out, I 
already had my own C++ based framework and didn't really worry about 
switching or not. Of course, now that I'm rewriting my bot, using 
someone else's framework would make more sense. When I look at libego, 
the big turn offs would be the lack of documentation, coding style (the 
use of #defines, global variables, hard coding to a set board size, 
etc...), and lack of a collaborative environment such as sourceforge 
(repository access, bug tracking, etc...).


My rewrite is using a little known language D. Here are some items that 
have been developed in the housebot rewrite that I really like:

* Multi-threaded core routines
* Inter-process communication with delegates (function objects) instead 
of fixed data structures and special handlers (like the MPI uses I've seen)
* Decentralized GTP command registration. I originally used the GTP from 
Gnu Go but didn't like how many places in the code I had to modify when 
adding new (debug) functions.

* Variable board sizes and shapes (currently, rectangular boards).

Instead of just supporting one best implementation, I want to have a 
flexible framework that supports the interests of many programmers. 
Eventually, the core will allow a variety of plug and play 
components/algorithms... I want to support different types of boards 
(such as bit boards and 3D boards), different types of chain tracking 
(such as the disjoint set data structure or gnu style int chain ID), and 
different search methods (UCT, alpha beta, PN, df-PN, etc...).


I'm always recruiting people to help if that inspires anyone ;)
___
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

[dhillismail]

On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote:
>   As I get into the home stretch of rewriting the core of my bot, I want 
> to add a monte carlo player.  I've realized that picking a random move 
> to play is non-trivial since it's such a key element in playout speed.
> 
>   An array of legal positions has easy lookup, but may not be easy to 
> maintain... I guess it'd require storing a mapping between board 
> position and index into the legal positions array so that a move that 
> becomes illegal can be quickly removed (by moving the item from the tail 
> of the array into the empty location).
> 
>   Looking at libego, I see it does a variant on this where it maintains 
> an array of empty points.  If the random index it picks is disallowed, 
> it'll scan through the array (with wrapping around the end) until it 
> either finds an allowed move or returns to its starting point.
> 
>   Which methods have people tried and what works best?
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

 If I had it to do over again, knowing what I know now, I would not spend a 
lot of time optimizing random games. These optimizations don't make much
difference for heavy playouts and heavy playouts are better.
 
- Dave Hillis 
 


























Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam 
and email virus protection.
___
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

[Don Dailey]

I'm a language caveman too then.   I really avoid C++ even though I
learned the basics long ago.   I really hate it. It's not like I'm
an old dog that can't learn new tricks - I have experimented and
explored many computer languages and I am versatile in many.   

It's one of those languages that to me feels wrong - like a big ugly
hack on top of something that isn't that pretty to start with.I
tolerate C because it's the best at speed.  I don't have a good reason
to tolerate C++.  

Don't want to start a language flame war though.   I love object
oriented but I always reach for something else when I'm compelled to go
that way.  Maybe it's caveman of me, but I don't associate object
oriented with super high performance programming.   Of course I realize
that c++ can be almost as fast as C if you know what you are doing and
avoid certain things - but it seems like an insane combination to me -
OOP is high level, C is low level.   C++ seems like a bad marriage.

I'm sure you can get used to anything.  If you get really familiar and
comfortable with C++ you probably can live with it and even believe it
to be a wonderful thing.   But that's no shocker - no matter how awful a
language is you will get many fanatics who seem to believe it's the most
wonderful thing ever invented!

- Don



On Sun, 2007-05-27 at 13:02 -0700, Peter Drake wrote:
> Yeah, I suffer from this, too. (There's also the fact that using
> someone else's code would disqualify you from the formal division of
> the KGS tournaments.)
> 
> 
> Here's a heroic tale of not-invented-here syndrome for your amusement:
> 
> 
> http://worsethanfailure.com/Articles/slammerSCR.aspx
> 
> Peter Drake
> http://www.lclark.edu/~drake/
> 
> 
> 
> 
> 
> On May 27, 2007, at 12:55 PM, steve uurtamo wrote:
> 
> > i'd need to write a C interface for it, then try to maintain
> > compatibility
> > through new releases.  (AKA i'd effectively end up rewriting it).
> > it might
> > seem like less of a burden for me to just write my code in C++, but
> > i guess i'm just a caveman who is stuck in his old ways and would
> > rather
> > reinvent the wheel than switch language horses just to save some
> > effort.
> > 
> > 
> > s.
> > 
> > 
> > - Original Message 
> > From: Łukasz Lew <[EMAIL PROTECTED]>
> > To: computer-go 
> > Sent: Sunday, May 27, 2007 2:39:55 PM
> > Subject: Re: [computer-go] Efficiently selecting a point to play in
> > a random playout
> > 
> > 
> > Hi,
> > 
> > 
> > I've tested many approaches, and the one I implemented is clearly
> > the best.
> > The bias that Peter Drake talks about is negligible and doesn't have
> > a
> > noticeable impact
> > on playout results.
> > (and uniformity of playout isn't something to fight for in MC Go)
> > 
> > 
> > Jason, can You tell me why You don't want to use libego instead?
> > Actually this is open question to all comp-go readers.
> > 
> > 
> > Is libego too complicated? Do You have problems with compilation?
> > Or You are not comfortable with the GNU license? Any other reason?
> > 
> > 
> > Best Regards,
> > Lukasz Lew
> > 
> > 
> > 
> > 
> > On 5/27/07, Jason House <[EMAIL PROTECTED]> wrote:
> > >   As I get into the home stretch of rewriting the core of my bot,
> > > I want
> > > to add a monte carlo player.  I've realized that picking a random
> > > move
> > > to play is non-trivial since it's such a key element in playout
> > > speed.
> > > 
> > > 
> > >   An array of legal positions has easy lookup, but may not be easy
> > > to
> > > maintain... I guess it'd require storing a mapping between board
> > > position and index into the legal positions array so that a move
> > > that
> > > becomes illegal can be quickly removed (by moving the item from
> > > the tail
> > > of the array into the empty location).
> > > 
> > > 
> > >   Looking at libego, I see it does a variant on this where it
> > > maintains
> > > an array of empty points.  If the random index it picks is
> > > disallowed,
> > > it'll scan through the array (with wrapping around the end) until
> > > it
> > > either finds an allowed move or returns to its starting point.
> > > 
> > > 
> > >   Which methods have people tried and what works best?
> > > ___

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

[Don Dailey]

Here is what I do, don't know if it's best 

Basically you want a list of empty points, since most of them are legal.
When I apply a move to the board I then do any needed legality
testing.  

At the beginning I start with a list of ALL points on the board.   When
a non-empty point is encountered I "put it away", placing it behind a
point in the list that represents all the occupied points.   To find a
random move I choose an index at random among the set of untested
points.  If that point is occupied, it gets put away, if it's not it's
the next move (and it still get's put away since it will not be
occupied.)If the point is not occupied but illegal, it gets "set
aside" until a legal move is found - then it is good again.   

When a capture occurs,  I have found nothing much faster than just
starting all over, due to my very simplistic data structure.One
could take the time to restore those points but this is expensive  with
naive data structures.  

It's often not productive to play to points that have been captured -
often a complete waste of time for either side.   There may be some
enhancements where this fact is used to advantage, but I'm not sure how
to reliably test when this should and shouldn't be done.

Lukasz Lew does something far more sophisticated and very fast using the
concept of pseudo liberties which you might want to look into.

- Don




On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote:
>   As I get into the home stretch of rewriting the core of my bot, I want 
> to add a monte carlo player.  I've realized that picking a random move 
> to play is non-trivial since it's such a key element in playout speed.
> 
>   An array of legal positions has easy lookup, but may not be easy to 
> maintain... I guess it'd require storing a mapping between board 
> position and index into the legal positions array so that a move that 
> becomes illegal can be quickly removed (by moving the item from the tail 
> of the array into the empty location).
> 
>   Looking at libego, I see it does a variant on this where it maintains 
> an array of empty points.  If the random index it picks is disallowed, 
> it'll scan through the array (with wrapping around the end) until it 
> either finds an allowed move or returns to its starting point.
> 
>   Which methods have people tried and what works best?
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

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

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

[Peter Drake]

Yeah, I suffer from this, too. (There's also the fact that using  
someone else's code would disqualify you from the formal division of  
the KGS tournaments.)


Here's a heroic tale of not-invented-here syndrome for your amusement:

http://worsethanfailure.com/Articles/slammerSCR.aspx

Peter Drake
http://www.lclark.edu/~drake/



On May 27, 2007, at 12:55 PM, steve uurtamo wrote:

i'd need to write a C interface for it, then try to maintain  
compatibility
through new releases.  (AKA i'd effectively end up rewriting it).   
it might

seem like less of a burden for me to just write my code in C++, but
i guess i'm just a caveman who is stuck in his old ways and would  
rather
reinvent the wheel than switch language horses just to save some  
effort.


s.

- Original Message 
From: Łukasz Lew <[EMAIL PROTECTED]>
To: computer-go 
Sent: Sunday, May 27, 2007 2:39:55 PM
Subject: Re: [computer-go] Efficiently selecting a point to play in  
a random playout


Hi,

I've tested many approaches, and the one I implemented is clearly  
the best.

The bias that Peter Drake talks about is negligible and doesn't have a
noticeable impact
on playout results.
(and uniformity of playout isn't something to fight for in MC Go)

Jason, can You tell me why You don't want to use libego instead?
Actually this is open question to all comp-go readers.

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

Best Regards,
Lukasz Lew


On 5/27/07, Jason House <[EMAIL PROTECTED]> wrote:
  As I get into the home stretch of rewriting the core of my bot,  
I want
to add a monte carlo player.  I've realized that picking a random  
move
to play is non-trivial since it's such a key element in playout  
speed.


  An array of legal positions has easy lookup, but may not be easy to
maintain... I guess it'd require storing a mapping between board
position and index into the legal positions array so that a move that
becomes illegal can be quickly removed (by moving the item from  
the tail

of the array into the empty location).

  Looking at libego, I see it does a variant on this where it  
maintains
an array of empty points.  If the random index it picks is  
disallowed,

it'll scan through the array (with wrapping around the end) until it
either finds an allowed move or returns to its starting point.

  Which methods have people tried and what works best?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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






__ 
__Yahoo! oneSearch: Finally, mobile search

that gives answers, not web links.
http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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

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

[steve uurtamo]

i'd need to write a C interface for it, then try to maintain compatibility
through new releases.  (AKA i'd effectively end up rewriting it).  it might
seem like less of a burden for me to just write my code in C++, but
i guess i'm just a caveman who is stuck in his old ways and would rather
reinvent the wheel than switch language horses just to save some effort.

s.

- Original Message 
From: Łukasz Lew <[EMAIL PROTECTED]>
To: computer-go 
Sent: Sunday, May 27, 2007 2:39:55 PM
Subject: Re: [computer-go] Efficiently selecting a point to play in a random 
playout

Hi,

I've tested many approaches, and the one I implemented is clearly the best.
The bias that Peter Drake talks about is negligible and doesn't have a
noticeable impact
on playout results.
(and uniformity of playout isn't something to fight for in MC Go)

Jason, can You tell me why You don't want to use libego instead?
Actually this is open question to all comp-go readers.

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

Best Regards,
Lukasz Lew


On 5/27/07, Jason House <[EMAIL PROTECTED]> wrote:
>   As I get into the home stretch of rewriting the core of my bot, I want
> to add a monte carlo player.  I've realized that picking a random move
> to play is non-trivial since it's such a key element in playout speed.
>
>   An array of legal positions has easy lookup, but may not be easy to
> maintain... I guess it'd require storing a mapping between board
> position and index into the legal positions array so that a move that
> becomes illegal can be quickly removed (by moving the item from the tail
> of the array into the empty location).
>
>   Looking at libego, I see it does a variant on this where it maintains
> an array of empty points.  If the random index it picks is disallowed,
> it'll scan through the array (with wrapping around the end) until it
> either finds an allowed move or returns to its starting point.
>
>   Which methods have people tried and what works best?
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/





   
Yahoo!
 oneSearch: Finally, mobile search 
that gives answers, not web links. 
http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC
___
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

[Łukasz Lew]

Hi,

I've tested many approaches, and the one I implemented is clearly the best.
The bias that Peter Drake talks about is negligible and doesn't have a
noticeable impact
on playout results.
(and uniformity of playout isn't something to fight for in MC Go)

Jason, can You tell me why You don't want to use libego instead?
Actually this is open question to all comp-go readers.

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

Best Regards,
Lukasz Lew


On 5/27/07, Jason House <[EMAIL PROTECTED]> wrote:

  As I get into the home stretch of rewriting the core of my bot, I want
to add a monte carlo player.  I've realized that picking a random move
to play is non-trivial since it's such a key element in playout speed.

  An array of legal positions has easy lookup, but may not be easy to
maintain... I guess it'd require storing a mapping between board
position and index into the legal positions array so that a move that
becomes illegal can be quickly removed (by moving the item from the tail
of the array into the empty location).

  Looking at libego, I see it does a variant on this where it maintains
an array of empty points.  If the random index it picks is disallowed,
it'll scan through the array (with wrapping around the end) until it
either finds an allowed move or returns to its starting point.

  Which methods have people tried and what works best?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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

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

[Peter Drake]

I've spent a lot of time struggling with this; it can have a huge  
impact on performance. The key thing to remember is to keep the  
common case fast.


Orego currently maintains a list (technically a stretchable array,  
analogous to the java.util.ArrayList class) of vacant points. I  
shuffle this list at the beginning of every playout. When it's time  
to choose a move, I work through this list until I find a legal move.  
Since vacant points are almost always legal, this usually produces a  
legal move very quickly.


I believe it's not worth maintaining a set of legal moves; when  
you're choosing a move randomly, you're not going to consider most of  
them, so any time spent checking their legality would be wasted.  
Maintaining a set of vacant points, on the other hand, is worthwhile,  
as it allows you to completely skip over verifying that the occupied  
points are illegal.


If your description of libego is accurate, it introduces a bias. If  
point X is vacant but illegal (say, it's inside an enemy eye), the  
next vacant point is twice as likely to be selected as some vacant  
point that doesn't follow an illegal one. I proposed an elaborate way  
to get around this bias here:


https://webdisk.lclark.edu/xythoswfs/webui/_xy-2352013_1-t_Gct7yJ5s%22

but I now believe that shuffling a list of vacant points is faster.

Peter Drake
http://www.lclark.edu/~drake/



On May 27, 2007, at 10:21 AM, Jason House wrote:

 As I get into the home stretch of rewriting the core of my bot, I  
want to add a monte carlo player.  I've realized that picking a  
random move to play is non-trivial since it's such a key element in  
playout speed.


 An array of legal positions has easy lookup, but may not be easy  
to maintain... I guess it'd require storing a mapping between board  
position and index into the legal positions array so that a move  
that becomes illegal can be quickly removed (by moving the item  
from the tail of the array into the empty location).


 Looking at libego, I see it does a variant on this where it  
maintains an array of empty points.  If the random index it picks  
is disallowed, it'll scan through the array (with wrapping around  
the end) until it either finds an allowed move or returns to its  
starting point.


 Which methods have people tried and what works best?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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