Commonsense Go

[daal]

AlphaGo upended 5000 years of human dominance less than a year ago. It doesn't seem like the time to lament that a theoretically much better go program hasn't yet been implemented.

[sorin]

Let's make this simple:

GnuGo uses the concept of groups in its design.

Commonsense Go uses the concept of groups in its design.

AlphaGo does not use the concept of groups in its design.

(and just in case AlphaGo does have groups in there somewhere, although not as core part):
The Go AI at https://chrisc36.github.io/deep-go/ is a pure neural net move selector bot (no MCTS or value network as in AlphaGo) so definitely doesn't have groups in its design.

Actually AlphaGo uses the concept of groups in its design at a very fundamental level: the board representation which is the input to the whole system uses a layer that tells what stones are connected in groups. This is described in the Nature paper.

Your intuition is right though - they could in principle have used just the stone positions - but that would take longer and be a more expensive learning process, since it would have to learn about the stones connectivity as well.

[Mike Novack]

Problem reduction is a commonsense way to go about solving a hard problem, by dividing it into two smaller and easier ones, as recommended by Polya's “How to Solve it” [15].

You just aren't "seeing it". Perhaps the reason being that not having enough practical experience in problem solving using software.

Solving the problem (play a very strong game of go) by using a neural net IS precisely an example of "finding the right island". And notice that I put it THAT way, because no, tackling a complex problem by just looking for any "island" between you and the goal is NOT a good way to proceed (Polya has oversimplified the arguement -- you need the right island, a useful island). Often a more fruitful way is to think of working backward from the goal (can you there would be a way from there to an island that was "terra cognito" (you already know how to get to THAT one).

Here the problem has broken into two parts. Code a program that implements a neural net and then train that net to evaluate the desired function <given a board position, return the best next move>. Both parts known how to do <if for board positions you can determine if the move the NN returns is the right one, then you can train the NN to evaluate the function>

And you aren't making a good case, not really making any case, that if your CS proposal can explain WHY that move is a good move the move would be a better move (than the SAME move sans explanation). Please, I am NOT telling you that being able to say "why" would not have value. Not saying that a program that made the right move AND told you why would not be a better program in the sense of more useful. But NOT better in the sense of making better moves (not a stronger go player).

[djhbrown]

using a neural net IS precisely an example of "finding the right island".

yes, it is. it's a good example of humans applying Polya's principle to solve their problem.

i'm not talking about that; i'm talking about software itself using the principle to solve its own problem.

You just aren't "seeing it". Perhaps the reason being that not having enough practical experience in problem solving using software.

please google me and check out my cv before defaming my PhD in artificial intelligence and other published work in software development.

[Mike Novack]

please google me and check out my cv before defaming my PhD in artificial intelligence and other published work in software development.

I did say PERHAPS. There could be other reasons. I can think of many possible reasons.

Never went back for a graduate degree but didn't stop studying and a few hundred thousand lines of code in my day. But that is NOT relevant.

But please do look at the LOGIC of what you are saying. If there is a function, which given a board position returns the best next move and there is a second function, which given a board position returns the pair of values, the best next move and what color your underwear is (pick anything) WHY do you say the second function would play stronger go?

Or how about just sticking to humans. Are you saying I should consider a top Chinese pro who does not speak English (and so cannot tell me why) would because of that necessarily play weaker go than a top Chinese pro who did speak English (and so could tell me why).

[djhbrown]

...the LOGIC of what you are saying. If there is a function, which given a board position returns the best next move and there is a second function, which given a board position returns the pair of values, the best next move and what color your underwear is (pick anything) WHY do you say the second function would play stronger go?

i didn't say that.

i couldn't decide whether you genuinely don't follow the logic of my argument, or are just winding me up (ie, trolling).

So i googled you but could only find your comments on other topics in this forum, which led me to believe that i should give you the benefit of the doubt and assume it is the former case.

So here is my attempt to explain my argument:

Master Alphago's technique is the best we know of, so far. But that doesn't mean she is the best that could ever be made, even if no human could ever beat her.

So the questions facing everyone interested in AI are these:

1. what could be better?
2. what does DCNN+Monte's success tell us about the intellectual challenge of Go?

last year i mused upon the second question in comments on YouTube videos of the Alphago - Lee Sedol match.

As to the first question, i don't have an unequivocal answer, but i did make a suggestion (CG) for future research last year, which included testing a simulated CG on just one example - the only example i know of where Alphago made a game-losing move. I was pleasantly surprised that CG quickly found a move that as far as i could see was better than the move Alphago made - it was a variation of the defence to Lee's wedge that Myungwan Kim found.

By itself, that doesn't prove anything, but it is a suggestive evidence.

Since then, DeepMind have said that they have improved Alphago so she wouldn't make the same mistake again in the same situation.

So nothing can be said for sure as to the relative playing strengths of DCNN and deductive logic. It would, however, be easy to test: simply replace Master's DCNN move generator with CG's, and her evaluation DCNN with CG's estimation function, and using all the rest of Master's paraphernalia (parallel Monte search on gerzillions of processors), see what happens when they face each other.

Only DeepMind could do that test, but a pimply kid with a PC could do a simpler and cheaper mini-test: implement Alpha's published algorithms as one program and CG's as another and let them battle it out on the same hardware. My adolescence finished half a century ago, and the rest of my life is too short, so i won't be that pimply kid.

As to the fact that CG can SWIM, i never claimed that that implies its thinking is superior to any other technique - that was your own illogical inference.

That it can, merely demonstrates that its way of thinking is comprehensible to people in terms that they can understand. If its thinking is reasonable, then it could be a useful learning aide.

Please note that i am using the term "thinking" in its Turing sense; i do not claim that CG's thinking is isomorphic to human thinking. Indeed, i have sometimes tried to apply CG's methods in my own games, and have sometimes discovered a move that was better than the one which had first come to my mind. But i am a weak player, so that doesn't mean anything - it's merely an indoor recreation.

[pookpooi]

So the conclusion is that djhbrown

-never claim his suggestion is superior to other suggestion

I agree

- his suggestion can satisfied his curiosity

I agree

-never claim his suggestion can benefit to any people other than him

I agree

[pnprog]

The program is designed, but it's up to others to turn it into software. Could it beat Alphago across the board, and with much less hardware? I think it could

This is unlikely that somebody will invest energy and time to implement somebody else ideas if that person is not convinced by your ideas from the beginning.

But, really, why don't you just go ahead an make that software yourself? I means, whatever how old you are now, considering your academic background, learning programming up to a sufficient level to implement your ideas is probably a matter of 1~3 months of self teaching on your spare time.

As a side effect, you may very well get rich in the process, or get a Nobel Prize, or land the perfect job at some perfect company.

Best regards,

[Mike Novack]

No, I am not "trolling" but yes, I do not get your logic.

I wish you would take another look at what you are saying in computer science terms, in mathematical and logical terms.

I will now more carefully/precisely define a FUNCTION. The function shall be "given a board position*, return a move such that there is no better move" < I have changed that from "best move" because there might not BE a best move. That this would sometimes be the case should be obvious from symmetry > So this function would always return a value, not necessarily unique, and so not always the same value every time evaluated.

I have NOT yet discussed HOW the eval will be done. Not talking about implementation in specific terms but in general terms.

Now assume we have two (very different) computer programs, A and B that both correctly "eval" that function. WHY (for what reason) are you arguing B is better than A? Having done a lot of this sort of thing, I can understand reasons like "runs faster", "easier to test", etc. But I cannot understand "more correctly" because we began assuming that they both DID correctly evaluate the function.

Look, back in my working days, given a problem that I saw could be solved (at the abstract level) by a finite state machine I might choose that approach (define the FSM and then write a program that implemented all the states/transitions). I might choose that because that "island" broke the problem into some very well defined and easily testable parts (independently testable). Almost all the of the other programmers in this very large shop would have tackled the problem more directly. But once they had gotten their solution debugged I would not make a claim like "my solution was more CORRECT".

Treat me like I was dense. That I am somehow not able to see that a program (in the ABSTRACT sense) depended on what language was used to create the concrete implementation.

Again to look at this from the human side of things, what exactly makes you conclude that the ability of the top pro to look at a proposed move and explain why it was a good move (or do the reading to confirm a good move) meant that this is how (the mental process) by which the move was discovered. When going over the course of a game by two top human players, doesn't one of them sometimes make a move that the other did not expect? Though afterwards can see why a good move.

If you were making a claim like "the process of training a neural net to the function will not converge fast enough to a correct evaluation of the function" so we need some other solution I would be more understanding << that te training of a large enough neural net must converge on a correct solution is clear; though the domain is VERY large, it IS finite >>

* By "board position" I don't mean just the stones on the board but also some "state information", for example, whether any point illegal because of ko, etc.

[djhbrown]

I will now more carefully/precisely define a FUNCTION. The function shall be "given a board position*, return a move such that there is no better move" ...

Now assume we have two (very different) computer programs, A and B that both correctly "eval" that function. WHY (for what reason) are you arguing B is better than A?

as the Irishman said: "If I were going to Dublin, I wouldn't be starting from here".

Mike, i think you are tying yourself in knots because you are starting off from the wrong place, namely: you seem to have inferred that i assume that A and B both compute a function of a board position which "return a move such that there is no better move".

But i don't assume that.

i do assume this:

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)

1. We know from the game record that K10 didn't work, because Lee saved his dead stones and went on to win the game.
2. Kim showed us that L10 does work
3. i believe that J13 is better than K10, because i think that J13 forces L12, after which black can play L10 and kill white in a variation of Kim's analysis.

game4.sgf

(17.3 KiB) Downloaded 506 times

game4move78.png (370.36 KiB) Viewed 11364 times

[sorin]

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?

[djhbrown]

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

[sorin]

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.

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

[djhbrown]

how is this different from the traditional rule-based systems?

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

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? ... id=2818149

[sorin]

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