dragonchild has asked for the wisdom of the Perl Monks concerning the following question:

Having harped on the evils of global variables for the length of time I've been a part of PM, I now find myself in the embarassing situation of thinking I actually need a global variable.

The situation: I'm writing a program that will play the game of Othello. (This is a precursor to playing the game of Go.) I want to write this as a OO program, both because I think it's the right way to do it and because I want practice in writing as true an OO-program as I can.

The issue: The size of the board is playing a part in a huge number of calculations, spread across all the objects. (For example, the AI object wants to know the bounds of the board. The Point object wants to know if its on the edge of the board or not. And, so on.)

Discussion: Now, one thing I'm gagging on (and this may just be unfamiliarity with the process) is should every object have a pointer to the Board? I mean, should the Point know who its Board is, so to speak?

Possible OO solutions: Maybe, have the Board give the AI a list of open squares? Maybe, have the Board tell the point, when it makes it, what sides of the Board it's on? Is this the way OO works??

We are the carpenters and bricklayers of the Information Age.

Vote paco for President!

Replies are listed 'Best First'.
Re: OO vs. global variables...
by Masem (Monsignor) on Sep 04, 2001 at 21:50 UTC
    I think what seems tricky is how a Point is going to know it's an edge point in a typical OO fashion, as you're finding out, you're trying to make objects work uphill as well as down. This typically doesn't work well.

    There's three possible solutions that I can think of, two requiring massive code changes in Board and other parts of the code, and one that requires Point to be changed. Let me do that one first:

    If this were C++, I would say one possible solution is to use templates (Pardon any syntax, I know what I mean, but haven't written C++ in years :-), and I just want to show the idea here...)

    template <int H, int V> class SpecificBoard extends Board { Point<H,V>** array; new() { array = new Point<H,V>[H][V]; /* then set i,j on each... */ } ... } template <int H, int V> class Point { int i,j; new(x,y) { i = x; j = y } ... } Board* board = new SpecificBoard<10,10>;
    What comes about here is that implicitely, you've passed the board size to the point class (which is specific to the board size), so the point doesn't know what Board it is part of, but can work out edge information from this. Can this be done in Perl? Sure, at the cost of two extra int's per point. It's not as 'invisible' as the C++ template method, but then allows you to check edge states without having a Board object to worry about.

    A second way would be to avoid having points know how to check for edges, and instead have those functions built into the Board class. It makes, from an object pov, more sense to have it this way, though from your description, it sounds like you'd have to modify code throughout to make this work.

    Finally, you could create a small BoardInfo class that only contains just enough info about the board itself (size, for example) that could be passed around to other objects without passing the entire Board object. The Board object itself could hold on to one copy of this to replace it's own versions of size and other details. But again, this is sort of getting away from a good OOP solution, since Points would need to know the BoardInfo to determine if they are edge points.

    (A fourth solution, icky but doable, is to create subclasses of points, MiddlePoint, EdgePoint, and CornerPoint, that would be determined by the Board object at creation time, and would immediately know what their state is. But that seems like lots of extra classes...)

    IMO, 2 is the *best* way to go, but 1 is the most adaptable if you are already though hours of coding.

    Dr. Michael K. Neylon - || "You've left the lens cap of your mind on again, Pinky" - The Brain
    It's not what you know, but knowing how to find it if you don't know that's important

      I know that this is not a C++ forum; however, it is a programming one and learning one language helps with all others...

      This is a completely incorrect use of templates. Templates take only a class (not an instance of a class), thus you would get <int, int> rather than <8,8>. What you want here is a constructor that takes two int's (or scalars) as arguments, and builds the class based on this input.

      The solution that has point as a base class and three inherited classes, middle-point, edge-point, and corner-point, is what fits best into an OO design pattern. Because the whole purpose of OOP is to have each class only worry about itself. However, you might consider making a line class to determine captures since captures are really line oriented...

        I know the original specification of C++ only allows class names as template parameters, but recent C++ developes allow a larger body of parameters to templates (see (first reasonable link I could find) here for example) -- this type of specification is commonly used to demonstrate how one can do fibonaci calculations all at compile time, rather than run time. Mind you, all these have to be specified at compile time, so that my method would not work with a board that could be dynamically allocated. But from a naming classification, you're talking about the slight difference between a Point-on-an-X-by-Y board, and a Point that knows it's on an X-by-Y board. Minor here, but could be significant in other cases.

        Dr. Michael K. Neylon - || "You've left the lens cap of your mind on again, Pinky" - The Brain
        It's not what you know, but knowing how to find it if you don't know that's important

Re: OO vs. global variables...
by John M. Dlugosz (Monsignor) on Sep 04, 2001 at 21:25 UTC
    Will you have more than one board?

    I think yes, because in the implementation I'm familiar with, the board state is thought-ahead as it forms the minmax tree. Each point in the thinking-ahead points to its own "what if" board. So yes, everything in the code needs to be told which board to use. Board means "current entire state of the game".

    Can you use constant board_size=>8; ? Sure, that's not a problem and the global police won't get after you. But it won't really be global, it will be in the package used for the board object. It's a class invariant, not a "global", right?

    Possible solution:

    Standard implementation of minmax tree. Generate a tree for every possible move, several moves deep. On odd levels you want the MIN result (bad for the player), on even levels (computer's play) you want the MAX result. If you can see all the way to the end of the game you know the result is infinite if it results in a win for that player. But you generally can't, so you make things much more complex by guessing if the board looks like its in a favorible state. Sort each row as you go, because you quit digging when you beat what you already have.

    The book I learned this from is this one. —John

(dws)Re: OO vs. global variables...
by dws (Chancellor) on Sep 04, 2001 at 22:05 UTC
    Now, one thing I'm gagging on (and this may just be unfamiliarity with the process) is should every object have a pointer to the Board? I mean, should the Point know who its Board is, so to speak?

    Yes. A Point needs to know who its Board is so that it can delegate certain questions/actions to its Board.

    Having a contained object delegate questions about "location" and "neighbors" to its container is a frequent pattern in OO-land. It usually leads to smaller (and more flexible) class definitions for the contained objects.

    Try approaching the problem by way of the question "Which is a more appropriate place to implement this behavior: Board, or Cell?"

      So, in the Point class, you'd have a function that sorta looks like:
      package Point; # Stuff here... sub isNextTo { my $self = shift; my $newPoint = shift; return $self->{PARENT}->Point_isNextTo($self, $newPoint); } # Stuff here...
      I suppose that would make sense, as a Point should not know all about the intricacies of Board layout. For example, I can think of several games (Risk comes to mind) where two Points would be next to one another, but there is no algorithmic way of determining that. So, I suppose the Board should determine next-to-ness.

      *frowns* Does that mean that the Board should be able to dip into the Point's inner workings and get its X and Y coordinates? How would this work without using an accessor function?

      We are the carpenters and bricklayers of the Information Age.

      Vote paco for President!

        You've got the general idea. Board can answer any next-to-ness question for a given Point. Consider this alternative to your fragment:
        # determine if I am next to aPoint sub isNextTo { my $self = shift; my $aPoint = shift; my @neighbors = $self->{Board}->neighborsOf($self); return 0 != grep { $aPoint == $_ } @neighbors; }
        Does that mean that the Board should be able to dip into the Point's inner workings and get its X and Y coordinates?

        The word "Point" carries some baggage (but then so do some alternatives, like "Square"). Let's reframe the question by using "Cell".

        Why should a Cell know its X and Y coordinates? Clearly, somebody needs to know them, but why Cell and not Board? (You might have good reasons to go one way and not the other, but this is a good question to ask yourself before deciding.)

Re: OO vs. global variables...
by Johnny Golden (Scribe) on Sep 04, 2001 at 21:55 UTC
    i looked into this a while ago and got alot of useful information by super searching "GO". I was suprised at the amopunt of information there was. You are right in the fundamentals being the same between the two games, but Go is much more difficult. As you look into this, you will find out that Othello and Go have many more variables in them than chess! (Chess has about 16 possible moves at any given time, Go has about 500)Check out the existing threads and you should save yourself alot of headache! I would be really interested to see your results as there is not currently ( I believe) a program in existance that can consistantly beat a Go master. Othello is a good step towards that! I wish you luck!
      *grins* Why do you think I'm writing this program? I wanna be the first. It's a pity that the million-dollar bounty isn't offered anymore. (The guy died in '97.)

      I've done a lot of research into both games, having played Othello since I was a kid and having become very interested in Go about a year ago. (It's interesting - my chess playing skills improved after learning how to play Go ...)

      We are the carpenters and bricklayers of the Information Age.

      Vote paco for President!

        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.

Re: OO vs. global variables...
by jepri (Parson) on Sep 04, 2001 at 22:53 UTC
    Or you could use a singleton, which as I understand it is a way of doing objects so that any attempt to create a new object actually returns a refernce to the first (and only object) created. This way you can access the same object without having to hand refs around.

    In practise this isn't done much, because modules do the same thing with a lot less fuss. If you want global variables, just create a module with variables in it, and access the variables from your main program. This is one of the times you can really appreciate Perl letting you break the rules in a good way.

    I didn't believe in evil until I dated it.

      But note that there are good reasons to use singletons in Perl. The most common one for me is when the object is expensive to create (database connections etc) and might need to exist for many reasons, but might be possible to do without. In that case then you just use a singleton and issue calls to its constructor from wherever you need it.

      Now no matter how complex the logic is to need it, it is there when you want, and you don't pay for it when you don't need it.

(elbie): OO vs. global variables...
by elbie (Curate) on Sep 04, 2001 at 22:34 UTC

    Masem makes an excellent point. If you are going to have a lot of board related functions, it makes a lot of sense to have those functions be methods of a board object.

    Your AI particularly should be able to make a move based on the board's layout. So you can just give the AI routines the current board object. Any information the AI needs can be retrieved using $board->is_free( x, y ) or whatever methods you'd need.


Re: OO vs. global variables...
by arhuman (Vicar) on Sep 05, 2001 at 20:06 UTC
    Here's my contribution :
    • Will you need more than one board
      Not necessary, I remember I coded a (REALLY SIMPLE) chess engine using only one 'state' (to save memory), the 'trick' was to play and un-play move while navigating the tree.
    • Use Alpha-beta or even better sorted alpha-beta rather than simple min-max
      (you compute an alpha beta on 2*n half-moves sort the move based on this result and then launch a deeper alpha-beta on 2*(n+x) half-moves, the ordered moves will help you cut quicker in the tree)
    • Tilly is right (as usual). The key is in the theory for the crunching power won't be enough for a game like go.
      You should especially use it to craft well your evaluation function (the one which rates the 'states') for it is the heart of your engine...
    • A Good trick to optimize your settings (evaluation function for example) is to make your engine play against another engine with different (random ? GA produced ? partially hand crafted ?) settings , keep the best setting at each step and iterate...

    "Only Bad Coders Code Badly In Perl" (OBC2BIP)
Re: OO vs. global variables...
by dragonchild (Archbishop) on Sep 05, 2003 at 04:18 UTC
    This is really interesting - exactly 2 years later, I've dropped and reapproached the problem completely differently. This time, I actually have something working and (soon) postable to CPAN. Also, the design is much simpler and extensible. Wow ...

    We are the carpenters and bricklayers of the Information Age.

    The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6

    Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.