124. Chew (3k) vs Fuego (Bot)

emeraldemon · Post by **emeraldemon** » Fri Jun 03, 2011 1:14 pm

I will be operating Fuego, a go-playing program, in a long time game vs. Chew. Fuego only understands area scoring (or AGA) if that's ok with you. Do you have any explicit requirements for how much time I give the program? I was doing some tests where I gave it 20 minutes per move, and it usually moved in 8 or 10, so it may not matter after a certain point.

I have a number in a hide tag, guess odd or even:

Enjoy the game!

Click Here To Show Diagram Code: [go]$$Bcm1 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Website · Post by **Chew Terr** » Fri Jun 03, 2011 1:39 pm

I guessed odd. Thanks for the game. I've never really played bots much, so this may be an interesting experiment.

Oh, I trust you to pick whatever time limits you rcommend.

Mike Novack · Post by **Mike Novack** » Fri Jun 03, 2011 2:50 pm

A "bot" is a program running on some hardware.

In this case with so much real time allowed per move the hardware should be irrelevant (I think with this much real time most of the MCTS programs would pass the point of diminishing returns even on very modest hardware).

But that assumes the program used automatically adjusts based on its determination of the power of the machine it finds itself running on and the average amount of time per move. Do we know that feugo does that?

Also in a case like this we should be more specific about the program version. Otherwise we might end up drawing a false conclusion from the result (mistakenly saying "feugo appears to have strength X" rather than "feugo yy.zzz appears to have strength X"). For most of these programs a version just a couple years old might be much weaker than a curerent version.

emeraldemon · Post by **emeraldemon** » Fri Jun 03, 2011 3:35 pm

Fuego has an opening book, so there's no thinking yet

Click Here To Show Diagram Code: [go]$$Bcm1 $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . B . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Some stuff about Fuego:

I'm using Fuego 1.1, the most recent version, It uses an algorithm called UCT (upper-confidence trees), which is a type of monte-carlo search. Basically, the core of Fuego's thinking is to play hundreds and millions of games with a very basic strategy, only a bit better than random. The playouts themselves are bad, but over the huge number of games it realizes that controlling certain points tends be good. It builds a tree similar to the reading we're used to, using the pseudo-random playouts to evaluate the end position.

To Mike's point: there's definitely going to be diminishing returns, I honestly doubt 20 min/move will produce better play than 10 min/move. But then, you could say the same thing about human play

The algorithm just does playouts until time is up, it doesn't really change its strategy for fast vs slow games or anything like that.

I can try to explain in more detail if anyone is curious, and maybe it'll be more clear once the game gets underway.

Post by **Joaz Banbeck** » Fri Jun 03, 2011 11:48 pm

I really like this thread.
:clap:

EdLee · Post by **EdLee** » Sat Jun 04, 2011 12:41 am

emeraldemon, thank you. Do you happen to know how Fuego decided on Q4?
(1. as opposed to other corner moves like 3-4, 3-3, 3-5, etc.;
and 2. as opposed to Q16). Thanks.

Loons · Post by **Loons** » Sat Jun 04, 2011 2:48 am

I have a question about "UCT". Is it related to some of the maths people use for phylogenetic analysis ? Or is my moment of wild speculation wrong. (I am bad at maths, so I want an analogy.)

flOvermind · Post by **flOvermind** » Sat Jun 04, 2011 3:13 am

I have no idea what "phylogenetic analysis" is

UCT is basically a tree search, just like Alpha-Beta. But instead of trying to find an exact value for each branch, it is assumed that the value of each branch is random variable with certain expected value. The value of the branch can be sampled by just making a random playout. Each node in the tree is then treated as a multi-armed bandit problem, in order to find the move with the highest expected value. Popular nodes are expanded (i.e., treated as recursive bandits), leaf nodes are random playouts. This whole thing is done iteratively until time runs out.

From this algorithm description, it should be clear that the computer does in no way need to "automatically adjusts based on its determination of the power of the machine it finds itself running on and the average amount of time per move". It will automatically get stronger when you give it more hardware and/or time. But I expect diminishing returns beyond a certain point

I really look forward to watching this game. I'm really curious how well UCT really scales when given that much time. I expect low dan strength, but that's just a wild guess

hyperpape · Post by **hyperpape** » Sat Jun 04, 2011 1:14 pm

Mike Novack wrote:A "bot" is a program running on some hardware.

In this case with so much real time allowed per move the hardware should be irrelevant (I think with this much real time most of the MCTS programs would pass the point of diminishing returns even on very modest hardware).

could you elaborate on this point? I had thought that one of the big advantages of Monte Carlo methods is that they make good use of increased computational power, in a way that older programs didn't.

What does your comment mean about the path forward for bots that employ MC?

Mike Novack · Post by **Mike Novack** » Sat Jun 04, 2011 2:12 pm

hyperpape wrote:
Mike Novack wrote:A "bot" is a program running on some hardware.

In this case with so much real time allowed per move the hardware should be irrelevant (I think with this much real time most of the MCTS programs would pass the point of diminishing returns even on very modest hardware).
could you elaborate on this point? I had thought that one of the big advantages of Monte Carlo methods is that they make good use of increased computational power, in a way that older programs didn't.

What does your comment mean about the path forward for bots that employ MC?

This isn't really my "line of country" but I'll try to explain where the rapidly diminshing returns comes from. It's all about probablility and how large a smaple size we need to draw a conclusion from statistics.

Let's simplify the question. The basis behind the so called Monte Carlo go playing algorithms is the assumption that if from position A player 1 wins a higher percentage of games against equal player 2 than from positon B then evaluate A as better for player 1 than position B. Here the players are both terrible, both play randomly, but that is equal.

Pretend we had a loaded coin, either heads or tails is somewhat heavier. How can we tell which? Well suppose we flip the coin once and it comes up heads. Does that make us very certain that the coin is head heavy? Now suppose we flip it 10 times and it comes up 6 heads and 4 tails. Does that make it very certain? Now suppose we flip it 100 times and it comes up 60 heads and 40 tails. Better; but I wouldn't want to risk my life on a bet that the coin wasn't an honest coin (60/40 out of a hunderd tosses isn't that unlikely for an honest coin). Now consider 1000 tosses coming out 600 to 400 or 10,000 tosses coming out 6000 to 4000.

In other words, as the sample size goes up our confidence that the (true) ratio is 6/4 increses. First that confidence increases very rapidly (when the sample size is small) but then begins increasing slower and slower.

Does this mean I don't think there will be further improvements? Like I said, not my line of country (I am a retired systems analyst, but my expertise is in financial software, not AI). There is a great deal more that some of these programs are doing than a naive application of "try this with all possible moves". I would expect advances to be coming from those "other things" (some clever pruning trick to focus tree growth down the most promising paths; a better AI generating the "plausible move set" for ones that do this rather than "try every move"; etc.)

emeraldemon · Post by **emeraldemon** » Sat Jun 04, 2011 4:24 pm

EdLee wrote:emeraldemon, thank you. Do you happen to know how Fuego decided on Q4?
(1. as opposed to other corner moves like 3-4, 3-3, 3-5, etc.;
and 2. as opposed to Q16). Thanks.

Well, Fuego just has a big book of openings, that looks something like this:

Code: Select all

19 Q4 C17 | Q17
19 Q4 C17 Q17 | D3
19 Q4 C17 R16 | D3
19 Q4 C17 R16 D3 | P17
19 Q4 C17 Q16 | D3
19 Q4 C17 Q16 D3 | D5
19 Q4 C16 | Q16

This says "if I play Q4 and the opponent plays C17, I play Q17. If the sequence was Q4 C17 Q17, I play D3" and so on. As long as the game sequence is in that book somewhere, it doesn't think at all, just plays what is suggested. Of course, I think your real question is "how did the people who built Fuego choose these moves?" And I have to say I don't know

I think maybe they're drawn from a database of games, but I don't know the details.

Mike Novack · Post by **Mike Novack** » Sat Jun 04, 2011 5:45 pm

I'm not familiar with feugo and I don't cheat (disassemble the code). However inferences can be drawn from a program's behavior and an experieinced program designer can usually think of several ways that behavior could be implemented.

The behavior I would expect (of a good go playing program) would be that in spite of the book, not always make the same move. That's prety easy with a random number (pseudorandom) generator. Could even mimic what could be expected from humans if the "book" contained "frequency with which this next move made" and I know some databases contain that. In other words, as long as still in a book sequence select the next move according to the frequency that move is made.

Earlier was asked why it began corner star point? That can be the same method (book has frequencies for the choice of first move).

emeraldemon · Post by **emeraldemon** » Sat Jun 04, 2011 6:02 pm

Mike Novack wrote:I'm not familiar with feugo and I don't cheat (disassemble the code). However inferences can be drawn from a program's behavior and an experieinced program designer can usually think of several ways that behavior could be implemented.

The behavior I would expect (of a good go playing program) would be that in spite of the book, not always make the same move. That's prety easy with a random number (pseudorandom) generator. Could even mimic what could be expected from humans if the "book" contained "frequency with which this next move made" and I know some databases contain that. In other words, as long as still in a book sequence select the next move according to the frequency that move is made.

Earlier was asked why it began corner star point? That can be the same method (book has frequencies for the choice of first move).

It's not necessary to disassemble, the project is open source ;-)

http://fuego.sourceforge.net/

The text I copied/pasted is from a file in the project called book.dat, I could hunt down the place where it's used to see exactly the setup, but I can see just from watching that there's no randomness in its opening. When you ask it to play itself it does the same fuseki every time. Moves after it exits the book vary, due to randomness in the search.

Mike Novack · Post by **Mike Novack** » Sun Jun 05, 2011 4:39 am

emeraldemon wrote:...... but I can see just from watching that there's no randomness in its opening. When you ask it to play itself it does the same fuseki every time. Moves after it exits the book vary, due to randomness in the search.

Well were I working on this project that's one of the first things I'd want to "fix". A good program would not play the same fuseki every time (there's no agreement among top human players about a "best"). And that represents a serious defect for anybody wanting to use the program as "learning tool".

To be fair, these all volunteer projects suffer from a lack of resources which is why we find them usually waiting for things to be done until somebody who wants to fix this or that problem steps forward (they can't assign resources). The non professionals among us have little idea of the value "X amount of analyst/programmer time" is worth on the market; what volunteers are being asked to donate. Most of the people qualified to do this work are also doing it for pay (their "day jobs"). So we have to accept that "free" programs will lag except perhaps for any "academic" projects (where the time may be coming from students working for course credit).

xed_over · Post by **xed_over** » Sun Jun 05, 2011 2:21 pm

I was curious to see how GnuGo (version 3.6) would have played it...

Click Here To Show Diagram Code: [go]$$Bcm1 GNU Go plays Q16 (a=75.00) - Game move Q4 (b=74.00) $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . b b b . . . . . . . . . b b b . . | $$ | . . b b b . . . . , . . . . b a b . . | $$ | . . b b . . . . . . . . . . . b b . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . b . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . b b . . . . . . . . . . . b b . . | $$ | . . b b b . . . . , . . . . b B b . . | $$ | . . b b b . . . . . . . . . b b b . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

Life In 19x19

124. Chew (3k) vs Fuego (Bot)

124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re:

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)

Re: 124. Chew (3k) vs Fuego (Bot)