One of the problems that comes up, sooner or later, in an OOP (Object-Oriented Programming) based programming course, is creating a set of classes for a “realistic” problem. One key thing to do is think about what a class is. It is a description of a type of object in terms of its properties and abilities. For example a Cat has several properties: number of legs, color of fur, weight, length, whether it's declawed, etc. It also has abilities: meow(), walk(), run(), jump(), purr(). The combination of those properties and abilities create the Cat class.
With all that in mind, we always start a course with the Hello World program, which is completely non-OOP, even in Java (which claims to be pure OOP). Then we eventually move up to a tic-tac-toe program. Ahhhh, the excitement of creating a board that is a 3x3 array of integers (that's a property)! The thrill of checking in 8 different directions for a win (the ability haveWinner())! WE HAVE CREATED A GAME!!!! Now we'll move on to go.
Err... what was that? You haven't heard of go? How about as baduk? Igo? Weiqi? Right, it's a game that is about 4000 years old that was invented in China. It's one of the national past-times of Japan, and is also very popular in Korea (along with StarCraft, but that's for another time). The rules are simpler than those of chess, yet the best go AI is still ranked as an amateur. The fact that go programs still kick my butt must mean I really suck! So, once we know the rules, we can get started.
Actually, that might be a bit of a problem. You see, the game is 4000 years old, so for over 3000 years, the rules were handed down orally. We have historical evidence that the board size has changed over time, and even now there are two different (but basically equivalent) ways of keeping score. Even today, there are some people who are working hard to fine-tune the rules into an optimal set.
Useful rules can be found at Sensei's Library: Rules of Go - introductory (Go read it now. The following text is a paraphrase of the rules found there, but without the helpful illustrations that will make it make more sense.):
Some other rule sets of interest are:
AGA Rules/Intro (American Go Association Rules with balanced scoring)- Rules of Go
Ing Rules (Very complicated international rule set) - http://www.usgo.org/resources/downlo...gRules2006.pdf
Tromp-Taylor Rules (the “logical rules of go”, very programmer friendly)- John's Go Page
OK, got all that? Now all we need to do is create a bunch of classes to store that information. First we need a list of potential classes. The way we'll get that list of potential classes is to list EVERY noun mentioned in the rules. After that's been done, we'll review which ones are classes and which are properties of classes. The potential classes are:1) There are two players, one is black, the other white.
2) The game is played on a grid of lines. 9x9 or 13x13 for beginners or quick games, 19x19 in tournaments/full games.
3) The intersections of the lines are called points. On a 9x9 board, that means there are 81 points. A 19x19 board has 361 points.
4) Black plays with black stones, and white plays using white stones. Stones are placed on empty points (points without a stone already on them).
5) On a turn, a player places one stone of his/her color on an empty point. Alternatively, a player may choose to pass. Placing a move may result in capture (see rule 7).
6) At the start of the game, the board is empty and it is Black's turn to play. Players alternate turns. If one player is more skilled than the other, White may pass one or more times to provide Black with a handicap.
7) Stones are considered adjacent to each other if they are next to each other horizontally or vertically (diagonals mean nothing in this game). If two stones of the same color are adjacent to each other, they form a group. If that group is adjacent to a third stone, all three are part of the group, etc. If a stone is played that fills in the last adjacent empty space around a group, the group is captured (removed from the board). The empty adjacent spaces are called liberties.
8) A player is not allowed to make a play that will NOT capture an enemy group of stones and also results in forming a group of the player's own color with no liberties (empty adjacent spaces). (This is referred to as suicide.)
9) A situation could arise where players could end up alternating back and forth in the same position forever (ko). To prevent this stalemate: you may not play a move which results in the repeat of a previous board position.
10) A player may pass (not place a stone) instead of taking the regular move. When both players pass in succession, the game ends.
11) Each player may claim a point for his/her score if it is either occupied by one of the player's stones or surrounded by the player's stones. The player who occupies or surrounds more points wins. (This is called Chinese scoring. Japanese scoring counts the number of surrounded points and the number of captured stones, but not occupied points. In reality, it makes almost no difference in scoring. I am partial to Chinese scoring, but most go sets sold in the US include rules for Japanese scoring. Chinese scoring is easier on new players because they aren't punished for placing extra pieces.) Generally, pieces that have no chance of survival are simply removed from the board (captured) rather than force the players to play out the tedious death sequence. If there is a disagreement as to whether some pieces are dead, simply play it out.
1) a go game class
2) a player class
3) a board class
4) a point class
5) a stone class
6) a turn class
7) a group class
8) a liberty class
9) a history class
10) a score class
OK, so which of these are really classes? Based on a little thinking, a stone or liberty isn't really an object as much as a property of a point or a group. Similarly, a score is a property of a player and a turn is a property of the history or the game. That trims us down to:
1) a player class
2) a board class
3) a point class
4) a group class
5) a history class
6) a go game class if we have something pure OOP (like Java)
So, let's look at these one by one:
Player: has a score (use float for certain rule sets), a handicap (integer value), and a color (black or white). If we get really fancy, we may update the score regularly with estimated scores, but from a practical standpoint, we ignore it except at the end of the game.
Board: has two 2-dimensional arrays of points (see below). It also has a history (see below) and an array of groups (see below). The idea is that for each move, you determine what the board position WOULD result in, then replay the game to check for a matching historical move. A conflict results in the current state being reconstructed from the history and the move is rejected.
Point: has one of three values: empty, black, white. It also is a group membership (if black or white) and a scoring value (none, black, or white).
Group: has a group identifier (integer) and number of liberties (integer). Every move has the potential to result in groups merging or being removed, so this needs to be updated carefully, along with the point memberships.
History: has an array of previous moves (pair of integers). This is pretty boring, though actual Go programs do a lot of hypothetical moves as part of their history for teaching purposes. We could make this all fancy later.
Go Game: contains 2 players and a board.
Here's what we have, then:
A board class with a 19x19 array of points (not necessarily all used) and a history class and an array of groups (or linked list, or whatever container makes you happy). The board class has to be able to accept a desired move and validate it, update its properties, and return whether the move was valid or not. It must also be able to calculate the scores for black and white and return them. It also needs a way to mark dead stones for scoring and resume the game if there is a disagreement.
A point is simple, it has a color, group membership, and scoring contributor. These are all managed by the board.
A history is just a list of moves that have been made. It is managed by the board.
A group has an identifier (shared by points in it) and a count of liberties. It is managed by the board.
A player has a color, handicap, and score (requested from the board).
You will, of course, need something to manage the board and players. This can be done with either an overall game class, a main function, or something similar. The details will depend on the language. Don't make a game class if it's not required by the language. It's a waste of time and just adds a layer of extra garbage you didn't need.
You may look at these classes and think they're too simple. That's a good thing! If you add nonsense that isn't necessary, you've added more ways for your program to fail. Add things only when they are REQUIRED for functionality. If you want to know how a cat works in real life, take a biology class. If you want a cat in your program, just give what you need to convince the user you have a cat.
Another thing you may have used is that I haven't mentioned accessor functions much. There's a reason for this: they are frequently stupid and just make your code harder to understand and slower to execute. Don't misunderstand, I use accessor functions, but only when there is a need to validate new values for a property or when changing one property's value forces another property's value to change as well. As with all things: keep your class as simple as possible.
Excellent tutorial. One quibble - the title of the tutorial should be "how to design a set of classes for my project", instead of a question. As it stands, the title makes the thread look like you are asking a question, as opposed to answering one.
Good suggestion... implemented.
Oh, and, um - I don't particularly like the period at the end of the title.
Sure, I slave away trying to make this tutorial perfect, and you're just not happy!
I didn't even read it.
I wouldn't doubt that. Excellent read, thank you for posting. +rep
I read a chapter in a PHP book dedicated to making "The Game of War" which was very similar to this tutorial. Each "point" could contain multiple types of objects (such as a tank, riflemen, etc) and it was based on abstract classes which made them interchangeable. More than one object in a class resulted in a group that could be added to or split. I can't, for the life of me, remember what the design pattern was called though. I believe this is the same as your group membership.
Have you created any code for this, or just working through thought?
I've got some UML diagrams lying around for this. Chess is a nice example of being able to have an abstract piece class along with a concrete child classes that implement the behavior of the various pieces.
An interesting mental exercise is to look at a game like StarCraft and think about the various objects in the game in terms of classes, properties, methods, parent/child classes, etc.
There are currently 1 users browsing this thread. (0 members and 1 guests)
Posting Permissions
LinkBack URL
About LinkBacks
Reply With Quote
Originally Posted by Jordan
Bookmarks