JavaScript ANTLR target

Tonight I managed to build ANTLR version with JavaScript target.

I must admit it was one of the most bizarre builds I did. The problem was not the target itself. The maintainers did a decent job making it. Although it is in it's early stages (the guys claim it not yet ready for publication) the compilation of the target went smooth. Building ANTLR is another story. The instructions (http://www.antlr.org/wiki/pages/viewpage.action?pageId=732) are less then obvious and only a little bit helpful. And that's a bit strange, because all in all, ANTLR is quite well documented.

[[In situation like this I start to appreciate build tools that are more strict as for defining dependencies in projects, like Maven.]]

Anyway, I did build it, so there is no need to complain.

What is important, that I can theoretically use the Shogi grammars I am working on, to build example browser-side parser for game record. Of course, I could do it earlier, by hand. But it would be much more tedious work. And this also gives me an opportunity to learn new things which is, as usual, great fun :-).

I think my first attempt will be a parser/viewer for format in which Reijer Grimbergen posts games on shogi-l and (most of the time) on his pages.

You can see an example game score in this format here. There are no variations. The file consist of only 3 types of information: tag (game details), move (what move whas made) and comment. The file is well formed -- there are strict rules to determine which line is what. A tag line starts and ends with '[' and ']' respectively. A line with move information starts with integer, followed by a dot, followed by move description, followed by two timestamps. The only exception are the comments. They can appear anytime in the text and couldn't be easily distinguished by the machine.

As I understand it, if I, in my parser, write a rule to recognize comment, which is basically free text, the rule would also consume other part of the file also. In other words every line of the text would satisfy the rule (every line can be treated as a free text), so the parser would be confused which rule to apply.

Actually I am not sure if a grammar file can describe it. (read: I am not sure if I could describe it ;-) ). Well, we'll see about that.

Ok, wish me luck.

JavaScript SFEN parser

Earlier in my posts I described Shogi FEN notation. I also showed SFEN parser -- a Java Web application that creates diagrams from SFEN data.

This time I spent some time learning JavaScript and programing the browser. As a result I came up with JavaScript Shogi Board Viewer and Shogi FEN parser. They have similar functionality as the former, but it's easier to use it on one's own Web pages.

The viewer
JS Shogi Board Viewer is a JavaScript component that makes it possible to generate Shogi position diagram on your Web page.

The viewer consists of 3 elements:

1. JavaScript program to generate the diagram
2. CSS file containing style definitions for the diagram
3. Images representing the board and the pieces

"Interesting" thing about the viewer is the way it is provided with Shogi data.

Well, I wanted my viewer to be "generic" (independent of the position data source) and possibly small. Therefore I decided that the position is provided with a javascript object. Feels like real pain, doesn't it? But fortunately, JSON notation comes to the rescue. Thanks to it we can build JavaScript objects that are understood both by computers and humans.

Besides, JSON is quite popular data exchange format, so there could be converters (i.e. from Shogi FEN or others) easily plugged in to the viewer.

Shogi position data format

The good thing about JSON is that it's very self-descriptive format. Here is how I designed the format.

The description consists of 4 elements:

• side on move
• white pieces in hand
• black pieces in hand
• pieces on the board

and could be expressed as JSON like this:

{
"sideOnMove":"black",
"blackHand":[],
"whiteHand":[],
"pieces":[]
}

Side on move is simple: it can be either "black" or "white".

Pieces in hand data is an array of numbers. Each number represent the count of pieces for a given rank. The rank is indicated by position in the array. Pieces info is stored in a given order:

• Pawn (index 0)
• Lance (index 1)
• Knight
• Silver
• Gold
• Bishop
• Rook (index 6)
  

So, for a Silver and 2 Pawns in hand the data would look like this:

[2,0,0,1,0,0,0,0,0,0]

I am not particularly happy with the format. I don't like the fact that a human has to remember position of piece ranks in the array. The format could be therefore change in the matter. [[Maybe better would be to have pairs rank:count?]]

Pieces on board are given by field:rank pairs. A field is described by 2 chars: column number and row char in the standard Shogi coordinate system. Leftmost column is named '9', rightmost is '1'. Uppermost row is 'a', lowermost is 'i'.

A piece symbol is "borrowed" from Shogi Ladder notation (http://www.shogi.net/ladder/shogiboard.html). The 'w' and 'b' in front of the piece symbol's abbreviations indicate white and black respectively. When a piece is promoted, it will be given with a preceding "+", as in "+bL" or "+wP".

Summing up, here is an example Tsume Shogi position and it's JSON object representation:

tsumeJson = { "sideOnMove":"black", "blackHand":[0,0,0,0,1,0,0,0,0,0], "whiteHand":[0,0,0,0,0,0,0,0,0,0], "pieces":[{"2a":"wK"},{"1a":"wL"},{"3c":"+wR"},{"1c":"+bB"},{"3d":"+bB"}] };

The parser

JS SFEN parser is a JavaScript class that is able to translate generate Shogi position data in SFEN to JavaScript objects. The parser and it's best friend, JS Shogi Board Viewer, make it easy to put a Shogi diagram for given SFEN on your Web page.

I won't explain SFEN here. I did my best on this ShogiTools wiki page so If you are interested in the details, please check it out.

The viewer consists of 2 elements:

1. JavaScript SFEN parser class.
   
2. JavaScript Shogi model classes (SFEN is translated to these objects).

Usage of the parser is simple. You put the following line in your code, to get JavaScript object representing given position:

tsumeJson = SfenParser.parse("7r1/6B1p/6Bsk/9/7P1/9/9/9/9 B 2S");

Then you send it to the viewer and voila!

Please, check out the example to see it in action. You can see a Shogi board here and you are able to dynamically set the SFEN to be shown.

The code is put inside the HTML file, so you can view the source to see what's going on there.

I hope that someone finds it useful...

As usual, any comment are welcomed.

New ANTLR targets

Till now I used javacc (http://javacc.dev.java.net/), the Java Compiler Compiler, for creating my parsers.

Like I said earlier (http://shogi-software.blogspot.com/2008/01/tsume-shogi-parser-or-how-to-store-28k.html) I was hoping to try ANTLR out.

Today I read two interesting pieces of information:

1. There is an IDE to develop and debug grammars, ANTLRWorks.
2. New (3.1) ANTLR would support JavaScript and ActionScript as targets (platforms in which parsers generated by ANTLR can run).

It is certainly big motivation for me to check this tool out. First of all, ANTLRWorks will make designing and testing my Shogi grammars much easier and faster.
Secondly, new targets will allow creation of shogi games browsing/viewing software on these two very popular platforms: JavaScript and Flash/Flex.

I am going to give it a try very soon.

Visiting the Dark Side

I've been inactive (as a blogger) for quite a time now.

Due to some technical problems MyJavaServer.com didn't accept any new files. That made me search for alternative hosting site for my experiments.
I couldn't find anything similar to mjs but I googled http://www.vndv.com/ out. They give you free hosting for your PHP pages, MySQL databases, subdomains, ftp access, no advertisements, very decent user interface, tutorials. But no Java... Well, nobody's perfect :-)
I spent time on toying a little bit with PHP and client side technologies.

I'll show you my firs PHP page (http://fatboldcyclop.vndv.com/index.php):

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <title>PHP Test</title>
</head>
<body>
  <?php phpinfo(); ?>
</body>
</html>

I am very proud of it :-). But seriously, I did some reading on PHP and I found it interesting. I decided to check it out later and take a closer look at client side web development with JavaScript and CSS first.
My first attempt was to write JavaScript Shogi Board Viewer. I'll describe the program on this blog later. Now I'll share with you my impressions on JavaScript (JS)-- it was basically my first real contact with the language.

First of all, I greatly underestimated the language. Now I think that it is a flexible, dynamic and powerful language. You can do many thing using small clever JS "tricks", but...

But developing in JS is for me a road trip through hell. I managed to get used to auto complete feature of Java IDEs. In Java, which is very strict, the tool can "easily" predict what the programmer can type (object properties and methods, etc.). With JavaScript it's not so easy -- it is dynamic, method and properties can be added on the fly, etc. But IDE is only small part of the problem.
The biggest pain was for me browser compatibility. I had a piece of code ruining smoothly on few browsers (i.e. FireFox 2 and 3, Opera, Safari) but IE somehow didn't like a line or two. Figuring out which line was the real challenge.

Debugging JS is so difficult. Thank God for FireBug. It saved me a lot of time and nerves, but it comes only with FireFox. Fortunately, Opera (9.5) and IE 8.0beta also have a "cheaper" version of the tool.

Another annoying thing about client side web development is CSS compliance. I tried to do simple things like having 2 text boxes next to each other. O what fun it is to make it work exactly the same in all the browsers. This one gives you an extra margin between two boxes, other resizes one box, etc. etc.
By the way, I fought with IE7.0 for correct placement of pieces on the board in my SFEN converter. I won the battle but I lost the war. After I finally forced IE7 to show it right, IE8 was released. And of course, the newer version of the browser has it's own way of positioning page elements.

Anyway, I'm glad I gave it a try. I learnt few things:

• I lack the imagination to think how people did it before the FireFox came to life.
• browsershots.org is a great tool to test your web design in different browsers.
• Trying/learning different languages opens your eyes to new possibilities.
• JavaScript is an interesting and powerful language but using it is not such fun at all.
• If you want to show HTML code on your blog, you could use this tool to make it possible.
  

All in all it was a very educational experiment for me -- short walk on the dark side of the web development.

Unicode for Shogi characters

To be able to translate Shogi data between formats you have to know possible piece symbols. I collected  the information I could get (mainly from wikipedia.org) in the following table. Then I found (on http://www.rikai.com/library/kanjitables/kanji_codes.unicode.shtml) unicode values for eaech Shogi piece.
Shogi pieces

English name	Unicode for abbr. Kanji	Kanji	Rōmaji	Meaning	Abbreviations
					Symbol	Kanji	Rōmaji
King (reigning)	738B	王将	ōshō	royal general	K	王	ō
King (challenging)	7389	玉将	gyokushō	jeweled general	K	玉	gyoku
Rook	98DB	飛車	hisha	flying chariot	R	飛	hi
Promoted rook (Dragon)	9F8D or 7ADC	龍王	ryūō	dragon king	+R	龍 or 竜	ryū
Bishop	89D2	角行	kakugyō	angle mover	B	角	kaku
Promoted bishop (Horse)	99AC	龍馬	ryūma or ryūme	dragon horse	+B	馬	uma
Gold general (Gold)	91D1	金将	kinshō	gold general	G	金	kin
Silver general (Silver)	9280	銀将	ginshō	silver general	S	銀	gin
Promoted silver	5168	成銀	narigin	promoted silver	+S	全	—
Knight	6842	桂馬	keima	horse	N	桂	kei
Promoted knight	572D or 4ECA	成桂	narikei	promoted laurel	+N	(圭 or 今)	—
Lance	9999	香車	kyōsha	incense chariot	L	香	kyō
Promoted lance	674F or 4EDD	成香	narikyō	promoted incense	+L	(杏 or 仝)	—
Pawn	6B69	歩兵	fuhyō	foot soldier	p	歩	fu
Promoted pawn (tokin)	3068 or 4E2A	と金	tokin	reaches gold	+p	と (or 个)	to

Coordinates
In KIF files the characters are Shift-JIS encoded. Characters used to describe shogi board coordinates and their unicode values are listed below.

description	char	unicode
1st column	１	FF11
2nd column	２	FF12
3rd column	３	FF13
4th column	４	FF14
5th column	５	FF15
6th column	６	FF16
7th column	７	FF17
8th column	８	FF18
9th column	９	FF19
1st row	一	4E00
2nd row	二	4E8C
3rd row	三	4E09
4th row	四	56DB
5th row	五	4E94
6th row	六	516D
7th row	七	4E03
8th row	八	516B
9th row	九	4E5D

Move modificators
The symbols used in Kifu to identify the piece to move (when there is
a situation in which more then one piece of the same kind can reach
given destination):

symbol	unicode	meaning
直	76F4	move straight
引	5F15	pull (back)
上	4E0A	go forward (literally means “up”)
寄	5BC4	go to the side
右	53F3	right
左	5dE6	left
右引		right-back
右寄		right-go to the side
右上		right up
左引		left-back
左寄		left-go to the side
左上		left up

I hope someone finds this information useful.

Requirements for new Shogi game format

There seems to be great need for a single computer standard for exchanging Shogi games data.

There has been ongoing debate on discussion board (shogi-l) for years now.

Although the discussion tends to be difficult (like the never ending dillema "which came first, the chicken or the egg") but the point is quite simple. After scanning the post you notice that there are just a few simple requirements to be fulfilled.

I try to collect them here. The standard should let for the following features:

1. Storing multiple games in one file.
2. Providing game information (type of the game, players, date, event, outcome, ...) in the way that any shogi software could correctly interpret it.
3. Allowing to store variants.
4. Allowing to store comments in different languages.
5. Allowing to embed multimedia contents (board markups, pictures, sounds, movies) in the comments.
   

Except for the last (embedding multimedia) I consider them to be the core features. They have to be included into the specification. In my opinion no matter if the standard is totally new or if it's based on some existing format (Simple Game Format, Portable Shogi Notation, KIF) it needs to address the problems mentioned above.

By the way, they seem to be easy to implement:

Ad 1) If the single game has concise and well defined description, the games are easily distinguishable/separable. Even if it is not the case, some game separator could be introduced.

Ad 2) The information could be provided in key/value pairs (let's not bother about their form now), for example sente:Sato Yasumitsu or [sente "Sato Yasumitsu"].

We would have to agree on the standard set of tags (sente, gote, event, etc.). The less, the better. The standard, to be flexible and extensible, would state that other tags are allowed but are not given any special meaning. This way if one program needs to add some information that matters only to it, it uses his own tag without any side effects on other programs.

Ad 3) There are many possibilities here. SGF and PSN uses tree-like text data structure for example. I could think of few more solutions but the actual implementation doesn't really matter. Ideally, the structure should be easy for the machines to decode but still easy enough for humans to read it.

Ad 4) For comments we should opt for standard Unicode encoding like UTF-8.

Ad 5) I have some reservations about number 5. It will greatly improve viewing the games with software but it also will make the format less readable by humans.

The most important thing is to make the multimedia comments/markups optional. I imagine not every Shogi game viewer will want the feature (furthermore I believe some target devices, like simple cell-phones, won't be able to use it).

I would split the problem of multimedia comments into two categories:

1. markups that don't require embedding additional data (markups for actions that are understand by viewer: drawing arrows, coloring board fields, showing hyper link, etc.)
2. markups that require embedding additional data (pictures, sounds, movies, etc.)

The first category is easy. The more I think about the second category the less I am convinced it belongs to the standard ;-)

And what do you think?

Tsumeshogi diagrams with Kanji, part III

I finally managed to finish PDF collection of 300 Tsumeshogi problems with pieces represented by Kanji characters (http://shogitools.googlecode.com/files/tsume_collection_0_3.pdf).

Now I am starting to validate the data. It turns out that there are few mistakes in the input data.

Missing tsume
I produced the collection from problems posted weekly on Shogi-l by Reijer Grimbergen.
There was 50 "episodes", 6 problems each which gives 300 problems. I dug the posts from our archives.
I found out that the 35th part of the series was missing from the archives -- or at least I couldn't find it.

Does anyone, by any chance has a copy of the post or the 6 problems?

Errors in definition
The second problem are errors in the definition. Some problems posted on shogi-l have clearly mistaken data:

Problem 103:
Black: S3d, S2c, P1f In hand: B, G
White: K2d, B5a, L1c, L1b, P3d, P2d
diagram

Problem 138:
Black: +B3d, B1d, N1a, L4c In hand: N
White: K2b, N1a, P1c
diagram

Problem 198:
Black: R3a, B4e, S4b In hand: R
White: K2b, G1c, S4b, N2a, L1b, P2e
diagram

Problem 297:
Black: R3f, S1d In hand: G, 2S
White: K3d, +B4b, G2e, L1a, P3b, P1d
diagram

Does somebody have any ideas how the problems should look like?


Mistakes in the problems
There could be some mistakes in the problems themselves. I found the two while browsing the archives (http://www.shogi.net/shogi-l/Archive/1993/Njan27-01.txt, http://www.shogi.net/shogi-l/Archive/1993/Njan27-02.txt). I made required corrections to problems:
12. 7l1/6k2/7p1/6p2/6N2/7+pP/9/9/9 B SGR
44. 9/6p2/5B1g1/5p2R/6k2/9/6S2/9/9 B B


If you find any errors while solving the problems, please drop a note on Shogi-l, or as a comment to this post.

Thanks in advance!