On Mon, 2008-08-11 at 15:21 -0400, Robert Waite wrote:
> > You don't need to know the whole tree, you only need to know some of the
> > tree and it's a very small fraction of the whole. That's what
> > alpha/beta pruning is all about.
>
> Certainly we are seeing gains by looking at smaller portions of the
> tree. Perfect play and the question of God however seem akin to
> generating the entire tree.
You clearly don't understand the principles of alpha/beta pruning. It
is an "admissible" technique which means it guarantee's the same result
as searching the entire tree, but only requires a very tiny subset of
the entire tree.
Let's say you have 381 possible first moves and you find that the first
one you look at wins the game by 6.5 points. So you know that no
matter what happens with the next 380 moves you can always "fall back"
on the one that wins by 6.5. You of course hope that you will find a
move that does BETTER so you are forced to search all 381 moves.
So you start looking at the 2nd move. Just for fun let's say you look
at A1 and your opponent, after looking at only 1 move to the end of the
game sees that he can beat you. You already KNOW that you can do better
and that you should not play A1. It does not matter if the opponent
finds an even better refutation or not, it's enough to know that even
if he doesn't try, he is going to beat you with his first choice - and
you have already discovered that you can win.
It is explained pretty well here:
http://en.wikipedia.org/wiki/Alpha-beta_pruning
Here is a quote:
Alpha-beta pruning is a sound optimization in that it does not
change the result of the algorithm it optimizes.
- Don
> Since we are using statistics to decide which parts of the tree are
> interesting or good... we are still missing other potential playouts.
> Judging by the number of samples vs. the number of possible games, we
> are missing many possible moves, some good, some bad. I guess it all
> depends on your definition of God... but my mental image would be that
> he knows all paths of the game.. and thus would not be tricked when we
> are only looking at a subset of the tree. Same goes for perfect move.
> We can never judge accurately if we found the perfect move unless we
> know what all possible moves are. We can only guess with a certain
> amount of confidence.
>
> However... humans are not anything like God and are missing huge
> portions of the tree as well. Generating a better move than a human is
> in no way related to the need to generate the entire tree. I do agree
> that it is very much possible that this technique alone could scale to
> the point of crushing a person. I just don't know yet if we can
> accurately guess that. People are rather flexible in the way they play
> and learn and it is still very trickly to evaluate a goban.
>
> I am not completely familiar with Mogo's inner workings.. but it does
> have a base heuristic that helps it judge where to start looking. If
> it doesn't find a certain group of moves.. it goes to random spots. It
> seems that adding this heuristic stage helped CrazyStone and Mogo
> greatly.
>
> I am totally on your side with beating human players. It is obvious
> that it will happen one day. I am just very curious of the number
> crunch vs. heuristics vs. a whole new paradigm debate. MC is kind of a
> new paradigm for number crunching (at least in go).. and it is great.
> I am just curious if new barriers will be hit. And I am happy either
> way... if MC does not turn out to be the panacea of computer go...
> then new methods will be combined with it or whole new methods will
> come out.
>
> A number of barriers have already been hit.. computer go seemed stuck
> around 12-8k for a while.. and it was a bit worse before right? I am
> not trying to crush anyone's dreams.. I am just curious if this
> breakthrough has really removed all of the barriers to number
> crunching or if it has just helped us push up to the next level, one
> where we will once again have to work on heuristics or go back to the
> drawing board. I wish we could rely on hardware scaling.. but I am not
> so sure that it is the answer yet. That is a hunch.. but so are many
> claims I have seen. I can't turn my hunch into a theory until I have
> more data. I haven't seen a source of data that convinces me we are
> home free yet. When we start putting these machines against seasoned
> pros... and watch what happens when you scale... I think we will have
> a much better answer.
>
> And to Don, I think we had plenty of misunderstandings and
> miscommunications... I know you aren't saying we are home free and you
> have put a lot more work in it than I have. When you said "proven to
> be scalable to perfect play" you probably meant it in a different
> sense than I read it and many people on here might have understood
> what you were trying to point out. I'm not trying to spray your parade
> with yellow rain... I just feel that there are still many unknowns.
>
> On Mon, Aug 11, 2008 at 12:23 PM, Robert Waite
> <[EMAIL PROTECTED]> wrote:
> > Yes, but "exhausitve search" does not improve your player by 63%
> (eg.)
> > for a doubling in CPU time.
> > This part was done in an empirical scalability study. Please check
> the
>
>
> > archives of the list.
>
> > In the (inifinite) limit minimax+evaluation-function would find the
>
> > perfect move
> > too, but UCT/MC already find "good" moves before the limit.
> Yes... I agree... UCT/MC seems to find the good moves before
> the limit and from statistics.. seems that the good moves come
> out long before we have exhaustively searched the tree. I was
> questioning the rate at which we approach "perfect play". This
> term seems silly to me... as it would imply actually solving
> the game. The whole idea of playing vs. god and drawing or
> winning only means one thing to me... and that would be
> actually knowing every possible path to determine the best
> path. The results of the MC statistics simply say that this
> move appears to be better given the sample size. To me.. I
> don't think anyone could say that you could beat god without
> actually knowing the whole tree. That would be conjecture at
> least at this point. And having God in the equation already
> moves us to mysticism (or some sort of statement that the game
> has a solution).
>
> As far as the 63% gain... I feel that there are certain
> additional descriptors needed there. We did not see a
> statistical increase in ability vs. human players. We saw a
> 63% gain when putting programs against programs. This is
> hardly the same problem. It is valuable information and I am
> not discounting it at all. I just feel that this evidence DNE
> what it seemed to be used for in previous discussions.
>
> > ...Why are you trying to share it with us in the first place.
> > For myself, i believe that what you are trying to do, is to
> > begin to analyses all the data the community has gathered so far...
>
> Well.. things certainly got heated and as I looked at the
> list.. I started feeling guilty that I kind of took over. The
> list seems primarily used for coordination between you guys
> and perhaps at times theoretical discussion. I apologize for
> the rants that have perhaps shown up suddenly.
>
> The background reason I came in here was that I love go and
> have loved it ever since I learned to play about 5 years ago.
> I am also a developer and long ago had read many articles on
> computer go. At the time.. and perhaps up to now.. there have
> been many go players, computer scientists and lay people who
> have worried that perhaps the greatest strength of the
> computer, fast computation, would not be such a great help
> with playing go. There were taunts from this side saying that
> computers couldn't really beat children who were decent. After
> reading and hearing these sorts of discussions... I started to
> fall into that group. My personal feeling was that AI now is
> akin to a human taking a lot of time trying to create a
> particular algorithm. Then this algorithm would work in a
> particular scenario. This seems difficult for go as each of
> these heuristics are focused and meanwhile, you have a human
> who is constantly changing his heuristics during their years
> of learning.
>
> I feel that to have what movies consider "AI" or what the
> general public expects from "AI", we will need a new paradigm
> where computers learn to solve problems by themselves through
> experimentation and learning. This does not necessarily apply
> to go, but is possible.
>
> The reason I brought up complexity theory is not to confine
> computer go to a particular complexity class... but to discuss
> the fact that our current model of computing machines do
> appear to solve many important problems.. but that there some
> classes of problems that we are not so certain can be solved
> with the computer model we all have at our desks or in our
> datacenters.
>
> When I read the article by the DeepBlue guy called "Cracking
> Go", I was very skeptical. I felt that he was assuming too
> much. When I read that Mogo was going to get a nice big
> cluster.. I was very excited and couldn't wait to watch the
> game. When Mogo started to turn around... I had completely
> swtiched from skeptic to cheering it on. I think the Mogo team
> and many people on here have done a great job.
>
> So then I jumped into conversation here and perhaps had not
> fully researched previous topics and breakthroughs... but I
> felt that I was cut down pretty quickly with the phrase
> "proven to be scalable to perfect play". The phrase itself was
> used to completely nullify my argument. That is perhaps where
> it started to get out of hand. Don's "Duck" does not really
> seem to be clearly a duck. In his analogy... his duck is
> almost an axiom and I am some crazy freak who thinks the world
> is flat. I felt it was a bit condescending and did feel I had
> to try to clear the logic up.
>
> At this point.. I have read the Bandit paper and am pretty
> sure where he got this phrase. In the paper it is phrased
> differently. I am probably at fault here because I have just
> jumped in here and have not been a part of much previous
> discourse. Perhaps that phrase has a different meaning here
> and people would assume what he meant. When I saw that
> phrase... the first thing I thought was that they surely meant
> practical. Afterall... what use is something that takes more
> memory that we have in the universe and more time than the age
> of the universe. Obviously we are hoping that it gets
> somewhere good well before that... but the phrasing in the
> original paper did not seem to use this phrase to show why it
> is practical.
>
> I looked at the empirical evidence (at least what I think is
> being referred to).. and to me it does not overwhelmingly show
> that this can be practically scaled to beat humans. I just
> don't see the duck... and I don't think that is from having a
> weak intellect or flawed logic. It seems that they are
> datapoints that are valuable in computer go... but they are
> datapoints that I feel do not prove or even begin to prove how
> Mogo will scale against humans. I don't think that the
> experiment in this case has covered the model.
>
> My reasons to start discussing things on here was that I was
> curious about the future of computer go. As a few discussions
> got heated.. I felt that some weak logic was being thrown at
> me so I probably got a little heated and started firing back.
> I will try to keep such discussions out of the list.
>
> I have however enjoyed reading many people's responses and
> from all of this... I have started getting much deeper into
> complexity theory... from my schooling.. we only knew about
> big O notation and how to apply it to our code.
>
>
>
>
>
>
>
>
> _______________________________________________
> 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/
