It is currently Fri Nov 17, 2017 9:24 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 153 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6 ... 8  Next
Author Message
Offline
 Post subject: Re: Commonsense Go
Post #41 Posted: Sun Feb 05, 2017 6:23 pm 
Dies in gote

Posts: 52
Liked others: 34
Was liked: 8
djhbrown wrote:
Let A = Alphago and B = CG and K = Myungwan Kim.
Let p = the position after move 78 in game 4 of Lee Sedol vs Alphago
Then A(p) = 79: K10, .. (DeepMind have never told us what followup move tree Alphago had expected)
, and B(p) = 79: J13, L12; 80: L10, .. (see https://papers.ssrn.com/sol3/papers.cfm ... id=2818149)
, and K(p) = 79: L10, etc (see sgf)


How is CG coming up with J13 in this particular case, can you please explain in some detail to understand how the various hierarchical systems make a decision among the 290+ legal moves in this position?

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #42 Posted: Mon Feb 06, 2017 2:13 am 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
sorin wrote:
How is CG coming up with J13 in this particular case, can you please explain in some detail to understand how the various hierarchical systems make a decision among the 290+ legal moves in this position?

detailed explanations of how CG chose J13 are provided in my paper
https://papers.ssrn.com/sol3/papers.cfm ... id=2818149
and my video
https://www.youtube.com/watch?v=Nns7004 ... a3Hl1X_v-S

your question seems to contain an implicit assumption, namely that CG decides between all the legal moves. It doesn't work that way (neither do any other bots, including Alphago).

CG looks at what it thinks is the big picture, computing clusters, groups, territory and influence, from which it figures out what it thinks is happening, and then decides what strategy to adopt. this becomes its goal, which its planning methods try to achieve, in so doing creating a tree of subgoals and so on down to the level of moves. for each of the move candidates it comes up with, it looks to see what it thinks the opp would play in reply and whether it thinks that would refute any of its goals. and then it looks to see whether it thinks it can refute that refutation by its next move and so on.

Note particularly that CG found a justification for J13, namely that it thought white would reply at L12 and then black could play the key killing move of L10 on its next turn. i had simulated CG by hand, and didn't go into other variations CG might have considered (there wouldn't be many).

how deep and how wide CG's highly selective search continues depends on how much time it has to make a move (i haven't described algorithms for that; my intuition is that it may be necessary to include Monte-Carlo search as well, since one cannot expect to be able to confidently predict an opponent's moves).

in general, CG is a software (design) embodiment of a decision-making methodology called "satisficing" that one of my heroes, Nobel laureate Herbert Simon, described. Whether or not you are interested in AI or economics or cognitive or behavioural psychology, i strongly recommend googling Simon as his theories are jolly useful and practical insights into how people go about making decisions, whether or not they are aware of what they're doing - and even if they think they're doing something different, like optimisation!

in 1975 i think it was, i had the great pleasure of chatting with Simon about my own work; he used to spend most of his time telecommuting to Carnegie-Mellon University from home but came in to meet me in his office. i thought telecommuting was a terrific idea and there and then it became my life's ambition to find a job i could telecommute to whilst living in a place of my own choosing (like Raivavae, because from the nautical chart it looked to have a perfect cyclone shelter at just the right latitude for getting the best food crop growing climate on Earth).

I never did find such a job, but i did visit Raivavae, although once there, i was persuaded by a Polynesian lady to stay on her island - Tupuai - a perfect example of satisficing in real life :)

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #43 Posted: Sun Feb 19, 2017 12:24 pm 
Dies in gote

Posts: 52
Liked others: 34
Was liked: 8
djhbrown wrote:
CG looks at what it thinks is the big picture, computing clusters, groups, territory and influence, from which it figures out what it thinks is happening, and then decides what strategy to adopt. this becomes its goal, which its planning methods try to achieve, in so doing creating a tree of subgoals and so on down to the level of moves. for each of the move candidates it comes up with, it looks to see what it thinks the opp would play in reply and whether it thinks that would refute any of its goals. and then it looks to see whether it thinks it can refute that refutation by its next move and so on.


I am not sure how is this different from the traditional rule-based systems that have been tried for tens of years in computer-go and led nowhere near a strong player.

djhbrown wrote:
Note particularly that CG found a justification for J13, namely that it thought white would reply at L12 and then black could play the key killing move of L10 on its next turn. i had simulated CG by hand, and didn't go into other variations CG might have considered (there wouldn't be many).


If you devise a system that would narrow down the candidate moves in such a complex situation like the one in this game, to very few candidate moves including the ones that AlphaGo missed, you already have a winner. That sounds too good to be true though - can you please explain in some detail how do you ensure you are selecting just a few good candidates for very deep analysis (which is required given the complexity of this position)?

_________________
Sorin - 361points.com

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #44 Posted: Mon Feb 20, 2017 5:15 am 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
sorin wrote:
how is this different from the traditional rule-based systems?


CG-SWIM does hierarchical (top-down) planning. rule-based programs like ManyFaces don't.

sorin wrote:
how do you ensure you are selecting just a few good candidates?


hierarchical planning naturally leads to relatively few move candidates, as the example in my paper shows. You can try it for yourself on a game position of your choice - just follow the algorithms and methods, creating hand-written goal trees like the ones in my paper, and you will see that very few move candidates are generated.

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2818149

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #45 Posted: Mon Feb 20, 2017 11:21 am 
Dies in gote

Posts: 52
Liked others: 34
Was liked: 8
djhbrown wrote:
sorin wrote:
how do you ensure you are selecting just a few good candidates?


hierarchical planning naturally leads to relatively few move candidates, as the example in my paper shows. You can try it for yourself on a game position of your choice - just follow the algorithms and methods, creating hand-written goal trees like the ones in my paper, and you will see that very few move candidates are generated.
http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2818149


The key part of my question was not just "few candidates", but "few and good candidates". There are three components to AlphaGo's success:
1) Generating few good candidates for next step analysis.
2) Reading ahead (MCTS)
3) Estimating who is winning in a certain situation (to avoid having to simulate too many games till the end).

Number 2 is relatively well understood, I am not concerned about it.
I am not sure how you deal with #1 and #3 above.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #46 Posted: Mon Feb 20, 2017 7:28 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
sorin wrote:
I am not sure how you deal with #1 and #3 above.

in order to figure out how to answer your questions in a way that will make sense, please first tell me a bit about what you already know:
1. have you studied AI at university?
2. have you written a computer program?
3. have you read my paper?
you can download my paper for free from: http://papers.ssrn.com/sol3/papers.cfm? ... id=2818149
it is 120 pages long, but the pages are small and the writing is big, so it only takes about half an hour to read it or to watch my movie of it:
https://www.youtube.com/watch?v=Nns7004 ... a3Hl1X_v-S

Your answers will help me figure out what i can say that will be meaningful. For example, if you answer yes to all of them, i can start off with:
re your #3, see pp 34-41 of my paper
re your #1, see for example pp 26-27, 102-103 and 112-113

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #47 Posted: Mon Feb 20, 2017 9:11 pm 
Dies in gote

Posts: 52
Liked others: 34
Was liked: 8
djhbrown wrote:
sorin wrote:
I am not sure how you deal with #1 and #3 above.

in order to figure out how to answer your questions in a way that will make sense, please first tell me a bit about what you already know:
1. have you studied AI at university?
2. have you written a computer program?
3. have you read my paper?


Yes to all.
About evaluating who is ahead in a given position: you add up territory and influence for each. The way you calculate influence is via a static analysis of stone positions ("shadow"). I doubt that this can be enough to decide who is ahead - since that decision may take a lot of reading to decide the fate of the groups.

A specific question from page 22-23: you define "strong" and you write "White C is strong" (about the position on page 22). What part of the definition makes it so? It does not have 2 "eyespaces", and the single "eyespace" is not large enough for 2 eyes, or maybe I misunderstand something about the paper's definition of strong.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #48 Posted: Mon Feb 20, 2017 11:13 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
sorin wrote:
static analysis ... I doubt that this can be enough to decide who is ahead

i agree; the key word here is "decide". CG's static evaluation function produces a preliminary perception, not a final decision. Its perceptions just provide a kicking-off point for dynamic analysis.

Unlike minimax and Alphago, CG's evaluation function is not used to decide between candidates, but rather to choose an overall direction for dynamic analysis. That ultimately produces a set of sets of candidates that are each believed to achieve the highest-level goal; CG chooses the most popular move among them.

sorin wrote:
you write "White C is strong" (about the position on page 22). What part of the definition makes it so?

the answer to your question is the previous sentence on the facing page (p23): "A group whose combined colour map and shadow map embraces two eyespaces, or a single eyespace large enough to be able to form two eyes, is strong."

White C's combined map covers 18 points (including the two stones). My paper does not define a number for "large enough", but i would like it to be small enough to include white C, because in her commentary on the position, Jenny Shin says the two white stones are not easily attacked. I think most people would agree with her. Of course, if CG labels a group as "strong", that does not mean it thinks it is unconditionally alive; merely that it's not a prime target for attack.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #49 Posted: Fri Feb 24, 2017 8:30 am 
Dies with sente

Posts: 82
Liked others: 2
Was liked: 42
Rank: OGS 7 kyu
Hi!

I am having a look at your paper. One question, on page 25 (6. Paths):
Quote:
The paths between white D and white A, and between white D and white E, are both blocked by the colour map of the live group black C.

I guess you mean?
Quote:
The paths between white D and white A, and between white D and white E, are both blocked by the colour map of the live group black D.

_________________
I am the author of GoReviewPartner, a small software aimed at assisting reviewing a game of Go. Give it a try!

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #50 Posted: Fri Feb 24, 2017 6:09 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
pnprog wrote:
on page 25 ..I guess you mean The paths between white D and white A, and between white D and white E, are both blocked by the colour map of the live group black D.

yes! thank you for spotting the typo. :salute:

also, p27 should read: "The path between white D and white B is partially blocked by black D". and the picture on page 24 should be the same as the one on page 26, to show the path boundaries.

i think i must have redrawn the pictures after drafting the text and changed the order of labelling the groups, thinking that clockwise labelling looked better than top-down left-right, but forgot to change the text correspondingly.

i have a vague feeling that there's another typo somewhere else in the paper but can't remember what it is now!

i've always been a bit absent-minded when it comes to attention to fine detail...this mental handicap may be something that most people suffer from to some extent, which might be one reason why computers are better than most people at certain tasks which require precise memory - such as transcribing texts, mental arithmetic, chess and Go ?

it could partly explain why different people's memories of who said what and when are often controversial - as in the game of "Chinese Whispers" - and why narratives that have been hand-copied numerous times by numerous scribes (such as the Gospels) drift away from their originals, so cannot be taken as gospel. As Dara O'Briain says: "It's only the Bible.. it's not gospel!!" :study:

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #51 Posted: Sat Mar 04, 2017 6:44 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
in a thread about Leela, viewtopic.php?f=18&t=13251 zwim says:
Quote:
I was wondering how such powerful engines not only cannot see [an obvious game-winning move] immediately but do not even consider a move as important as an atari onto a big group ?! ... to not even assess a potential atari seems quite a big flaw in the design.
the reason dcnn engines sometimes appear to not consider good moves that are obvious to people is that whereas dcnn's so-called intuition (sic) "sees" convolutions of pattern fragments, they don't "see" commonsense Go concepts such as groups, eyes, etc. it was this fundamental flaw that led Alphago to miss the "obvious" defence to Lee's magic wedge which didn't work.

that's why i advocate combining commonsense and dcnn in a jury (or committee discussion rounds as suggested by UpWarrior)
viewtopic.php?f=18&t=14049

_________________
i ink, therefore i arm

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #52 Posted: Sun Mar 05, 2017 6:18 am 
Lives in sente

Posts: 857
Liked others: 0
Was liked: 139
djhbrown wrote:
the reason dcnn engines sometimes appear to not consider good moves that are obvious to people is that whereas dcnn's so-called intuition (sic) "sees" convolutions of pattern fragments, they don't "see" commonsense Go concepts such as groups, eyes, etc. it was this fundamental flaw that led Alphago to miss the "obvious" defence to Lee's magic wedge which didn't work.


But THAT works both ways, with the engines sometimes seeing good moves that the humans do not because based on scattered fragments rather than some central theme.

However this is not my main objection to your proposal. Saying that it would be better were there a rule based/pattern based AI capable of finding the best move is NOT the same thing as devising this AI. Please, I am NOT meaning to imply that it cannot be done, just pointing out that it has not been done. Prior to the introduction of MCTS based programs (and now neural nets) this WAS the approach being tried, with programs getting up to about 5 kyu. Perhaps a few stones stronger now.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #53 Posted: Sun Mar 05, 2017 2:52 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
Mike Novack wrote:
this WAS the approach being tried
No, it wasn't. Early programs used bottom-up processing, whereas CG uses top-down. To understand the difference between top-down and bottom-up, you could start by watching this video:
https://www.youtube.com/watch?v=WLDp82vwVkk

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #54 Posted: Tue Mar 07, 2017 9:43 am 
Dies in gote

Posts: 52
Liked others: 34
Was liked: 8
I noticed today this new paper from Deepmind that combines deep-learning with sub-goals oriented learning:
"
FeUdal Networks learn complex behaviour by breaking up tasks into sub-goals & learning to achieve them http://goo.gl/gVsWgn
"

_________________
Sorin - 361points.com

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #55 Posted: Tue Mar 07, 2017 4:26 pm 
Lives in sente

Posts: 857
Liked others: 0
Was liked: 139
djhbrown wrote:
Mike Novack wrote:
this WAS the approach being tried
No, it wasn't. Early programs used bottom-up processing, whereas CG uses top-down. To understand the difference between top-down and bottom-up, you could start by watching this video:
https://www.youtube.com/watch?v=WLDp82vwVkk


You are GROSSLY misunderstanding the LEVEL at which I am discussing when you dismiss what I said about AI attempts back then. Bottom up vs top down not to the point. Yes I clearly hear you that it MIGHT be possible to create an AI solution that would be stronger than the ones of a decade or so ago. Demonstrate the existence of the algorithm, be it top down, bottom up, or sideways.


Understand? I am NOT arguing that such an AI would not be a good thing, possibly a stronger go player than what we have now. I am saying AS YET DOES NOT EXIST.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #56 Posted: Mon Mar 13, 2017 6:48 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
"I algorithm, therefore I exist" - Rene Descartes al-Kwarizmi

Steps Towards an Artificial Intelligence Gobot:

step 1: stone pattern reactions (eg Zobrist, GnuGo)
step 2: stone pattern reactions + Monte-Carlo search (eg mogo, Crazy Stone, Zen)
step 3: DCNN pattern reactions + Monte-Carlo (eg Alphago, Leela, CrazyStoneX, ZenX, etc)
step 4: deductive reasoning (eg SwimCG) + Monte-Carlo Jury/Committee
Attachment:
topbottom.png
topbottom.png [ 106.67 KiB | Viewed 1184 times ]

Here's a narrative version of Swim's reasoning in the second example in my paper
https://papers.ssrn.com/sol3/papers.cfm ... id=2818149

"It looks like white will be about 10 points ahead if all his stones live, so I need to kill something. White group wA (of 4 stones) is his largest weak group, so let's attack it. To attack a group, i must first separate it from its friends, then surround it, and finally move in for the kill. wA's nearest friend is wE, so let's cut the path from wA to wE. My black groups bA and bE are both near the path; let's look at sliding into the path from bA. I can slide in at J13, which is not too far from bA. How would that look?

J13 is well-connected to bA, and now wE is surrounded and doesn't have room for eyes, so it's dead. So far, so good..

What can white do? He could try to save wA by connecting wA to wF; to do so, he could make a leaning attack on bA or bB from the wA-wF path. Let's consider bA first; he could attach to K11 at K12, or shoulder-hit on K11 at L12. Now let's look at bB: he could attach to M12 at L12, or peep at L13. L12 satisfies both goals, so that looks like his best choice.

Now it's my turn again... i've gained a couple of points by capturing wE, but that still leaves me 8 points back, so i would need to keep on attacking. wA is now connected to wF, but it's still weak. Its nearby friends are wB and wG; the path wAF-wB is {L10,M10} and the path wAF-wG is {L10, K10} + J10 or K9. L10 is in both paths, so let's choose that."

Attachment:
move79.png
move79.png [ 359.78 KiB | Viewed 1175 times ]

See What i Mean? Swim anticipates the sequence (J13, L12); (L10, ..) which it thinks achieves the goal of separating wAF from its friends.

It would next need to see how it can then reduce wAF's eyespace and stop it getting 2 eyes, but my paper doesn't go into that as Kim Myungwan has already shown us that L10 does so, defeating Lee's much talked-about wedge at L11.

Swim's context-sensitive reasoning methods may be a suitable platform for experimentation with what DARPA https://www.youtube.com/watch?v=-O01G3tSYpU calls "Third Wave AI" adaptation and synthesis processes that modify and create methods based on specific examples when a later play (or a Monte-Carlo prophecy) demonstrates its move didn't achieve its intended purpose.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #57 Posted: Mon Mar 13, 2017 11:14 pm 
Lives in sente

Posts: 871
Liked others: 25
Was liked: 168
Are you still banned from posting to the computer-go mailing list?

_________________
North Lecale

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #58 Posted: Wed Mar 15, 2017 9:14 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
Javaness2 wrote:
Are you still banned?

The school bully blue weasel troll tries to stir up trouble again. The first time it was happenstance, the second time coincidence. The third time it is enemy action.

Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #59 Posted: Thu Mar 23, 2017 9:26 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
pnprog wrote:
Hi!.. on page 25.. I guess you mean "The paths between white D and white A, and between white D and white E, are both blocked by the colour map of the live group black D."

yes again :tmbup: Also, whilst making a new episode (wip) of MiG, featuring the UEC JueYi-Zen game, i just came across the other typo i had wondered about in my previous acknowledgement of your observation: this typo is more subtle, but more significant: on page 21, corrections are as shown in the picture. Actually, maybe it's not so subtle, since quite obviously one can't have eyes in a shadow! :oops: ... only possible future eyes, which is why i use the term eyespace (= space for future eyes) when talking about how Swim distinguishes weak groups from strong ones.
Attachment:
p21.png
p21.png [ 416.54 KiB | Viewed 968 times ]


Attachments:
p21.png
p21.png [ 427.61 KiB | Viewed 897 times ]
Top
 Profile  
 
Offline
 Post subject: Re: Commonsense Go
Post #60 Posted: Fri Mar 24, 2017 6:52 pm 
Lives with ko
User avatar

Posts: 245
Liked others: 12
Was liked: 29
Rank: NR
Sneak Preview of upcoming Episode 32 of Mental Imagery in Go
https://www.youtube.com/playlist?list=P ... a3Hl1X_v-S
Attachment:
swagp23.png
swagp23.png [ 312.92 KiB | Viewed 889 times ]

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 153 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6 ... 8  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group