Re: [pygame] PyGameDB coming along well

["Hugo Arts" <hugo.yoshi@xxxxxxxxx>]

On Tue, Aug 19, 2008 at 10:39 AM, kschnee <kschnee@xxxxxxxxxx> wrote:
> On Tue, 19 Aug 2008 07:49:16 -0700, James Paige <Bob@xxxxxxxxxxxxxxxxxxx>
> wrote:
>> That reminds me of something I read recently. Apparently the first ever
>> computer program that can play Go with near-human skill was developed
>> this year:
>> http://www.usgo.org/index.php?%23_id=4602
>>
>> Of course, it only beat the human in 1 out of 3 matches :)
>
>
> From what I understand, the reason that AI for these games is so hard is
> that the general method being used is a brute-force lookup table. A chess
> computer has a list of each possible board position that could result from
> its next move, and the possible moves from there, eventually dead-ending at
> some kind of evaluation of whether a board position is "good." So the AI
> picks the move that its lookup table says is most likely to give a good
> result. Because there are 20 possible moves for White at the beginning and
> 400 possible board configurations after Black goes once, that's a
> ridiculously huge database for looking even a few moves ahead. Go has even
> more possible moves, making it harder to take on _with that strategy_. In
> other words the trouble in building a Go computer isn't so much because Go
> is innately more complicated than Chess, but because of the specific way
> that it's complicated.
>
> What's been proposed as an alternative to this strategy is to try to get a
> machine to recognize patterns of pieces, the way that a human might
> recognize a "knight fork" situation, so that it can develop general
> strategies instead of relying on exact known board layouts. If anyone can
> build a program like that, it'd be useful for other purposes too.
>
>

The method used in beating the Go professional player was a Monte
Carlo algorithm, i.e. the computer did not scan the entire set of
possible moves, but just a random sample from it, and judged these for
their outcomes. It should also be noted that the computer had a
9-stone handicap (i.e. it could place 9 stones on the board before the
game began), and the computer in question was an 800-core monster
supercomputer. In go, a 9-stone handicap is a huge advantage in a
game. Kind of like taking some one's queen and knights away in a chess
game before the game starts, possibly even worse. The computer did
play at human levels, but certainly not at professional levels, and
the amount of resources required to do even that are tremendous.

Developing an algorithm smarter and more efficient than brute force is
quite a difficult problem, perhaps even AI-complete. This goes for
chess and other games as well of course, but these have a more limited
possible move set, and so are more amenable to brute-force solutions.
The average amount of possible moves in a chess situation is around
40, but for go it is closer to 250.
Even so, I think it is easier to increase computational power than it
is to solve the AI problem. With Moore's law still standing, and
brute-force Go algorithms being embarrasingly parallel (each possible
move can be considered separately), stronger Go playing computers will
most likely come from the direction of supercomputers and many-core
machines with the same Monte Carlo approach.

Back on topic: smoke, mist, or other steam derivatives are a bit lame,
though I am all for a pun on steam, these are a bit obvious. I think
it would also be a good idea(tm) to get either a snake or flying
circus reference into the name. Anyone know any skits that are
smoke/steam/hydrogen related?