Velocity Reviews > When in doubt use brute force

# When in doubt use brute force

Shane
Guest
Posts: n/a

 07-19-2007
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.

Lawrence D'Oliveiro
Guest
Posts: n/a

 07-20-2007
In message <f7oiuj\$g6l\$(E-Mail Removed)>, 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.

Nik Coughlin
Guest
Posts: n/a

 07-20-2007
Lawrence D'Oliveiro wrote:
> In message <f7oiuj\$g6l\$(E-Mail Removed)>, 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.

Shane
Guest
Posts: n/a

 07-20-2007
Lawrence D'Oliveiro wrote:

> In message <f7oiuj\$g6l\$(E-Mail Removed)>, 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.

Lawrence D'Oliveiro
Guest
Posts: n/a

 07-20-2007
In message <f7p6e8\$n6o\$(E-Mail Removed)>, Nik Coughlin wrote:

> Lawrence D'Oliveiro wrote:
>> In message <f7oiuj\$g6l\$(E-Mail Removed)>, 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.

Rob.S.
Guest
Posts: n/a

 07-20-2007
Lawrence D'Oliveiro wrote:
> In message <f7p6e8\$n6o\$(E-Mail Removed)>, Nik Coughlin wrote:
>
>> Lawrence D'Oliveiro wrote:
>>> In message <f7oiuj\$g6l\$(E-Mail Removed)>, 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

Shane
Guest
Posts: n/a

 07-20-2007
Rob.S. wrote:

> Lawrence D'Oliveiro wrote:
>> In message <f7p6e8\$n6o\$(E-Mail Removed)>, Nik Coughlin wrote:
>>
>>> Lawrence D'Oliveiro wrote:
>>>> In message <f7oiuj\$g6l\$(E-Mail Removed)>, 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.

Gordon
Guest
Posts: n/a

 07-21-2007
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

Fred Dagg
Guest
Posts: n/a

 07-21-2007
On 21 Jul 2007 08:46:30 GMT, Gordon <(E-Mail Removed)> 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.

Yeah Right
Guest
Posts: n/a

 07-23-2007
On , , Fri, 20 Jul 2007 08:54:53 +1200, When in doubt use brute
force, Shane <(E-Mail Removed)-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.
>