Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Re: Looking backwards to GO forwards

by gregor42 (Parson)
on Sep 06, 2001 at 18:24 UTC ( #110586=note: print w/replies, xml ) Need Help??


in reply to Re: Looking backwards to GO forwards
in thread Looking backwards to GO forwards

Let us chant our mantras...

Laziness is a virtue... If you have to do something more than once, automate it!

When a player cannot move, that means that a certain set of conditions have evolved. There should be recognizable patterns that can be detected. Otherwise, how would we as human thinking machines play the game.

What you say is true, so we are adding another layer of complexity to the problem. This will make the solution set larger and more difficult to define, since an iterative approach will be necessary to find every winning combination, containing every possible 'blocked' pattern.

Therein lies the inherent challenge in Go.

But also commenting on Johnny Golden's reply, these 'opinions' you mention might also be described as strategem. A way to capture this sort of hint-based event/decision driven system is generally described as an expert-driven system, wherein expert metholodolgy & rulesets are compiled for automatic response with some degree of subtlety.

Wait! This isn't a Parachute, this is a Backpack!

  • Comment on Re: Re: Looking backwards to GO forwards

Replies are listed 'Best First'.
Re (tilly) 3: Looking backwards to GO forwards
by tilly (Archbishop) on Sep 07, 2001 at 01:39 UTC
    The crux of the problem is that there is a huge disjunct between patterns that we can recognize and act on, and patterns that we can describe in sufficient detail to train a computer to act on.

    Bridging this gap is the main goal of AI research.

    As so-called expert systems demonstrate, it is possible in many cases to straightforwardly break down complex decisions into many simple ones. And so a computer program with a good rule-set can do routine diagnostics quite effectively.

    As chess-playing computers demonstrate, it is possible in many cases to give the computer very little general knowledge, but have them at each step work out from first principles how things will happen.

    The problem is that Go has enough states to be infeasible to work much out from first principles. You are talking about how large the solution set is. Unfortunately the solution set is already far too large for us to calculate it statically once, or to calculate on the fly enough of the local decision tree to recognize what a human would see on general principles.

    It isn't a question of just doing it intelligently. It is a question of being able to do it at all.

    At a guess the problem shares a lot problems we deal with in voice recognition. The raw signal comes in a form that is essentially useless to the task at hand. The rules that people actually use are done at a level which they cannot even think about conciously. What can we do?

    Well we can search for a transformation of the raw signal into alternate signals in which patterns are easier to state. For instance patterns in speech tend to involve features that are localized in both space and frequency. So we search for some way of describing that signal in terms of components that are themselves localized in both space and frequency. And we find that wavelets do that. Using wavelets, our signal is massively clearer. Still a mess, but oh well.

    We then improved that by finding ways to make wavelet transforms dynamically choose the trade-off between localizing in space and time. We chose the one with the minimum entropy, meaning the shortest internal description. What did that do? Well it made the wavelet transform naturally break on the phoenemes of speech. And gave each one a recognizable "signature" we could work with. And now we had something to work with.

    Something similar is true with games. Humans don't just sit down and learn a bunch of rules. Humans engage in the twin activities of learning how to recognize patterns, and learning how to react to them.

    A good player of the board game of your choice does not merely know more rules about that board, they actually see a different board. For instance consider the task of memorizing a chessboard. If you take good chess players and poor chess players, and hand them a board with pieces randomly arranged, they perform about equally. If you take both and put down random positions from middle-games of real tournament games, the good chess players are substantially faster and more accurate at memorizing the board.

    Why? Well when I heard about this, we didn't know for sure. But here is my best guess, that the good chess player has developed an internal model of pieces on a board that allows them to describe the board efficiently. (The efficiency of our internal descriptions is highly significant in memorization tasks. For instance native Welsh speakers can memorize more numbers if asked to do it in English than if they are asked in Welsh. That is because the same number said in Welsh has more syllables.) How efficiently? Well components are obvious because they are features you learn to analyze. Others because they are features which are characteristic of the opening.

    Therefore I would guess that there will turn out to be a deep connection between having a computer that can play Go well, and the task of describing positions which arise in real Go games efficiently...

      That connection between playing Go well and being able to describe positions that arise is the precise section I am going to be working on.

      I have this concept of Shapes. One thing I noticed when playing Chess, Othello, and learning Go, is that there's this concept of pressure in space and time. I'll use Chess as an example, as it's the game I know how to describe best.

      If you're executing an attack on the King's Side, then what you are doing is attempting to have more officers able to reach the opponent's KS than your opponent can muster in defence. This is pressure in space - you have cut off places your opponent can safely move to. This is also pressure in time, in that your opponent needs more moves to successfully defend than you need to successfully attack.

      All pressures can be graphed. The trick to graphing is to find meaningful axes and to assign meaningful values to the observed phenomena. Anything that can be graphed has a shape (and, potentially, an equation).

      So, what I want to do is to start observing how these shapes interact with one another. What properties do these shapes have? Go is actually easier to do this with than Chess because the game naturally lends itself to this concept, due to its grouping nature. The shapes (initially) will be the actual groups of pieces. In Chess, these shapes are based on what the pieces will do, not on the pieces themselves.

      I think that this is much closer to the way humans think about strategy games than static board analysis. I know that when I think about a move in Chess (or Go), I'm not thinking about the board position that will arise so much as about the pressures I will be placing on my opponent. I'm thinkin about keeping to the fundamentals and making solid moves. Why are they solid moves? Because they apply more pressure to the opponent. Your army is a weapon - as sharp or blunt as you want to make it. If you have sufficiently more men, a blunt attack is fine, otherwise a sharp attack is demanded.

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

      Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Re: Re: Re: Looking backwards to GO forwards
by dragonchild (Archbishop) on Sep 06, 2001 at 18:36 UTC
    It's not a matter of when a player cannot move ... it's when a player should not move. Your list of "winning" positions is calculable in theory, but not in practice. My initial reaction is that you would have to go forwards to find the positions, then go backwards.

    One of the bigger issues that that Go, unlike Chess, has a number of identical positions. Not just considering the fact that the board is rotateable (which quadruples the number of "winning positions"), but that you could swap the NE and SW corners and have the same "winning position". Or, rotate a subsection of the board.

    The rules and starting position of Chess dictate that a huge majority of the potential board arrangements can never be reached, which is why it's a much simpler game.

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

    Vote paco for President!

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (8)
As of 2020-12-04 08:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    How often do you use taint mode?





    Results (58 votes). Check out past polls.

    Notices?