Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re (tilly) 3: OO vs. global variables...

by tilly (Archbishop)
on Sep 04, 2001 at 22:41 UTC ( [id://110121]=note: print w/replies, xml ) Need Help??


in reply to Re: Re: OO vs. global variables...
in thread OO vs. global variables...

Be warned. While you might build a prototype in Perl, you will not have any possibility of succeeding in your eventual goal without rewriting in a different language. Perl is just too wasteful on memory to be great at this task.

OTOH traditional game-playing algorithms are simply incapable of playing Go well at any point in the forseeable future. We will not have great Go-playing computers unless we rethink how computers work (eg quantum computing) or else rethink how computers are supposed to play games.

For those who don't know about this problem, here is the general issue. Computers play chess by having a simplistic evaluation of a board, and then thinking through all possible interactions several moves ahead and evaluating the end position. The result is that consequences that humans understand by having a sophisticated internal understanding of how games evolve, a computer can figure out by analyzing far enough ahead that it sees that things will work that way, even if it cannot explain why.

As a result the same program that was a mediocre player on 1980's hardware was very good on 90's hardware and is grandmaster level on current hardware. The program isn't any better. We have just thrown hardware at it. In fact there appears to be an approximately linear relationship between the number of moves ahead the program works, and how strong it is. Looking ahead one more move takes exponentially more work, but computers get better exponentially fast, so in terms of chess strength computers progressed approximately linearly.

Go is a much simpler game than chess, but with a much larger number of possible choices for each move. Also a game lasts many more moves than in chess. The number of choices means that computers simply don't have the horsepower to analyze what will happen very far in advance, and the length of the game means that to play well, the computer has to anticipate things much farther ahead than they do in chess. So brute force doesn't go very far.

More precisely, looking ahead one more move does less good in Go than it does in chess, and it takes a heck of a lot more work. Assuming that things work in Go like they did in chess, and assuming that Moore's law continues to hold, computers will eventually trounce humans. But not for centuries to come. (And the physics of information theory tell us that Moore's law must halt before that day.)

So the problem is that we have never figured out how to have a computer "understand" games using anything other than very unsophisticated models. Which is why computers are not very good at Go. So if you want to do what dragonchild wants to do, what you need to do is learn all of the theory. Learn how to write games. It is all important because the last 5% of how humans play games uses all of that stuff. But then you need to find a creative way to do something completely different than that to fill in the missing 95%, because we know that our current approaches are useless for playing Go.

Replies are listed 'Best First'.
Re: Re (tilly) 3: OO vs. global variables...
by dragonchild (Archbishop) on Sep 04, 2001 at 22:59 UTC
    I know all of this, tilly. In fact, I think we've discussed part of this before (but I'm too lazy to go look up the node, assuming it wasn't by /msg).

    What I'm doing is exploring to see if I can get a program to learn about shapes and pressure, then make decisions based on that. Part of the problem that the standard alpha-beta algorithms have had is that they used static board evaluations - evaluations of this position without any concept of where this position may or may not go. I want to try and use a more dynamic evaluation.

    And, yes, I know this is exponentially more difficult to program than static evaluations. *grins* Therein lies the challenge, neh? :)

    Once I get going into it and have my theory actually start to make some real moves, I'll probably throw a Meditation up there on the concepts I'm using and see what happens when people who actually have working braincells bang on it. Till then, I'm gonna be sorta mum.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Vote paco for President!

(pmas) 1: OO vs. global variables...
by pmas (Hermit) on Sep 05, 2001 at 00:05 UTC
    Don Green from Yale designed new game OCTI with special goal to be intuitive for humans and hard for computers. It is really simple, fast to play, see www.octi.net. There was even OCTI-bout tournament recently...

    Just Another Strategy AI Game...;-)

    pmas
    To make errors is human. But to make million errors per second, you need a computer.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://110121]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2024-03-29 06:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found