6 ms·

Because combinatorial explosion?

by _ak 11y ago

eli_gottlieb 11y ago
Then how do human beings play Go? I've heard a lot of claims about human intelligence been non-replicable in-silico, but I've never heard the claim that it can somehow "defeat" a combinatorial explosion of possibilities just to plan a sales trip or play a board game.
- brianberns 11y ago
  Humans are much better at pattern recognition than computers. As a result, computers have to employ "brute force" algorithms that are vulnerable to combinatorial explosions.
  - Moshe_Silnorin 11y ago
    100 trillion synapses isn't brute force?
    - c54 11y ago
      Brute force = check every possible next move, and then assuming you've picked that move, check every possible opponent's move... you end up playing out a whole game's worth of turns for each turn. Brute force has this particular definition of trying every possible outcome. Humans pattern match pretty quickly and more or less guess based off prior experience and "intuition" -- it's not a brute force approach.
      - baddox 11y ago
        It may be the case that the hardware of your brain isn't essentially brute forcing behind the scenes, but it certainly isn't obvious to me that this is the case.
        zaroth 11y ago
        I thinks it's provable that it's not a brute force process. Since combinatorial explosion means by definition you cannot play to the end, and humans can in fact play Go, there has to be something else going on.
        baddox 11y ago
        You can still brute force all game states in a tree with height n, with some heuristic to estimate the strength of position at each game state. I certainly don't think humans solve Go, because I've never heard of any experts being undefeated.
        deleted 11y ago
        [deleted]
      - deleted 11y ago
        [deleted]
    - chongli 11y ago
      Most of that is irrelevant to the problem domain. Humans do a lot more with their brains than just play Go.
  - zaroth 11y ago
    Explains why there is such a focus on generating ever better and more efficient pattern matching algorithms. It also helps to be able to utilize ever more powerful machines. But I think well performing ones are all task-specific algorithms, there is no general purpose pattern matching capability that I know of that you can plug into a computer today and have it perform untrained tasks. I think it is possible, and it will be a big step forward. I would love to have time to work on this type of problem...
- bobfromhuddle 11y ago
  Heuristics. Really complex heuristics that defy simple codification: the feeling that a particular group of stones just isn't quite safe yet, the feeling that there is weakness in a structure on the other side of the board that can be exploited, the feeling that this corner is too hot right now, so you should definitely extend instead of the hane. If you're not already a go player, and want to get started, come sign up on online-go.com and ping me, I'm pathogenix.
  - eli_gottlieb 11y ago
    >Heuristics. Really complex heuristics that defy simple codification: The whole point of a heuristic is that it's a simple rule that works reasonably well, one might even say admissibly as they do in undergrad AI classes, for dealing with an unsolvably complex problem. Saying "humans use complex heuristics" amounts to just saying, "Humans use some algorithm I don't know." >the feeling that a particular group of stones just isn't quite safe yet, the feeling that there is weakness in a structure on the other side of the board that can be exploited, the feeling that this corner is too hot right now, so you should definitely extend instead of the hane. This mostly just sounds like probabilistic, bounded-rational prediction and evaluation of positions, which is what we currently think human cognition is anyway, but hey.
    - white-flame 11y ago
      It's not that humans only _use_ heuristics, it's that humans _create_ heuristics, and seem to be able to optimize the speed of the heuristic with training and use. They're also introspectable to some level, and can be combined with rational observation and feedback.
      - iheartmemcache 11y ago
        Devils advocate - ML is introspective at some level and certainly can observe (with Spock-like objectivity; almost defining the term) rationality, and take the result of each move and grade it with some degree of confidence as a "good move" or "bad move" [and even contextualize the move: i.e., move : 'e4' ; context : "opening" => evaluation - "great move"]. I agree with your first point though w/r/t heuristics and more importantly pattern recognition which can be used to integrate in more heuristic knowledge in your aggregate 'decision making system' at a way more 'effective' rate (with respect to time, within the domain of the game Go).
- KirinDave 11y ago
  The answer is actually: We don't know. Some people suggest comllex visual pattern matching is at play, but this seems really unlikely when you get to know the space because: 1. Good Go players can often reconstruct an entire game just by looking at the board, if they have some idea how it started. Given that good go players can substantially alter the board in the course of play (called "playing under the stones" in many books), this suggests more than simple visual recognition. 2. Some go players can even play "one color go" which is pretty amazing to watch. Its basically a game of who can keep every move in their head. This isn't a silly stunt, some people really practice this. Personally, I think that actually Go is more like a contextual NL problem than a vision definition problem. The existence of things like "joseki" and the fact that small board games play out in such a radically different way than big board games suggests that a variety of human cognitive shortcuts are at play. It is absolutely the case that with just a few months of modest practice almost anyone can beat the pants off the best go playing computers.
  - mquander 11y ago
    > It is absolutely the case that with just a few months of modest practice almost anyone can beat the pants off the best go playing computers. It sure isn't. The strongest computers are a few stones worse than professionals. You can count on your hands and toes the number of people in the United States that can beat the pants off the best go-playing computers.
  - Someone 11y ago
    https://en.m.wikipedia.org/wiki/Computer_Go#Performance https://en.m.wikipedia.org/wiki/Computer_Go#Performance: "In 2009, the first such programs appeared which could reach and hold low dan-level ranks on the KGS Go Server also on the 19x19 board." I know virtually nothing about what it takes to become a low-level dan ranked player, but I would think it would take more than "just a few months" to "beat the pants off" them. Back to the subject at hand: I think we will solve mathematical go before we solve chess (where 'solve' is used in the mathematical sense, so that, for example, we can prove "chess is a win for white, in 53 moves", and mathematical go is as described in https://math.berkeley.edu/~berlek/cgt/gobook.html; https://math.berkeley.edu/~berlek/cgt/gobook.html; its difference with regular go variants is the way half stones are counted). Reason is that both games, even with extensive pruning, are too complex for an full search of their game tree, and go has a simpler structure, making it easier to reason about it without doing that exhaustive search. [I also doubt I'll live to see either happen]
- nl 11y ago
  Humans uses features that aren't used by computers. I'm more familiar with Chess than Go, but in Chess people will often talk about things like "too crowded" or how pieces are exposed. These visible to humans quite easily, but hard to engineer sufficiently well to be useful to computers. In chess, brute force is easier. In Go, I suspect that some deep-learning style bots will develop similar features themselves in the hidden layers. It's worth noting that the Google Deep Mind team is looking at tackling NP-hard problems (like traveling salesman) with their Neural Turing Machines[1]. [1] See for eg: https://medium.com/@alevitale/notes-from-deep-learning-summit-2015-london-day-1-1599f603a40 https://medium.com/@alevitale/notes-from-deep-learning-summi...
  - neilh23 11y ago
    Yes - Go is full of concepts like 'aji' (lit. "taste"), thickness, influence, good and bad shape which are features that can only really be evaluated in terms of actual points dozens of moves later. I think Go is particularly difficult for AI because you need fuzzy pattern matching and precise reading out of positions (life and death problems). as well as the judgement to know when to use which.

Because combinatorial explosion?

by _ak 11y ago

Because combinatorial explosion?

Then how do human beings play Go? I've heard a lot of claims about human intelligence been non-replicable in-silico, but I've never heard the claim that it can somehow "defeat" a combinatorial explosion of possibilities just to plan a sales trip or play a board game.

brianberns 11y ago
Humans are much better at pattern recognition than computers. As a result, computers have to employ "brute force" algorithms that are vulnerable to combinatorial explosions.
- Moshe_Silnorin 11y ago
  100 trillion synapses isn't brute force?
  - c54 11y ago
    Brute force = check every possible next move, and then assuming you've picked that move, check every possible opponent's move... you end up playing out a whole game's worth of turns for each turn. Brute force has this particular definition of trying every possible outcome. Humans pattern match pretty quickly and more or less guess based off prior experience and "intuition" -- it's not a brute force approach.
    - baddox 11y ago
      It may be the case that the hardware of your brain isn't essentially brute forcing behind the scenes, but it certainly isn't obvious to me that this is the case.
      - zaroth 11y ago
        I thinks it's provable that it's not a brute force process. Since combinatorial explosion means by definition you cannot play to the end, and humans can in fact play Go, there has to be something else going on.
        baddox 11y ago
        You can still brute force all game states in a tree with height n, with some heuristic to estimate the strength of position at each game state. I certainly don't think humans solve Go, because I've never heard of any experts being undefeated.
        deleted 11y ago
        [deleted]
    - deleted 11y ago
      [deleted]
  - chongli 11y ago
    Most of that is irrelevant to the problem domain. Humans do a lot more with their brains than just play Go.
- zaroth 11y ago
  Explains why there is such a focus on generating ever better and more efficient pattern matching algorithms. It also helps to be able to utilize ever more powerful machines. But I think well performing ones are all task-specific algorithms, there is no general purpose pattern matching capability that I know of that you can plug into a computer today and have it perform untrained tasks. I think it is possible, and it will be a big step forward. I would love to have time to work on this type of problem...
bobfromhuddle 11y ago
Heuristics. Really complex heuristics that defy simple codification: the feeling that a particular group of stones just isn't quite safe yet, the feeling that there is weakness in a structure on the other side of the board that can be exploited, the feeling that this corner is too hot right now, so you should definitely extend instead of the hane. If you're not already a go player, and want to get started, come sign up on online-go.com and ping me, I'm pathogenix.
- eli_gottlieb 11y ago
  >Heuristics. Really complex heuristics that defy simple codification: The whole point of a heuristic is that it's a simple rule that works reasonably well, one might even say admissibly as they do in undergrad AI classes, for dealing with an unsolvably complex problem. Saying "humans use complex heuristics" amounts to just saying, "Humans use some algorithm I don't know." >the feeling that a particular group of stones just isn't quite safe yet, the feeling that there is weakness in a structure on the other side of the board that can be exploited, the feeling that this corner is too hot right now, so you should definitely extend instead of the hane. This mostly just sounds like probabilistic, bounded-rational prediction and evaluation of positions, which is what we currently think human cognition is anyway, but hey.
  - white-flame 11y ago
    It's not that humans only _use_ heuristics, it's that humans _create_ heuristics, and seem to be able to optimize the speed of the heuristic with training and use. They're also introspectable to some level, and can be combined with rational observation and feedback.
    - iheartmemcache 11y ago
      Devils advocate - ML is introspective at some level and certainly can observe (with Spock-like objectivity; almost defining the term) rationality, and take the result of each move and grade it with some degree of confidence as a "good move" or "bad move" [and even contextualize the move: i.e., move : 'e4' ; context : "opening" => evaluation - "great move"]. I agree with your first point though w/r/t heuristics and more importantly pattern recognition which can be used to integrate in more heuristic knowledge in your aggregate 'decision making system' at a way more 'effective' rate (with respect to time, within the domain of the game Go).
KirinDave 11y ago
The answer is actually: We don't know. Some people suggest comllex visual pattern matching is at play, but this seems really unlikely when you get to know the space because: 1. Good Go players can often reconstruct an entire game just by looking at the board, if they have some idea how it started. Given that good go players can substantially alter the board in the course of play (called "playing under the stones" in many books), this suggests more than simple visual recognition. 2. Some go players can even play "one color go" which is pretty amazing to watch. Its basically a game of who can keep every move in their head. This isn't a silly stunt, some people really practice this. Personally, I think that actually Go is more like a contextual NL problem than a vision definition problem. The existence of things like "joseki" and the fact that small board games play out in such a radically different way than big board games suggests that a variety of human cognitive shortcuts are at play. It is absolutely the case that with just a few months of modest practice almost anyone can beat the pants off the best go playing computers.
- mquander 11y ago
  > It is absolutely the case that with just a few months of modest practice almost anyone can beat the pants off the best go playing computers. It sure isn't. The strongest computers are a few stones worse than professionals. You can count on your hands and toes the number of people in the United States that can beat the pants off the best go-playing computers.
- Someone 11y ago
  https://en.m.wikipedia.org/wiki/Computer_Go#Performance https://en.m.wikipedia.org/wiki/Computer_Go#Performance: "In 2009, the first such programs appeared which could reach and hold low dan-level ranks on the KGS Go Server also on the 19x19 board." I know virtually nothing about what it takes to become a low-level dan ranked player, but I would think it would take more than "just a few months" to "beat the pants off" them. Back to the subject at hand: I think we will solve mathematical go before we solve chess (where 'solve' is used in the mathematical sense, so that, for example, we can prove "chess is a win for white, in 53 moves", and mathematical go is as described in https://math.berkeley.edu/~berlek/cgt/gobook.html; https://math.berkeley.edu/~berlek/cgt/gobook.html; its difference with regular go variants is the way half stones are counted). Reason is that both games, even with extensive pruning, are too complex for an full search of their game tree, and go has a simpler structure, making it easier to reason about it without doing that exhaustive search. [I also doubt I'll live to see either happen]
nl 11y ago
Humans uses features that aren't used by computers. I'm more familiar with Chess than Go, but in Chess people will often talk about things like "too crowded" or how pieces are exposed. These visible to humans quite easily, but hard to engineer sufficiently well to be useful to computers. In chess, brute force is easier. In Go, I suspect that some deep-learning style bots will develop similar features themselves in the hidden layers. It's worth noting that the Google Deep Mind team is looking at tackling NP-hard problems (like traveling salesman) with their Neural Turing Machines[1]. [1] See for eg: https://medium.com/@alevitale/notes-from-deep-learning-summit-2015-london-day-1-1599f603a40 https://medium.com/@alevitale/notes-from-deep-learning-summi...
- neilh23 11y ago
  Yes - Go is full of concepts like 'aji' (lit. "taste"), thickness, influence, good and bad shape which are features that can only really be evaluated in terms of actual points dozens of moves later. I think Go is particularly difficult for AI because you need fuzzy pattern matching and precise reading out of positions (life and death problems). as well as the judgement to know when to use which.