# When in doubt use brute force

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

1. ### ShaneGuest

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

2. ### Lawrence D'OliveiroGuest

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

3. ### Nik CoughlinGuest

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

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
4. ### ShaneGuest

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

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
5. ### Lawrence D'OliveiroGuest

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

>
> 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
6. ### 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

>> 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
7. ### ShaneGuest

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
>>> 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
8. ### GordonGuest

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

Beep Blue here, been there done that.

Meanwhile i am totally buggered with Go. All this fuzzy logic

Gordon, Jul 21, 2007
9. ### Fred DaggGuest

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

>
>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
10. ### Yeah RightGuest

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
11. ### Bruce SinclairGuest

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
12. ### Rob SGuest

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