3 ms·

10000 samples are nothing compared to 2^100 possible outputs. It is absolutely, definitely not a "brute search". Testing a small fraction of possibilities (e.g.

10000 samples are nothing compared to 2^100 possible outputs. It is absolutely, definitely not a "brute search". Testing a small fraction of possibilities (e.g. 0.000001%) is called heuristics, and that's what people use too. Please learn a bit of combinatorics. > After all, the human solving these problem doesn't make 10k attempts before getting a solution, do they? No. People have much better "early rejection", also human brain has massive parallel compute capacity. It's ridiculous to demand GPT-4 performs as good as a human. Obviously its vision is much worse and it doesn't have 'video' and physics priors people have, so it has to guess more times.

lelanthran 2y ago
> 10000 samples are nothing compared to 2^100 possible outputs. It is absolutely, definitely not a "brute search". Testing a small fraction of possibilities (e.g. 0.000001%) is called heuristics, and that's what people use too. Brute searching literally means generating solutions until one works. Which is exactly what is being done here. > Please learn a bit of combinatorics. Don't be condescending - I understand the problem space just fine. Fine enough to realise that the problem was constructed specifically to ensure that "solutions" such as this just won't work. Which is why this "solution" is straight-up broken (doesn't meet the target, exceeds the computationally bounds, etc). > It's ridiculous to demand GPT-4 performs as good as a human. Wasn't the whole point of this prize to spur interest in a new approach to learning? What does GPT-[1234] have to do with the contest rules? Especially since this solution broke those rules anyway? > Obviously its vision is much worse and it doesn't have 'video' and physics priors people have, so it has to guess more times. That's precisely my point - it has to guess. Humans aren't guessing for those types of problems (not for the few that I saw anyway).
- ealexhudson 2y ago
  I think to be clear, brute force generally means an iterative search of a solution space. I don't think that's what this system is doing, and it's not like it's following some search path and returning as early as possible. It's similar that a lot of wrong answers are being thrown up, but I think this is more like a probabilistic system which is being pruned than a walk of the solution space. It's much smarter, but not as smart as we would like.
  - lelanthran 2y ago
    > I think to be clear, brute force generally means an iterative search of a solution space. Sure, but not an exhaustive one - you stop when you get a solution[1]. Brute force does not require an exhaustive search in order to be called brute-force. GP was using the argument that because it is not exhaustive, it cannot be brute-force. That's the wrong argument. Brute-force doesn't have to be exhaustive to be brute-force. [1] Or a good enough solution.
    - naasking 2y ago
      A brute force search can be expected to find a solution after a more thorough search of the space of possibilities. If it really is only searching 0.000001% of that space before finding solutions, then some structure of the problem is guiding the search and it's no longer brute force.
- killerstorm 2y ago
  [flagged]
  - lelanthran 2y ago
    > I studied algorithms for years. Who hasn't? > You're 100% WRONG on everything you wrote. Maybe you should update the wikipedia page, then all the other textbooks, that uses a definition of brute-force that matches my understanding of it. From https://en.wikipedia.org/wiki/Brute-force_search https://en.wikipedia.org/wiki/Brute-force_search > Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. Further, in the same page https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up_brute-force_searches https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up... > One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class. I mean, the approach under discussion is literally exactly this. Now, Mr "ACM ICPC, studied algorithms for years", where's your reference that reducing the solution space using heuristics results in a non-brute-force algorithm?
    - baobabKoodaa 2y ago
      This was extremely cringe worthy to read. You are confidently wrong about this. You are trying to redefine well established terminology. I don't care about whatever random wiki page you might find to "support your claims". Anybody who has worked a lot on algorithms (including myself) knows what brute force means and this is not it. Also: lol at your "who hasn't" comment. Because you clearly haven't.
      - lelanthran 2y ago
        > You are trying to redefine well established terminology. Reference? Link, even? > don't care about whatever random wiki page you might find to "support your claims". That isn't some "random wiki" page; that's the wikipedia page for this specific term. I'm not claiming to have defined this term, I'm literally saying I only agree with the sources for this term. > Also: lol at your "who hasn't" comment. Because you clearly haven't. Talk about cringe-worthy.

lelanthran 2y ago

> 10000 samples are nothing compared to 2^100 possible outputs. It is absolutely, definitely not a "brute search". Testing a small fraction of possibilities (e.g. 0.000001%) is called heuristics, and that's what people use too. Brute searching literally means generating solutions until one works. Which is exactly what is being done here. > Please learn a bit of combinatorics. Don't be condescending - I understand the problem space just fine. Fine enough to realise that the problem was constructed specifically to ensure that "solutions" such as this just won't work. Which is why this "solution" is straight-up broken (doesn't meet the target, exceeds the computationally bounds, etc). > It's ridiculous to demand GPT-4 performs as good as a human. Wasn't the whole point of this prize to spur interest in a new approach to learning? What does GPT-[1234] have to do with the contest rules? Especially since this solution broke those rules anyway? > Obviously its vision is much worse and it doesn't have 'video' and physics priors people have, so it has to guess more times. That's precisely my point - it has to guess. Humans aren't guessing for those types of problems (not for the few that I saw anyway).

ealexhudson 2y ago
I think to be clear, brute force generally means an iterative search of a solution space. I don't think that's what this system is doing, and it's not like it's following some search path and returning as early as possible. It's similar that a lot of wrong answers are being thrown up, but I think this is more like a probabilistic system which is being pruned than a walk of the solution space. It's much smarter, but not as smart as we would like.
- lelanthran 2y ago
  > I think to be clear, brute force generally means an iterative search of a solution space. Sure, but not an exhaustive one - you stop when you get a solution[1]. Brute force does not require an exhaustive search in order to be called brute-force. GP was using the argument that because it is not exhaustive, it cannot be brute-force. That's the wrong argument. Brute-force doesn't have to be exhaustive to be brute-force. [1] Or a good enough solution.
  - naasking 2y ago
    A brute force search can be expected to find a solution after a more thorough search of the space of possibilities. If it really is only searching 0.000001% of that space before finding solutions, then some structure of the problem is guiding the search and it's no longer brute force.
killerstorm 2y ago
[flagged]
- lelanthran 2y ago
  > I studied algorithms for years. Who hasn't? > You're 100% WRONG on everything you wrote. Maybe you should update the wikipedia page, then all the other textbooks, that uses a definition of brute-force that matches my understanding of it. From https://en.wikipedia.org/wiki/Brute-force_search https://en.wikipedia.org/wiki/Brute-force_search > Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. Further, in the same page https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up_brute-force_searches https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up... > One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class. I mean, the approach under discussion is literally exactly this. Now, Mr "ACM ICPC, studied algorithms for years", where's your reference that reducing the solution space using heuristics results in a non-brute-force algorithm?
  - baobabKoodaa 2y ago
    This was extremely cringe worthy to read. You are confidently wrong about this. You are trying to redefine well established terminology. I don't care about whatever random wiki page you might find to "support your claims". Anybody who has worked a lot on algorithms (including myself) knows what brute force means and this is not it. Also: lol at your "who hasn't" comment. Because you clearly haven't.
    - lelanthran 2y ago
      > You are trying to redefine well established terminology. Reference? Link, even? > don't care about whatever random wiki page you might find to "support your claims". That isn't some "random wiki" page; that's the wikipedia page for this specific term. I'm not claiming to have defined this term, I'm literally saying I only agree with the sources for this term. > Also: lol at your "who hasn't" comment. Because you clearly haven't. Talk about cringe-worthy.