Game Of "GO" Editor - Role of Up-Front Design in XP
Vladimir Levin
a simple game editor (not AI player) may server as a good point of
discussion to clarify the role of up-front design in XP.
The basic rules of Go are simple:
You have a board consisting of a grid with pieces placed on the
intersections of the grid. The grid is usually 19x19, but there are
variations with 9x9 and 13x13 boards. In any case, the rules are
pretty much the same. The players alternate placing pieces (black and
white respectively) on the board. You can capture your opponents piece
by covering the points adjacent to it with your own pieces. So to
capture a single piece, you would place 4 pieces on the board, above,
below, and to the left and right of the opponent's piece.
. . . # . . .
. . # O # . .
. . . x . . .
Black (#) removes the white piece (O) with move 'x'
You can form groups of pieces that live and die together, e.g.
. . . # # . . .
. . # O O # . .
. . . # x . . .
Black removes white group with move 'x'
If a group has one inner space, which is called an eye, then it has to
be covered last, e.g.
. . . # # # . .
. . # O O O # .
. . # O x O # .
. . . # O O # .
. . . . # # . .
Black can remove the white group with move 'x'
Finally, a group with two "eyes" cannot be removed, since both spaces
have to be covered last. There is also a situation called a 'ko' where
you have to place a piece somewhere else to prevent an infinite loop:
. . . . . . . .
. . . # O . . .
. . # y x O . .
. . . # O . . .
. . . . . . . .
Assuming black captured a white piece at 'y' in the last move at 'x',
white cannot take the black piece back with 'y' immediately.
I think the description above is a reasonable starting point to write
an editor using XP. I don't think it's so important to know how a game
ends or how it is scored just yet. So, how would one go about writing
a Go editor on the basis of these rules using XP?
Would one figure out one's basic approach for how to store groups, how
to merge several groups into one, and how to figure out when a group
has been captured first? Even using XP and TDD, I would be inclined to
say 'yes', let's come up with a basic plan of attack, an algorithm for
these things, then implement that plan using TDD. Of course, the plan
can change as the code develops. If it is ok to make this initial
plan, I think that deals with many objections to XP from people who
believe that XP mean you have to start writing unit-test backed code
right away.
Looking forward to comments.
Vlad
Laurent Bossavit
Have you been lurking on the French-language XP mailing list ? We
discussed that as an example domain, inquiring into almost the same
questions, in fairly recent times.
> I think the description above is a reasonable starting point to write
> an editor using XP.
A good question to ask at this point is, should this be considered a
sufficient amount of domain analysis ? (Refer to the comp.object thread
"agile/xp question".)
> Would one figure out one's basic approach for how to store groups, how
> to merge several groups into one, and how to figure out when a group
> has been captured first?
I think I would want to know what you mean by "figure out".
Certainly there are things that would need to be decided - though
reversibly so - before you could begin implementation in XP; such as
what representation to use for test cases.
Even before that, you would have to think about what a Go game editor is
good /for/. Who's the user, and what's the problem we are solving for
that user ?
I'm not asking the question rethorically, by the way - I'm interested in
pursuing "analysis" of writing a Go editor in XPish manner.
It may well be premature to think about storing, merging or capturing
until we have answers to the above, that align with what we already know
of the domain. (And we may have to rethink our first cut domain analysis
in the light of what the user/customer says.)
Once we know what problem we are solving, we can pick a dead-simple
scenario that demonstrably solves part of the problem, then agree on a
test case representation to express the demonstration in. ("Yes, if you
show me a Go editor that can work through these steps, I'll concede that
you're going in the right direction.")
That dead-simple scenario will already have started to constrain,
perhaps to decimate, the range of conceivable implementation decisions
we were facing above. At the least we will start to have a feel for the
forces in play. This may well start to elicit implementation-flavored
thoughts.
We might want to put these thoughts aside as we get down to work on the
first few unit tests, because we can then get a feel for what
shortcomings an "unthinkingly naive" solution might present. We're not
really working out an "unthinkingly naive" design, of course - we're
only pretending to. Sophisticated naïveté, if you will.
Sooner or later, we're going to get around to feature requests that call
for a more definite choice of storage structure or algorithms. By then,
if we have gauged correctly the forces affecting the design, the code
will be nimble enough to "hide" most such choices from all but a few key
modules.
What I think I would do, in the meantime, is read voraciously on as many
aspects of Go as I could collect from the Web or Amazon.com. I'd be
looking to play Go with teammates at coffee breaks, reading a book on
the metro home, and while idle for other reasons Googling like mad for
Go implementations, preferably but not exclusively open source, looking
at how the AI is "supposed" to be done, and so on. Not to imitate, but
to get an idea of the possibilities.
What I would be trying to gain in all this is an ability to see more
than one move ahead. By this I mean, not just being able to /propose/
one design for storage, mergers, captures; but being able to guess
astutely the consequences, good and bad, of several competing designs.
"If I write /this/ unit test next, then the next problem to solve in
sequence would have to be this one, but..."
One advantage of doing this kind of work within a team is that I might
well have colleagues with different personal inclinations, focusing on
different design strategies (for instance, actually working out one
design for storage or captures, perhaps as a spike, or just to solidify
their own understanding). Diversity would improve our chances with such
a project. With mutual respect, and agreement on a few ground rules of
behaviour, diversity could turn out to be a rose without a thorn.
Stede Troisi
You bring up a great concept: An example.
Maybe you will find like me, after studying all the books, talking to all
the experts (including their supreme leader Ron Jeffries) that XP is very,
very vague on specific. Why you might ask?
First, I think there is this problem called building software. First it was
simple. Sort of like designing a new apartment. You may or may not have an
specific solution at hand but you begin somewhere. You get immediate
feedback, change this, add that and bang; sooner or later you have something
that you internally can judge as either being successful or not. Things get
horribly more complicated when you must figure out what someone else wants.
Especially when that person often doesn't know what they want or could be
completely wrong.
XP seems to revolve around this core idea that this problem can't be solved;
at least not easily. So XP seems to split off into two distinct areas,
Project Leadership (user stories, customer acceptance tests, pair
programming, etc., etc.) and Software Design (TDD, Refactoring, etc., etc.)
The larger part of XP in my opinion is Project Leadership which deals with
figuring out what the user/customer wants and getting it to the customer as
quickly as possible before he runs off to India to hire real programmers.
The more interesting part (in my opinion) is the Software Design. Should you
design up-front? Should you physically write or at least design for changes
you almost know you will need? Is there a better, more flexible way of doing
A over doing B? It seems to like you are interested in the Software Design
which, ironically, I feel has the most to give to the body of knowledge
known as Computer Science.
Sadly, all you are going to get in XP are "what is the sound of one hand
clapping" answers because XP really has no answers. Most people looking into
XP are either programmer/managers or consultants who need answers to Project
Leadership puzzle.
I feel we should develop clear examples in different domains with concrete
examples like you mentioned. How about me and you and anyone else who would
like to join build examples like these in the languages of our choices. Then
we can compare each of our code from a larger height and see if some design
decision are truely better than others?
Stede
"Vladimir Levin" <vladimi...@yahoo.ca> wrote in message
news:88f5a83.04111...@posting.google.com...
Ilja Preuß
> Sadly, all you are going to get in XP are "what is the sound of one
> hand clapping" answers because XP really has no answers.
What about Metaphor, Simple Design, Test Driven Development, Refactoring,
Pair Programming?
Which other process goes as much into detail how you do your daily design
job?
Puzzled, Ilja
PS: You should read Robert Martin's "Agile Software Development -
Principles, Patterns and Practices". This book is solely about how to create
good, flexible designs incrementally. And it is heavily influenced by XP.
sted...@yahoo.com
Refactoring,
> Pair Programming?
> Which other process goes as much into detail how you do your daily
design
> job?
> Puzzled, Ilja
Yes, you are. "Make software simple" sadly isn't detailed enough for
all projects. Just look at the more *detailed* questions posted by
programmers on this board.
How do you hook the GUI up to the business Logic?
What design pattern work best in certain situations?
Are singletons bad?
What is the best way to Test A, B, and C?
Should we Test Private members?
The list goes on. Obviously *Simple Design" needs a little more
clarification. The best example of what I consider great detailed
clarrification is "Adventures in C#" by Ron Jeffries. When Ron gets off
his priest soap box and into the typewriter his examples are simply
incredible. Sadly, the projects he undertakes in the book are so trival
(no database access, rich gui, complex functionality) that you are left
wanting more.
Stede
Laurent Bossavit
> Sadly, the projects he undertakes in the book are so trival (no
> database access, rich gui, complex functionality) that you are left
> wanting more.
Well, the Go editor thread could be that. Or it could be another one of
those that run in unproductive directions.
Up to us, I suppose.
Laurent
sted...@yahoo.com
I am ready when you are!
By the way, what does it mean by editor? Does this mean you play and
the computer determines if the moves are valid?
Stede
Laurent Bossavit
> By the way, what does it mean by editor? Does this mean you play and
> the computer determines if the moves are valid?
I assume not, but what "editor" means is precisely the question I have
suggested Vladimir might want to answer, rather than launch into what I
think is a premature investigation of design and algorithms.
Please refer back to the first (longish) answer I wrote in answer to
Vladimir's original post, where I outline the strategy I would adopt.
Laurent
Christophe Thibaut
May I chime in ?
I think as soon as some users stories and acceptance tests can be
settled, I'll be happy to run into a TDD frenzy about that very subject:
a Go "editor".
I'm learning Go currently, but quite slowy because I don't play enough
games and the printed material is still hard for me to evaluate on my
"goban". Long ago when reading about chess openings I used to have 3 or
4 chessboards in front of me in order to better visualize alternatives.
I didn't have a software like Fritz(tm) at the time (nor a computer of
mine btw).
What I'd like is a system with which I can enter a game, enter
alternative moves, navigate through the complete tree of all the
branches thus created, and visualize the game a any point of this tree
through a different window. An MDI go editor of some sort.
Does it sound interesting ? Or is it still just another piece of trivia
which wouldn't teach us anything about software design, TDD, or Go ?
Just for the fun of discovering TDD, I once wrote some code that can
check for living groups and remove dead stones. Quite easy, as long as
you don't enter in the "and what if this program could evaluate your
current position ?" zone. Go rules are very simple. Go game is very complex.
Cheers,
--ct
>
> Laurent
Ilja Preuß
>> What about Metaphor, Simple Design, Test Driven Development,
>> Refactoring, Pair Programming?
>
>> Which other process goes as much into detail how you do your daily
>> design job?
>
>> Puzzled, Ilja
>
> Yes, you are. "Make software simple" sadly isn't detailed enough for
> all projects.
Well, Simple Design has a definition in XP:
- runs all the tests (and therefore is testable)
- communicates intend (pair programming helps testing for that)
- doesn't contain duplication
- and, under those constrains, contains the minimal amount of code
Of course that doesn't suffice. But it's certainly more concrete than any
other process I know.
Cheers, Ilja
Stede Troisi
Stede
"Christophe Thibaut" <cthi...@club-internet.fr> wrote in message
news:419A7C32...@club-internet.fr...
Stede Troisi
"Ilja Preuß" <i...@iljapreuss.de> wrote in message:
> Of course that doesn't suffice. But it's certainly more concrete than any
> other process I know.
>
> Cheers, Ilja
>
Exactly. It doesn't suffice. And just because aother processes are not any
better doesn't mean we can't try to be? right?
Stede
Vladimir Levin
> Even before that, you would have to think about what a Go game editor is
> good /for/. Who's the user, and what's the problem we are solving for
> that user ?
Since I already knew the rules, I felt my initial description sufficed
to get started. Below you will find some further description of how
the game works. As for the user and the nominal purpose of the
exercise, there are many possible options. Here are two that I think
may be worthwhile:
1) A basic editor: This program displays a board. Two players
alternate by clicking on the board to place their pieces
(from now on I will refer to the pieces as "stones" in
accordance with standard Go terminology). The black player
always starts first. When a group is captured, the editor
automatically removes it from the board, and keeps track of
the stones captured by each player. The editor knows about the
"Ko" rule, so it prevents players from recapturing stones in a
Ko ad-infinitum. Note: It is very unusual, but there are some
scenarios where multiple instances of Ko can exist on the board at
the same time. I can't recall the rule for this, but I'd be
inclined leave it as a low priority item for later investigation.
When the game is over, the editor calculates the score. By the way,
the game is over when one player passes, then the other player
passes, then the first player passes a second time. Also, there
are several ways of calculating the score. For the most part
they work out to the same result, although there are some
subtleties. I would suggest implementing the Japanese scoring
system with the possibility of adding others later. A few final
notes: Go has a notion of "handicaps." If I am a better player,
I can allow you to place between 2 and 9 of your black stones
on the board in a pre-defined pattern before we start, then I make
the first actual move. Also, there is a concept known as Komi.
This is a point advantage given to the white player to prevent
a tie and to compensate for the advantage the black player has
in moving first. The minimum komi is 0.5 to prevent a tie. The
usual komi seems to be about 5.5 or 6.5 for an even game (more
research can be done here). Anyway, presumably the players could
change the Komi from a default at the start of a game.
2) To make this a bit more interesting, we might want to extend
this as an Internet service. Now, there are already some high
quality Go servers out there, so it's probably not worthwhile
replicating their efforts, although that might still be an
interesting academic exercise. I'm not sure whether there is a
service for "correspondance" play so that might be something
interesting to do. This idea would entail building a Web site
where players can sign up and start games. The games are not
intended to be interactive. Instead, you retrieve the game(s) in
progress when you log into the Web site, and make your move. A
link is e-mailed to your opponent. At her convenience, she logs in,
and plays her move and you receive your notification e-mail with
the link to the game. And so on. This would be for people who
enjoy playing at a slow pace, perhaps just making a few moves per
week. It can also be used as an educational tool, whereby you
receive feedback about your move from an instructor, followed
by a full game review at the end of the game.
As I mentioned in item 2, there is always the possibility of writing a
a full-fledged interactive, multi-player game server. See IGS
(Internet Go Server) for one of the most popular examples. Also, there
is the question of the AI. Writing an AI for Go seems to be harder
than writing one for Chess. Go AIs are making progress, but any decent
amateur can beat them, especially after having a chance to play
against them a few times. This is unlike Chess. I'd say that writing
an AI presents much more of an algorithmic challenge, since it is not
a well understood area. So I would not consider it to be a good
candidate for a software engineering exercise. It would fall more into
the realm of algorithm development and pure research. I would consider
this message, together with any readily available pamphlet/url on the
rules of Go, to be a sufficient point of departure to write some story
cards and to start planning a first iteration of development...
Comments?
Ronald E Jeffries
wrote:
The rules aren't constructive, in the sense that they don't tell you
what to do next. However, when you work with them, you discover
answers to the questions you asked and others like them.
>>
>>Well, Simple Design has a definition in XP:
>>
>>- runs all the tests (and therefore is testable)
>>- communicates intend (pair programming helps testing for that)
>>- doesn't contain duplication
>>- and, under those constrains, contains the minimal amount of code
>How do you hook the GUI up to the business Logic?
At first, we might put logic in the GUI. That violates the
communication rule, because we have two ideas (GUI and logic) in one
class. Therefore ... we create a new class for the logic and have the
GUI use it. Patterns used, if we are into that sort of thing, are
Extract Class, and Extract Method, among others.
>What design pattern work best in certain situations?
Mostly a separate topic, but the way to learn the answer is to use the
patterns. Reading about them helps but only somewhat. Knowledge of
patterns, as I see it, is the resource upon which we draw when we go
to make the next test work, or to make the code look more like the
Simple Design rules would suggest.
But I am continually surprised by how good the code gets with just
focus on those rules alone.
>Are singletons bad?
Not always. In fact, in small programs, hardly ever. On the other
hand, I find that I rarely use the Singleton pattern directly: I might
fairly often wind up just having one of some kind of object, without
ever enforcing it.
When they are bad, you'll notice it because you'll find yourself
wanting to have two singletons. So you do.
>What is the best way to Test A, B, and C?
It depends on you. I make different kinds of mistakes than you do, and
CTips presumably makes fewer and a different kind still. Therefore we
surely need to test differently.
So while I am happy to display my practices, as in the Adventures
book, the real purpose is to invite the reader to read, think, and try
the ideas in his own universe.
>Should we Test Private members?
We should test any code that should possibly break. Therefore, all
private members need to be sufficiently tested: but what's the
definition of "sufficient"? Hah, trick question. It doesn't have a
definition, it is a matter of judgment. It's "well known" that
complete testing of any complex program is impossible, We have to
balance our confidence in the program and the time we put into
testing. That's not something that can be learned by reading, in my
opinion, but only by doing and paying attention.
To digress in a direction that feels important ...
If we're doing TDD, sufficient testing /tends/ to just happen, but in
my case I sometimes break discipline when something seems to hard to
test or when I'm impatient to put in some cool code. On the assumption
that this might happen to others, I always recommend a second level of
Acceptance tests, and of course as much manual testing as may be
desirable.
The Adventures example, in addition to all its other flaws,
was hard to test at the Acceptance level using automated tests. These
tests got beefed up from time to time as problems occurred. But there
are at least a few places in the book where all the tests ran fine,
and where I finally found a problem only upon manual testing. Yet I
still tended to defer manual testing because it was a pain and took me
off my intended task. My judgment was contaminated by my focus on the
code and on the book, and my automated tests were sometimes not
helpful enough. Then the universe would rise up and whack me, and I'd
try to improve my process.
As far as I know, it all comes down to that. In my long years at this,
I've taken courses, attained degrees, read zillions of books. All
these things helped. What helped the most was the practice -- putting
the ideas I learned about into practice. That's what builds the
intuition we need.
Now bless you, my son, and go in peace. :)
--
Ron Jeffries
www.XProgramming.com
I'm giving the best advice I have. You get to decide if it's true for you.
Laurent Bossavit
> I would consider this message, together with any readily available
> pamphlet/url on the rules of Go, to be a sufficient point of departure
> to write some story cards and to start planning a first iteration of
> development...
Steven Perryman over in a comp.object thread stated willingness to do
"domain anlysis" the way he would do it, as a test of my hypothesis that
the knowledge that is captured in the first few story tests is a good
enough substitute for "domain analysis".
I think XP would recommend that we start with option 1, as more amenable
to a small release sometime soon. In that scenario option 2 would be an
interesting test of how modular an architecture we end up with, since
we'd want to rip out most of the GUI parts of the editor for a games
server.
I'm not sure your description is sufficient analysis for me. I don't
know who the users are, and why they would prefer using the software
rather than play on a goban. Also, it seemed to me that Christophe's
post on what he might want from a Go editor could provide interesting
suggestions.
However, assuming we did have enough information to write out a few
story cards, what would these be ?
Laurent
Vladimir Levin
> Steven Perryman over in a comp.object thread stated willingness to do
> "domain anlysis" the way he would do it, as a test of my hypothesis that
> the knowledge that is captured in the first few story tests is a good
> enough substitute for "domain analysis".
I would love to see anything he would produce. The idea of working the
same project (or part thereof) using several different approaches
certainly sounds interesting to me.
> I think XP would recommend that we start with option 1, as more amenable
> to a small release sometime soon.
I agree. I'd suggest starting with the "simple gui go editor" notion
then. Designed properly, one would hope much of the initial code could
be reused for development of some further, as yet undefined, project.
> I'm not sure your description is sufficient analysis for me. I don't
> know who the users are, and why they would prefer using the software
> rather than play on a goban.
To me the user would be "Joe Go Player" but please do elaborate if you
can as to how one might make the user more tangible... As for they
"why" question here are some ideas, for what they're worth...
1) May use the editor as a client for an internet go server
2) Record one's games, including variations/branches (Christophe's
idea)
3) Load and view games stored in a standard format (e.g. SGF)
4) Avoid the hassle of counting the points at the end
5) Play anywhere on a laptop or handheld that supports the game,
so more convenient for airports, buses, crowded cafeterias, etc.
> However, assuming we did have enough information to write out a few
> story cards, what would these be ?
How about:
1) Provide a 19x19 board with the ability for two players to exchange
moves
2) Remove captured groups/stones automatically
3) Implement end-of-game rule (3 consecutive passes)
4) Implement the Ko rule
5) Allow default komi editable by player before a game (not during)
6) Support setting number of handicap stones
7) Support 13x13 and 9x9 board sizes (adjust max handicap accordingly)
8) Score the game at the end
9) Save game to file (SGF format?)
10) Replay game loaded from file (SGF format?)
11) Supply estimate of score while game is in progress
I'd suggest developing an initial prototype in whatever language seems
suitable with the intention to clarify the technology to use for the
final product within the first few iterations (about 1 month sounds
reasonable). For this exercise, I think Ruby might be an interesting
option, since I've never used it but my coworkers are constantly
raving about it. Hopefully there is an RUnit...
Laurent Bossavit
> To me the user would be "Joe Go Player" but please do elaborate if you
> can as to how one might make the user more tangible...
That leaves a few questions open... Let's start with:
- What is Joe's handicap level, or other measure of Go skill ?
- Who does Joe typically play Go with ?
> 1) Provide a 19x19 board with the ability for two players to exchange
> moves
That sounds like it might be a candidate for splitting. How would you
write an acceptance test for that ?
> 2) Remove captured groups/stones automatically
> 3) Implement end-of-game rule (3 consecutive passes)
> 4) Implement the Ko rule
I think I'd be clearer on how to write an acceptance tests for most of
these...
> 5) Allow default komi editable by player before a game (not during)
> 6) Support setting number of handicap stones
> 7) Support 13x13 and 9x9 board sizes (adjust max handicap accordingly)
These sound like pertain to a different level of abstraction than 1-4;
not that this is a problem, but it's something to keep in mind as we
inquire into domain aspects.
> 8) Score the game at the end
That also sounds like a big one. (I understand that scoring is a multi-
step process, with such complications as the elimination of dead stones
and filling in neutral territory - perhaps there are intermediate steps
of "partially manual scoring" that have distinct business value.)
> 9) Save game to file (SGF format?)
> 10) Replay game loaded from file (SGF format?)
OK...
> 11) Supply estimate of score while game is in progress
OK... Perhaps another big one, perhaps not.
Two more questions:
- are these *all*, or could we come up with more ?
- can we sort these by business value ?
> I'd suggest developing an initial prototype in whatever language seems
> suitable with the intention to clarify the technology to use for the
> final product within the first few iterations (about 1 month sounds
> reasonable). For this exercise, I think Ruby might be an interesting
> option, since I've never used it but my coworkers are constantly
> raving about it. Hopefully there is an RUnit...
There is an RUnit, and Ruby is a fine language. I'd love to use Ruby to
work on something like this.
Laurent