When in doubt use brute force

Discussion in 'NZ Computing' started by Shane, Jul 19, 2007.

  1. Shane

    Shane Guest

    OK OK, so I'm quoting Ken Thompson
    http://news.bbc.co.uk/2/hi/science/nature/6907018.stm
    It could be a case of game over for draughts - scientists say the ancient
    board game has finally been solved.

    A Canadian team has created a computer program that can win or draw any
    game, no matter who the opponent is.

    It took an average of 50 computers nearly two decades to sift through the
    500 billion billion possible draughts positions to come up with the
    solution.
    [...]
    Chinook looked at solving problems much like a human does by using trial and
    error to find out what appeared to be the best solutions. This is called a
    heuristic approach.

    However, Professor Schaeffer said that although the program was extremely
    successful - it won the World Checkers Championship in 1994 - it was not
    perfect and occasionally lost games.

    So the computer scientists tried another non-heuristic tack, where, over a
    number of years, hundreds of computers ran through game upon game of
    draughts to work out the sequences that would lead to winning, losing and
    drawing.

    Eventually, the new program gathered so much information that it "knew" the
    best move to play in every situation. This meant that every game it played
    led to a certain win, or, if its opponent played perfectly, a draw.
    [...]
    With the vast number of playing possibilities, draughts is the most complex
    game to have been solved to date - it was about a million times more
    complicated to solve than Connect Four.


    So it looks like every board game invented to this point is going to be
    brute forced into submission. Whilst I dont lament the games being solved
    as such, I was kind of hoping for a more elegant method.


    --
    Q: Why do mathematicians often confuse Christmas and Halloween?
    A: Because Oct 31 = Dec 25.
     
    Shane, Jul 19, 2007
    #1
    1. Advertising

  2. In message <f7oiuj$g6l$>, Shane wrote:

    > So it looks like every board game invented to this point is going to be
    > brute forced into submission.


    Draughts is peanuts compared to chess, and chess is peanuts compared to Go.

    I don't think a brute-force approach will work with chess in our lifetimes.
    Or with Go, in another couple of lifetimes.
     
    Lawrence D'Oliveiro, Jul 20, 2007
    #2
    1. Advertising

  3. Shane

    Nik Coughlin Guest

    Lawrence D'Oliveiro wrote:
    > In message <f7oiuj$g6l$>, Shane wrote:
    >
    >> So it looks like every board game invented to this point is going to
    >> be brute forced into submission.

    >
    > Draughts is peanuts compared to chess, and chess is peanuts compared
    > to Go.
    >
    > I don't think a brute-force approach will work with chess in our
    > lifetimes. Or with Go, in another couple of lifetimes.


    Don't be so sure. They are making good progress with quantum computing,
    these kind of problems are perfect for massive parallelisation.
     
    Nik Coughlin, Jul 20, 2007
    #3
  4. Shane

    Shane Guest

    Lawrence D'Oliveiro wrote:

    > In message <f7oiuj$g6l$>, Shane wrote:
    >
    >> So it looks like every board game invented to this point is going to be
    >> brute forced into submission.

    >
    > Draughts is peanuts compared to chess, and chess is peanuts compared to
    > Go.
    >
    > I don't think a brute-force approach will work with chess in our
    > lifetimes. Or with Go, in another couple of lifetimes.


    From the article:
    Researchers are now hoping to move on to even bigger problems, however it
    seems that grand master of the board games - chess - may remain unsolved
    for some time.

    It has somewhere in the range of a billion billion billion billion billion
    possible positions, meaning that computers, with their current capacity,
    would takes aeons to solve it.
    --
    Q: What do you get when you cross a mosquito with a rock climber?
    A: Nothing. You can't cross a vector and a scalar.
     
    Shane, Jul 20, 2007
    #4
  5. In message <f7p6e8$n6o$>, Nik Coughlin wrote:

    > Lawrence D'Oliveiro wrote:
    >> In message <f7oiuj$g6l$>, Shane wrote:
    >>
    >>> So it looks like every board game invented to this point is going to
    >>> be brute forced into submission.

    >>
    >> Draughts is peanuts compared to chess, and chess is peanuts compared
    >> to Go.
    >>
    >> I don't think a brute-force approach will work with chess in our
    >> lifetimes. Or with Go, in another couple of lifetimes.

    >
    > Don't be so sure. They are making good progress with quantum computing...


    Which there are sound reasons to believe will never work.
     
    Lawrence D'Oliveiro, Jul 20, 2007
    #5
  6. Shane

    Rob.S. Guest

    Lawrence D'Oliveiro wrote:
    > In message <f7p6e8$n6o$>, Nik Coughlin wrote:
    >
    >> Lawrence D'Oliveiro wrote:
    >>> In message <f7oiuj$g6l$>, Shane wrote:
    >>>
    >>>> So it looks like every board game invented to this point is going to
    >>>> be brute forced into submission.
    >>> Draughts is peanuts compared to chess, and chess is peanuts compared
    >>> to Go.
    >>>
    >>> I don't think a brute-force approach will work with chess in our
    >>> lifetimes. Or with Go, in another couple of lifetimes.

    >> Don't be so sure. They are making good progress with quantum computing...

    >
    > Which there are sound reasons to believe will never work.


    Or when one does work, it will instantly become self-aware, will soak up
    the entire internet in 5 days, will ponder over it for a day, then on
    the seventh day will create it's own universe and move into it. Which we
    won't mind at all, considering we won't be here any longer, the quantum
    computer having used the sum total of energy in this universe to create
    it's own.
    :)
    Might not be a bad thing.
    Rob S
     
    Rob.S., Jul 20, 2007
    #6
  7. Shane

    Shane Guest

    Rob.S. wrote:

    > Lawrence D'Oliveiro wrote:
    >> In message <f7p6e8$n6o$>, Nik Coughlin wrote:
    >>
    >>> Lawrence D'Oliveiro wrote:
    >>>> In message <f7oiuj$g6l$>, Shane wrote:
    >>>>
    >>>>> So it looks like every board game invented to this point is going to
    >>>>> be brute forced into submission.
    >>>> Draughts is peanuts compared to chess, and chess is peanuts compared
    >>>> to Go.
    >>>>
    >>>> I don't think a brute-force approach will work with chess in our
    >>>> lifetimes. Or with Go, in another couple of lifetimes.
    >>> Don't be so sure. They are making good progress with quantum
    >>> computing...

    >>
    >> Which there are sound reasons to believe will never work.

    >
    > Or when one does work, it will instantly become self-aware, will soak up
    > the entire internet in 5 days, will ponder over it for a day, then on
    > the seventh day will create it's own universe and move into it. Which we
    > won't mind at all, considering we won't be here any longer, the quantum
    > computer having used the sum total of energy in this universe to create
    > it's own.
    > :)
    > Might not be a bad thing.
    > Rob S


    Theres a second theory, that this has already happened :)
    --
    Q: What's big, grey, and proves the uncountability of the reals?
    A: Cantor's diagonal elephant.
     
    Shane, Jul 20, 2007
    #7
  8. Shane

    Gordon Guest

    On Fri, 20 Jul 2007 14:13:07 +1200, Lawrence D'Oliveiro wrote:

    > I don't think a brute-force approach will work with chess in our
    > lifetimes.


    Beep Blue here, been there done that.

    Meanwhile i am totally buggered with Go. All this fuzzy logic
     
    Gordon, Jul 21, 2007
    #8
  9. Shane

    Fred Dagg Guest

    On 21 Jul 2007 08:46:30 GMT, Gordon <> exclaimed:

    >On Fri, 20 Jul 2007 14:13:07 +1200, Lawrence D'Oliveiro wrote:
    >
    >> I don't think a brute-force approach will work with chess in our
    >> lifetimes.

    >
    >Beep Blue here, been there done that.
    >

    Deep Blue wasn't full brute force - only a few moves ahead, and even
    then not just brute force.
     
    Fred Dagg, Jul 21, 2007
    #9
  10. Shane

    Yeah Right Guest

    On , , Fri, 20 Jul 2007 08:54:53 +1200, When in doubt use brute
    force, Shane <-a-geek.net> wrote:

    >So it looks like every board game invented to this point is going to be
    >brute forced into submission. Whilst I dont lament the games being solved
    >as such, I was kind of hoping for a more elegant method.


    I don't know, it will be great when they sort chess out.
    >
     
    Yeah Right, Jul 23, 2007
    #10
  11. In article <>, Yeah Right <> wrote:
    >On , , Fri, 20 Jul 2007 08:54:53 +1200, When in doubt use brute
    >force, Shane <-a-geek.net> wrote:
    >
    >>So it looks like every board game invented to this point is going to be
    >>brute forced into submission. Whilst I dont lament the games being solved
    >>as such, I was kind of hoping for a more elegant method.

    >
    >I don't know, it will be great when they sort chess out.


    Chess is (relatively) easy for a computer and has been for a while. Now if
    they can get a computer to professional dan standard at Go, that would be an
    achievement :)
     
    Bruce Sinclair, Jul 24, 2007
    #11
  12. Shane

    Rob S Guest

    Bruce Sinclair wrote:
    > In article <>, Yeah Right <> wrote:
    >> On , , Fri, 20 Jul 2007 08:54:53 +1200, When in doubt use brute
    >> force, Shane <-a-geek.net> wrote:
    >>
    >>> So it looks like every board game invented to this point is going to be
    >>> brute forced into submission. Whilst I dont lament the games being solved
    >>> as such, I was kind of hoping for a more elegant method.

    >> I don't know, it will be great when they sort chess out.

    >
    > Chess is (relatively) easy for a computer and has been for a while. Now if
    > they can get a computer to professional dan standard at Go, that would be an
    > achievement :)
    >

    Don't know about Go, but mine's a winner at stopping. :)

    --

    Rob
    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    http://aspir8or.com
    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


    Fine, fine, everything is fine. But using your GUI's breaking my mind!
    Change this, don't change that, can't you redesign!!! (to the tune of
    'read the signs')
    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
     
    Rob S, Jul 24, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Martino
    Replies:
    8
    Views:
    10,784
    Bill Marshal
    Feb 1, 2006
  2. Rob Slade, doting grandpa of Ryan and Trevor

    REVIEW: "Brute Force", Matt Curtin

    Rob Slade, doting grandpa of Ryan and Trevor, Jun 16, 2005, in forum: Computer Security
    Replies:
    0
    Views:
    535
    Rob Slade, doting grandpa of Ryan and Trevor
    Jun 16, 2005
  3. Replies:
    0
    Views:
    1,416
  4. Replies:
    2
    Views:
    1,085
    Bert Hyman
    Dec 31, 2008
  5. Lawrence D'Oliveiro

    Brute-Force SSH Attacks Still Worthwhile

    Lawrence D'Oliveiro, Apr 18, 2009, in forum: NZ Computing
    Replies:
    0
    Views:
    368
    Lawrence D'Oliveiro
    Apr 18, 2009
Loading...

Share This Page