Re: [computer-go] UCT outside of go?
On 04/06/07, Darren Cook [EMAIL PROTECTED] wrote: Does anyone know of UCT being used in games other than go, or outside games altogether, such as travelling salesman problem, or some business-related scheduling/optimizing/searching problem domain? I am trying to use UCT for the game trax. I will post my results in a few months from now. ( http://traxgame.info/ ) Regards Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT outside of go?
Darren Cook wrote: Does anyone know of UCT being used in games other than go, or outside games altogether, such as travelling salesman problem, or some business-related scheduling/optimizing/searching problem domain? I have used it in a connect4 engine. http://www.roland-illig.de/viergewinnt.html http://www.roland-illig.de/download/connect4-1.1.jar The applet is currently using a simple monte carlo engine, but it's very easy to replace it with the UCT engine (Applet.java, line 37). The results of a simple tournament are these: first playersecond player wins losses draws - KnowledgeEngine KnowledgeEngine 1000 0 0 KnowledgeEngine UCTEngine(1000) 56640034 UCTEngine(1000) KnowledgeEngine 212779 9 UCTEngine(1000) UCTEngine(1000) 51843745 I didn't run a tournament between MC and UCT. Roland ___ 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
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
Á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] UCT outside of go?
In case anyone else was interested, yes, the AAAI general game-playing competition has just started. You can find instructions to join the mailing list on the resources page at the site (games.stanford.edu) and evidently the games from the competition are being broadcast live online. If it's run like last year's competition (which I strongly suspect it is), then there are several preliminary rounds before the on-site final, with later rounds weighted more heavily so as not to punish machines that are still learning in the early rounds when they first face strong competition, so you could in fact join late with little penalty. (The tournament director stated this last point in his response to me.) It's an interesting field, and I do recommend that people check it out if they're curious. It helps push games back towards the realm of big AI for a while. (Measurable goals tend to fall eventually. ;) Neat stuff. -Nick On 6/3/07, Peter Drake [EMAIL PROTECTED] wrote: I don't know, but I'd like to try it on the AAAI's general game-playing competition. Does anyone know if it's still running? The only site I could find gives a past date as Real Soon Now: http://games.stanford.edu/competition.html I didn't get any reply from the address listed. Does anyone else know anything? Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ On Jun 3, 2007, at 5:13 PM, Darren Cook wrote: Does anyone know of UCT being used in games other than go, or outside games altogether, such as travelling salesman problem, or some business-related scheduling/optimizing/searching problem domain? Thanks, Darren -- Darren Cook http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary) http://dcook.org/work/ (About me and my work) http://dcook.org/work/charts/ (My flash charting demos) ___ 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
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
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 wrote:
On 6/6/07, *Rémi Coulom* [EMAIL PROTECTED]
mailto:[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
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
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/
