Discussion: Coordinates System, Move notation, File format  

--Last edited by Funky-AbaloneTheory-JazzClub on 2005-11-18 17:55:46 --

Notation Standard Proposal

Part of my work on computer Abalone requires that I can save games. Currently, there is no standard that defines an open file format for Abalone. I would like to define such a standard, and to provide a reference implementation for programmers.

The standard has several goals:
1) Make it possible to save games
2) Easy exchange of games between different programs
3) Human readable
4) Text based, so it is possible to post games on forums for discusstion.

A good candidate for such a format is the PGN used by chess, but adapted for Abalone. The difference lies primarily in how moves are written.

In http://90214.aceboard.fr/90214-2318-15375-0-Move-notation.htm I present some arguments for a move notation. I would like comments on this proposal. (Otherwise the standard would not be widely accepted)

In brief:
Location use coordinates similar to AbaPro, but with axes reversed: A1 is still bottom left, but A2 is in the clockwise direction (opposite to AbaPro)

Moves always use two locations: FromFirst and ToLast (of your own pieces). For Broadside moves, the additional rule that the number of steps (Manhattan distance) between FromFirst and ToLast should be equal to the number of marbles moved.

I might be wrong but here are some remarks/questions:

1) how is handled blitz? more precisely, I haven't seen a notation to include move timestamps. right?
2) abalone allows 2 to 6 opponents. This is a major difference with chess which should be handled.
3) don't forget abalone allows 3D games (a second layer). The notation system should forsee an extension for it by implicitly considering that when the z-axis is omitted it is not present (tbi, an extra header tag or versioning will be needed for this).
4) format versioning is mandatory.
5) start-up/setup positions should be fully qualified (all marble positions and colors) and it should be a mandatory field (more precisely, one mandatory 'setup' field per color). (tell me if I'm wrong, but this could also solve the inconsistencies found between official notation and aba-pro-notation, isn't it?no!)

IMHO and in order to avoid confusion we should follow the 'official' axis notation when using an export format. By 'official' I mean the one referenced on abalonegames.com and on wikipedia.org  which are hopefully the same (and the same as the one exposed here). Abalone is not chess nor go and is highly versatile, hence no comparison argument seems to me valid. Another point is that you can't expect somebody to read this forum to find out what is the "official" notation (even if not perfect).
For what concerns the move-notation, I don't see why the short notation wouldn't coexist with the "official" long notation or even with a more robust and error prone notation (over untrusted network... fyi some "bugs" (ghost moves or ghost marbles) encountered on netabalone are partly linked to an inability to recover from a move error due to the inherent lack of context recovery with the short move-notation, but this is a matter of net-related implementation which has nothing to do here). I think It's only a matter of logic to adapt from one to another move notation (at least between short and "longer" notations or broadside moves written in one direction or the other).
I personally prefer the short notation exposed by you as it seems to lead to unique moves in all cases although non unique notation for broadside moves.
However, could you better clarify your notation? What would you chose for a g6h6i6 -> g7h7i7 move (extended from the example above)?

1.a) g6h6i6g7 (FromAllFirst-ToFirst)
1.b) g6h6i6i7 (FromAllFirst-ToLast)
2.a) g6i6g7   (FromFirst-FromLast-ToFirst)
2.b) g6i6i7   (FromFirst-FromLast-ToLast)

I would prefer 2.b (as you if I have well understood) as it matches the natural mouse selection dynamics and is more compact (as opposed to the notation exposed in Keith's message where the FromFirstFromLast-ToFirst is used).
I don't see any need to disambiguate FromFirst from FromLast as it leads to the same result (i.e. g6i6i7 or i6g6g7 are equivalent). Hence I don't see any need for an extra notation constraint (as found in abnet).


kr.  

--Last edited by kopedito on 2005-10-28 01:56:41 --

Time for a poll about axis-notation and move-notation?

Nacre, I think it is better to leave to you the practical PGN specification extension as you seem to have more abalone implementation experience as anybody else here, but please bear in mind at least my remarks number #1 (timestamps), #2 (multiplayer), and #5 (setup).

kr.

Binary file formats are commonly far more efficient regarding speed or compactness.

Text files are great by being readable by the user without any special viewer program.

Thus, if a Text format is chosen for readability, a user-friendly notation should be used. This excludes polar, 3axis or any unfamiliar, obfuscated or complex notation, i think.

However you are 100% right about timestamps, number of players and initial positions.

I think it's a good idea that each text line begins with an indication about which player it applies to.

I would start the file by indicating all positions for each player. Then, i would start each line by the player number, the time he waited before he moved and the move he did (additionnal informations being able to be added then, in case of specific needs, without requiring the program to know anything about them if it doesn't need them).  

--Last edited by chriscool on 2005-10-28 16:03:59 --

kopedito wrote:
"I would prefer 2.b (as you if I have well understood) as it matches the natural mouse selection dynamics and is more compact (as opposed to the notation exposed in Keith's message where the FromFirstFromLast-ToFirst is used)."

yes, I agree.

Seems to me a fruitful dialogue. Thank you chris, kopedito and nacre  

The suggested move-notation DOES allow broadside moves. Using AbaPro coordinates and the abbreviated notation (FromFirst-ToLast), the illustrated broadside move (2.2) would read i6g7. This is the only way to describe a move that moves i6h6g6 -> i7h7g7.

You might argue: "But what if I started in the other end? How would you describe  g6h6i6 -> g7h7i6 (which moves the same marbles). The answer is that it is STILL described i6g7: The move g6i6 would only move two marbles: g6->h7 and h7->i7.

This is caused by the rule: "Distance between FromFirst and ToLast must equal the number of marbles moved (not including opponent marbles)"

The discussion can be divided into three categories:
1) Coordinates system
2) Move notation
3) File format

1) Coordinate system
I have argued for a coordinate system that has A1 in the bottom left, and A2 in the clockwise direction. The argument against it is that a standard exist, the one defined by NetAbalone and Wikipedia. Unfortunately these two sources disagree.

Here are a quick list of coordinate systems:
AbaPro, Wikipedia: A1 = bottom left, A2 counterclockwise
NetAbalone: A1 = bottom right, A2 counterclockwise
PBM: A1 = top left, A2 counterclockwise
(Proposal: A1 = bottom left, A2 clockwise)

In order of authoritativeness with respect to notation I would order them
1) AbaPro
2) NetAbalone
3) PlayByMail
4) Wikipedia

My reasons are:
1) AbaPro is used for game notation (in the aceboard forums) - no other notation has that privilege.
2) NetAbalone is where most players are exposed to Abalone today, but the notation is not used to describe games.
3) PlayByMail has existed longer than any of the two above, so one could argue that this notation is more official. I put it in third place because it is a relative quiet place today.
4) The authors of the Wikipedia text are helpful persons - but the source of the text is not any official Abalone organisation.

My opinion is that since the body of recorded games are currently low (only a few players have bought AbaPro and use it for game comments), we have an opportunity to define a notation which is easy to learn and simple to use.

The reason I suggest A1 in the bottom left and A2 in the clockwise direction is to make it quick to master for newcomers. Most are already familiar with coordinate systems from school, where we write (x,y). The x coordinate increases to the right, the y coordinate increases up. This is what chess and go uses, and we should use the same.

Sorry, I made a mistake.  The article http://uk.abalonegames.com/magazine/articles/articles_20.html IS the official notation. With respect to coordinates, it is the one used by AbaPro & Wikipedia. With respect to move notation it is not used by anybody.

I must say I still feel that switching the axes would have benefits for newcomers, and this outweigh the drawbacks (invalidating existing game records). All games on aceboard.fr are accompanied with a descrïption of the coordinates used. Why? Because nobody knows these coordinates. Why is it necessary to describe them? Because they differ from what you would expect (the x,y coordinate system)

However, I should not have the final word here as the purpose is to build a new standard. This requires that the persons using the standard are involved in specifying it. So, what is your opinion?

3) File format
3.1) Issues
3.1.1) Timestamps
3.1.2) More than 2 players
3.1.3) Second layer variations
3.1.4) Versioning
3.1.5) Full specification of start position
3.1.6) Human readability

First, I would like to propose two file formats: One “small” that is human readable (like PGN) and one “large” that can do everything (like SGF). One other large candidate is the Generic Game Format (http://www.cs.ualberta.ca/~mburo/ggsa/ggf)

3.1.1) Timestamps
Large format. SGF does not have it today (as far as I know) but the GGF has it. I would copy the concept from GGF to SGF.

3.1.2) More than 2 players
Small format. Just add more players to each round. Example 3 player game (not a valid game):
1. a2b3 h3i2 g7g6 2. b3b4 i8h8 e5e5 ….

3.1.3) Second layer variations
Large format. I know of the variations where one or two extra marbles are added. One problem is to give them a coordinate system. One way to do it was to indicate a coordinate and “+” or “-“ to indicate if it was above or below the given location.

3.1.4) Versioning
Large format. Why not the small? Because it should be readable. PGN does not include it. If we build upon PGN we get a mature notation so I expect no backwards-incompatible extensions in the future. A brave expectation, I know.

3.1.5) Full specification of start position
Optional in Small format. The file format I use for Nacre always does this (because variations are not uniquely understood). I’m not quite sure on this, though. I would make it optional to make the notation shorter. However, one should be allowed several choices: a) nothing = classic, b) a short text = some standard variations, c) full specification.

3.1.6) Human readability
Small format only. If you look at SGF it is very unreadable, but it also capable of encoding a complete game tree (not just a sequence of moves)

3) File Format

Note that SGF is "larger" than GGF

1) Axis notation
So, it seems agreed and assumed that the y-axis is at the left and indicates the horizontal lines while the x-axis is at the bottom and indicates the diagonal columns. Starting from that, there are thus in the end 2 proposals:
1.a) (x:1->9 , y:A->I) : abalonegames & wikipedia & aba-pro ...
1.b) (x:A->I , y:1->9) : nacre & chess & go ...
It also seems commonly agreed and assumed that a coordinate is usualy (hand-)written with the letter first and the digit after (although nothing forbids to swap letter and digit -and a computer should be able to parse both-  Note that this is not the case in Scrabble for instance, where the first character indicates if the direction is horizontal (digit first) or vertical(alpha first) ).
In this context you've got a point, 1.b matches the natural x,y notation. However, unlike chess or go this abalone grid is not orthogonal (geometrically speaking). In that context, and looking at the board, what is the easiest way to get a position? From my point of view, it is easier to look first for the y-axis as it is horizontal (and thus get the letter first in the 1.a notation), and then go for the x-axis (the digit) which is less natural to retreive as it is diagonal. This would give a point to notation 1.a. Additionally, as explained in my previous post, I prefer to reuse something which has already been "standardized" on abalonegames and wikipedia than to impose a de-facto standard that would have been agreed in one or another "unofficial" forum not known by a newcomer.
Well, both notations have pro & cons... what do other people think?
I personnally would stick to the "official" 1.a.

2) Move notation.
2.a) own marbles only (no pushed opponent marbels included in the notation) => agreed.
2.b) inline moves: FromFirst-ToLast is enought => agreed. (but see 2.c below!)
2.c) broadside moves (in fact this may apply to inline-moves as well):
2.c.1) FromAnyFirst-FromAnyLast-ToAnyLast is not the most compact but is  natural and does not require disambiguation (move can be written in any direction: the "First" marble before the move and the "Last" marble before the move can be swapped.)
2.c.2) FromTheFarFirst-ToTheFarLast: here "TheFar" denotes a constraint by which disambiguation is necessary, and the fromfirst and tolast marbles which are the farest from each other during the move are taken to describe the move. This notation carry implicitly a more precise "direction" information "direction" about the move. Visually, you express the move in such a way that the 2 components of the vector describing the movement (selection and then movement direction) always have an open angle (>90°).
Let's illustrate it with some examples:
   g6h6i6->f5g5h5
     => 2.c.1) = g6i6h5 = i6g6f5
     => 2.c.2)          = i6f5    (g6h5 would refer to g6h6->g5h5)
   g6h6i6->g5h5i5
     => 2.c.1) = g6i6i5 = i6g6g5
     => 2.c.2) = g6i5             (i6g5 would refer to i6h6->h5g5)
   g6h6->f5g5
     => 2.c.1) = g6h6g5 = h6g6f5
     => 2.c.2)          = h6f5    (g6g5 would refer to g6->g5)
   g6h6->g5h5
     => 2.c.1) = g6h6h5 = h6g6g5
     => 2.c.2) = g6h5             (h6g5 would refer to h6->g5)

The advantage of 2.c.2:
  -uniqueness (very interresting for computer algorithm),
  -compact (very interresting for network),
  -carry extra direction information as for inline-moves,
  -same notation as for inline moves
  -and very elegant!
The drawback  of 2.c.2:
  -error prone?
  -can't distinguish at the first sight an inline move from a broadside move.
  -disambiguation required:
    -extra 'distance' constraint required when writing the move.
    -extra processing when reading the move.

I'm a little bit puzzled: The 'uniqueness' advantage would convince me to vote for your notation (2.c.2), BUT for the ease of readability and handwriting I would prefer the aba-pro and more common notation (2.c.1) which has also the property of not requiring disambiguation...
Anyway, both may coexist since they rely on the same 'ToLast' convention (FromFirst-[FromLast]-ToLast) and one notation can thus be deduced from the other (it is not as if we disagreed between ToFirst and ToLast)...

Conclusion? Let's support both for input (FF-FL-TL and FF-TL for inline AND broadside moves) and let's use 2.c.2 (FF-TL) for output?

3) File Format.
Concerning SGF and GGF: from my point of view they are less readable than PGN. I would prefer a modified PGN, and based on that:
3.1) Issues
My main problem with PGN is that I don't like the round-system notation (what if a variant allowed a player to have 2 moves per round or to skip a round?). More, the round-system causes a problem for timestamps. I thus propose an alternate move-system mainly based on the player-indicator. Note that the round-system adds no information since the file/game/notation is sequential. On the opposite, the player-indicator adds an important information about the rule played. I would define the move-system as follow (abnf like definition):

///BEG DEF
game: moves [" " moves]*
moves: round-system | move-system
round-system: round-indicator " " move-notation {" " move-notation}
move-system: move-indicator " " move-notation
move-notation: fromfirst [fromlast] tolast  //*cf note 2.c above
move-indicator: [round-indicator] player-indicator [time-indicator]
round-indicator: DIGITS "."
player-indicator: DIGIT ":" //[1..6]
time-indicator: DIGITS   //time elasped between 2 consecutive moves expressed in milliseconds (ms mainly for computer games and drift correction)
fromfirst: marble-position //before move *cf note 2.c above
fromlast:  marble-position //before move *cf note 2.c above
tolast: marble-position    //after move  *cf note 2.c above
marble-position: row col | col row
row: [a..iA..I]            //if convention 1.a above
col: [1..9]                //if convention 1.a above
///END DEF


Note: the round-system could still be used concurrently since it is easy to detect which system is used:
1# if there is no player-indicator (":" pattern detected) then the traditional round-system is used, no timestamp are specified and all moves of that round follow the "." of the round-indicator.
2# if there is a player-indicator (":" pattern detected) then the move-system is used and there is only one move after each indicator.

Starting from that:
3.1.1) Timestamps
with timestamps: "1.1:1000 a2b3 1.2:2000 h3i2 1.3:2000 g7g6 2.1:1500 b3b4 2.2:7000 i8h8 2.3:1200 e5e5 …." (first move takes 1 second, 2nd move takes 2 seconds, time elapsed between 4th move and 5th move is 7 seconds... etc)
wo timestamps #1: "1: a2b3 2: h3i2 3: g7g6 1: b3b4 2: i8h8 3: e5e5 …." (note also that for the example I got rid of the optional round-indicator)
wo timestamps #2: "1. a2b3 h3i2 g7g6 2. b3b4 i8h8 e5e5 …." (traditional ropund-system. note the "." instead of ":")


3.1.2) More than 2 players
agreed. works both with round-system and move-system

3.1.3) 3D games (2nd layer)
"+" and implicit "-" is an easy extension. agreed. I don't see any impact on move-notation: inline-move and broadside-move notations remain valid (FromFirst, FromLast and ToLast just extend the coordonate system without side effects)

3.1.4) Versioning
Take the traditional extension mechanism: For the time being, just assume that [Version 0.0] is the default implicit (optional) header. If another Version header is explicitly specified and different from 0.0 then do your best, ring a bell, popup a warning, crashdump gently...

3.1.5) Starting position
I would prefer a fully qualified starting position. Indeed, even with the classic, you don't know exactly where are the whites and where are the blacks (could be in diagonal)... Let's be simple, let's just always specify it. For humans it will be a matter of copy-paste, for computers a matter of 28 cycles... In order to increase readability, comments could be added to say what kind of variant it is (classic, daisy, etc... More, which language would you use to specify the variant name? english, french, german, danish, dutch? => fully qualified setup position mandatory: One setup header per player/color:
[Setup 1: a1 a2 a3 a4 ....]
[Setup 2: i5 i6 i7 i8 ....]
[Setup 3: c1 d1 e1 ....]
....

3.1.6) Human readability.
Hmmm... very interresting remark concerning game-trees!
TBI...
Well, game-trees are usefull for abaschool for instance, not for a traditional game. I would thus say that it is more computer related and doesn't need to be "easily" readable or writable by humans. So, why not including a (computer genarted) SGF like section in PGN in case game-trees or another advanced feature is used?

kr.  

--Last edited by kopedito on 2005-10-30 17:55:43 --

1) Axis notation

1.a) (x:1->9 , y:A->I) : abalonegames & wikipedia & aba-pro ...
1.b) (x:A->I , y:1->9) : nacre & chess & go ...

I think there are two arguments and I agree with both, this is my problem, because they are mutually exclusive

1.b) I agree with nacre that 1.b. has benefits for newcomers.

The right image shows the frontal-perspective of a newcomer.
The Newcomer, who plays standard-related starting-positions, reduces the complexity of the game with this frontal-perspective: there is the "wrong" presumption to play the game like chess on a orthogonal-axis board. This is the intuitive Newcomer-approach. And of this point of view it would be helpful to regard the lines as numbers, since the number-order is (cultural-)common faster available in mind.

1a) But if there is a less necessity to reduce the game-complexity, then the board-perception is changing and the number-order is dominant to the letters independent of the axis.

I think a good argument for 1b) is now, that Newcomers learn the notation and then the notation-knowledge is changing into a notation-habit. Only if an advanced player has to learn a new notation, than the frontal-perception-problem disappears and maybe by personal preferences one axis is favoured.

The question to me is, if this argument - intuitive approach for Newcomers - is the decisive argument.
And then the contrary argument appears, that 1a) is already the notation of the current strongest program, is still, however, the "official" notation and the notation of the well known wikipedia.

There are - for example - two point of views for both (Newcomers, publicity) arguments. From a evolution-point-of-view, in the long run, I think so, it is helpful to ensure the Newcomers a "fast" and "easy" approach. But from a current-organisation-point-of-view there is already a established notation and its maybe not very popular to change the notation.      

I can only say: I have not found my personal decision in this question, but there is a tendency to help the Newcomers  

2) notation
inline-moves: 2.b) is agreed and accepted, I think so.
broadside-moves: I still have to think about it, but the former propostion seems to me interesting.

3) File Format:
PGN - this is a well proved format, I think so, too.  

--Last edited by SilverSurfer on 2005-11-04 05:41:56 --

I think that part of this thread should move to 'abalone programming'.

1) axis-notation :
- do you really think that "newcomers" need to know anything about ascii notation? In fact, the term "newcomers" will most probably refer to "advanced" players. Hence the "easyness" argument is quite biased. They'll just need to be acquainted to a clear and unique reference.
- In case different axis conventions need to coexist, the versioning mechanism could still be used (i.e.: ver:0.0 = official (y,x); ver:0.1 = nacre (x,y))

2) move-notation
Just an idea: as an option/facility, just write broadside-moves in uppercases and inline-moves in lowercases.
When using notation 2.c.2 (FF-TL) , this would ease the human readability by allowing quicker differentiation between the 2 types of moves.

kr.  

--Last edited by kopedito on 2005-11-04 21:58:07 --

Just a note:

I used in the former message the term "Newcomer" with the meaning "Beginner", since I thought this was nacres (Posted 30/10/2005 07:20:12 AM ) intention.
But I use the term generally for advanced players, who play less than one year with an auspicious performance.
http://148009.aceboard.net/148009-519-1280-0-Some-good-players-Netabalone.htm#vb  (here the Newcomer: Loulei)

And I use the term "Beginner" for first-stage-players - in present days the average-period from the first day till about 1,5-6 months.
http://148009.aceboard.net/148009-109-209-0-Standard.htm#vb  
Therefore: "Beginner" was my intention.  

--Last edited by SilverSurfer on 2005-11-05 16:45:02 --

kopedito said:

Quote :

I think that part of this thread should move to 'abalone programming'.

Thank you for the advice. We will copy the according parts into the Forum Abalone-Programming, if this topic will have been  obtained something of a "first results".

Best Regards,
Funky-AbaloneTheory-JazzClub

Hello,

there are now two topics: "Official Rules and Aba-Pro-Notation"  and "Discussion: Coordinates System, Move notation, File format". This seems a better arranged order.

Thank  you,
Best Regards
Funky-AbaloneTheory-JazzClub  

--Last edited by Funky-AbaloneTheory-JazzClub on 2005-11-18 18:00:35 --