Saturday, July 5, 2008

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.

Thursday, July 3, 2008

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.

Friday, June 27, 2008

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.

Tuesday, June 24, 2008

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.

Monday, June 23, 2008

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.

Thursday, March 27, 2008

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?

Tuesday, February 12, 2008

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!

Thursday, February 7, 2008

Tsumeshogi diagrams with Kanji, part II

The delay

As I wrote earlier I had been planning to produce this version of "my" Tsumeshogi Collection for a long time now. The only thing that was putting me off was weird interpretation of "reference-orientation" XSL-FO attribute. The specification describes it as follows:

The reference-orientation property defines the direction for top for the content-rectangle of the reference-area.




Property Values
ValueDescription
0Default. The orientation of this area has the same orientation as the containing reference-area
90The orientation is rotated 90 degrees from the orientation of the containing reference-area
180The orientation is rotated 180 degrees from the orientation of the containing reference-area
270The orientation is rotated 270 degrees from the orientation of the containing reference-area
-90Same as specifying 270
-180Same as specifying 180
-270Same as specifying 90

The first problem was that in Apache FOP using -90, -180 and -270 as reference-orientation instead of 90, 180 and 270 resulted in content being drawn outside its block.

The first results

The commercial equivalent of FOP, RenderX' XEP, did better in this area. I used to produce my first version of the collection with Kanji for the Shogi pieces.

The power of the Open Source community

Although XEP is a decent piece of software (and the company provides free personal edition) I decided to keep on looking for open source alternative.

I described what I am doing and I asked the question about the strange FOP behaviour on public w3.org lists. I didn't have to wait long for the answer. Jeremias Maerki informed me that the situation I described is a known bug in Apache FOP which hasn't been resolved yet.

Bad news, but at least I finally knew what is going on...

The same day, few hours later, Jeremias posted his second answer: he fixed the bug!

After downloading the newest version of FOP from Apache's site I am now able to produce the collection the way I wanted to.

Monday, February 4, 2008

Tsumeshogi diagrams with Kanji

I have just found a PDF (from xsl-fo) renderer which properly handles rotated text in tables.

I produced Tsumeshogi collection with 300 problems using "international" symbols. After that I decided to do the same thing using Kanji characters.

The PDF generator I used, Apache FOP, acted strange when it came to rotated characters (the idea was to use Kanji representation for Shogi diagrams, black pieces heading up, white pieces upside down). So I gave up.

Few days ago I found out, that there is a commercial implementation of PDF renderer (fortunately, they also provied "personal licence") -- RenderX's XEP (http://www.renderx.com/tools/xep.html).

Thank's to this piece of software I will soon be able to produce my Tsumeshogi collection using Kanji characters.

Just give me a day or two...

Sunday, January 27, 2008

Installing Oracle XE on openSUSE Linux

Despite what I have read on the net it was quite easy. I decided to put the information on the net in case I would have to repeat the procedure. And maybe someone else would need the information...

First I'll tell you what machine I use, then I'll show you what I did.

The machine

I use HP Compaq 6710b laptop, with 2G of RAM. Inside the machine is the Intel® Core™2 Duo T7300 2GHz processor.
There is Windows Vista preinstalled in it, but I decided to use OpenSuse (10.3) Linux as my development environment.

Installation procedure

You could summarize the whole process in 3 steps:
1. Obtaining the installation file.
2. Installing Oracle XE and required libraries.
3. Configuring Oracle instance.

In my case the procedure went as follows:
1. I downloaded Oracle XE for Linux x86 (http://www.oracle.com/technology/software/products/database/xe/htdocs/102xelinsoft.html). I chose oracle-xe-univ-10.2.0.1-1.0.i386.rpm.

2. Logged as the root I run the installer. Everything went smooth except for the database didn't run. I checked the installation guide (I know, I should have done it earlier :-) ) and it turned out that this Oracle distribution requires libgc and libaio libraries.

I ran software management program (/sbin/yast2 --install) that lets you see and modify software components installed on your openSUSE.
In my case the libraries where absent so I looked for them on openSUSE Build Service pages (http://software.opensuse.org/searchand), downloaded and installed them.

3. The final step, according to the manual was running the provided configuration script. So I did, as the root, ran

/etc/init.d/oracle-xe configure

I chose the default options when prompted and set up the password for sys and system users:
Do you want Oracle Database 10g Express Edition to be started on boot (y/n) [y]:y
Starting Oracle Net Listener...Done
Configuring Database...Done
Starting Oracle Database 10g Express Edition Instance...Done
Installation Completed Successfully.
To access the Database Home Page go to "http://127.0.0.1:8080/apex"
I tried to run the database's home page by running FireFox and entering http://127.0.0.1:8080/apex address.

Unfortunately I couldn't log in (I probably did something wrong but I am not sure what was it -- maybe just misspelled the password during log-in),
so I opened "Run SQL command line" and typed:
conn sys as sysdba ;
alter user system identified by ;
alter user sys identified by ;
After this maneuver I retried entering user/password and finally successfully logged into the database's home page.

Like I said, I am not sure if the last step (resetting the password) was necessary. When I have a chance to run the installation again I'll correct the information.

Have fun with Oracle on openSUSE!

Friday, January 25, 2008

New Shogi Tools banner




A friend of mine was so kind to make a banner for my Shogi Tools project.


I put the banner on the project's page. I also used it on www.myjavaserver.com/~fatboldcyclop/sfen_ggl.jsp.

Thanks Yummy!

Wednesday, January 23, 2008

Learning from our Go colleagues

Trying to figure out the way to increase popularity of Shogi I also look for already proved solutions.

I took a close look at Go world. The game, much like Shogi, is of Asian origin. And it is quite popular all around the world.

It quickly turned out that there are quite a few thinks to be envy about. Few things and activities in the Go community.

I'll try to describe them shortly here as an entry point to the discussion if the ideas would work in Shogi world.

SGF


SGF is the abbreviation of 'Smart Game Format'.

It is the least important of the things I bring up here, but still. Go guys have worked out a standard for storage and presentation of their games. (Of course, as our world is not perfect, there are few flavours of the standard.) The format allows them to discuss comment and discuss games on the net and off-line.
SGF provides many features such that strongly suppor this:
  • board markup,
  • comments,
  • game information,
  • setup positions,
  • variations etc.
You can, for example, draw arrows indicating lines of attack, markup some pieces that play a special role in a given position, etc.

Like I said, the standard itself may not be a big thing, but it let's them to communicate more easily and it also "gave birth" to many game viewer and editor programs.

The Go Teaching Ladder

Now, here is a thing I personally admire a lot. As the site states itself, after several high dan players have recommended getting your own games reviewed by stronger players as a good way to make progress, some guys came up with idea to do it over the net.
Volunteers in the ladder comment games made by weaker players. Anyone may submit a game for commenting by a stronger player.
The service is totally free and community based. This is possible, because many advanced Go players are eager to teach weaker players.
This way weak players benefit from their advice and advanced player benefits from teaching as well.

Isn't it something?

Sensei's Library


Sensei's Library is meant to be a place where Go players can meet to find information, contribute information and discuss any items related to the game. This is a Wiki which everybody is welcome to edit. There are problems with it but I think the idea is great.

There is wealth of information there, whether you are looking introduction to the game, some player's bio, problems to solve -- it's here.

goproblems.com


goproblem.com is a base with problems to solve on-line (currently 5467 problems).
The problems are divided by genre and difficulty. The system measures two types of difficulty and it's "coolness". The difficulty is expressed as: x/y where x is the percentage of people who've gotten this problem wrong and y is the average number of seconds it took people to solve the problem correctly. Coolness is a way for people to judge the problem subjectively.

While you solve the problems your rating is recalculated. You have also access to statistics of your progress.

Another cool thing is that the system let's its users to dynamically shape the database itself. You can do it by adding new problems.
Problems submitted by users wait in the sandbox. Other people play with the problems there and you, as an author, can read people's comments to see if there are any issues with your problem. Also, an examination of the attempt paths will show you where some areas may need to be improved (if a common attempt path has not been accounted for in the problem).


Would it work for Shogi?


Here are my thoughts.

Having standard for game storage and annotation would be useful but is not essential.

Teaching Ladder is a great idea. Unfortunately I think it won't work for us. The community is too small.

Site like Sensei's Library would be great. There is often a situation with "normal" sites that the author looses interest in maintaining it (or doesn't have time, etc. etc.). With Wiki this would be not a problem as anybody (or at least "more people") can make the site live.

As for goproblems.com, people claim to gain much play strength by solving the problems systematically. I think the same is true for Shogi.
I'd love to have this kind of server for Shogi. In fact, I'd want it so badly that I think I could write one myself ;-)

What do You think?


Links


SGF definition -- http://www.red-bean.com/sgf/
Go Teaching Ladder -- http://gtl.xmp.net/
Sensei's Library -- http://senseis.xmp.net/
Go Problems -- http://www.goproblems.com/

Friday, January 18, 2008

Shogi FEN -- similar works

Different FEN


After publication of the post about my proposal for Shogi positional data storage standard, there was some comments on shogi-l.
Bernhard C. März pointed out that there is similar way of storing Shogi positions described earlier. He gave a link to the archived shogi-l message: http://www.shogi.net/shogi-l/Archive/2002/Nsep29-03.txt.
The description differs from mine in 'pieces in hand' part.

There was some discussion about the approach.

>> > *fat bold cyclop* wrote:
>> > > I think the only flaw of it is, I think, it insufficient for
>> > > storing positions with more than 9 pieces in hand.
>> > In my opinion, this is a rather serious problem.
>>
>> Just use A, B, C, ..., H for 10 through 18.
>>
>> Using A through F for 10 to 16 is pretty standard (hexadecimal).
>> This particular extension seems rather obvious.

I have implemened a FEN notation in MacShogi 2 years ago, but I don't
have added the GUI part to use it yet.

I first have chosen the hexadecimal option to store the number of
pawns in hand but finally, I have preferred to use only digits.

The algorithm is pretty simple for pawns: the pieces in hand part in
the notation has 7 digits in all, one digit for each piece type,
except for the pawn where 2 digits can be used. So, if the string
contains 8 digits, the pawn number uses 2 digits, otherwise only one
digit is used for the number of pawn pieces.

It works well. But this is only a matter of personal choice.


Another SFEN

Tord Romstat devised http://www.glaurungchess.com/shogi/usi.html (draft dated 2007-01-24).
Both approaches seem to be identical. Both in contents and name :)

Sunday, January 13, 2008

Proposal: Standard for storing Shogi position information

Foreword: I know that similar work have been undertaken by different people already.
I don't claim I am inventing something that others didn't think of before. If you know some sources I'd be glad to put links to them in this post.


That said, I move on to the subject with is a proposal of standard for storing positional data in Shogi. I called it Shogi FEN (or SFEN) because it is derived from FEN standard designed for chess. I write more about the standard itself on ShogiTools project's wiki. Here I try to advocate the need for a standard like SFEN.

Do we need such a standard

I think it is very important to have a standardized way to write Shogi positions. This way data are easily exchanged between programs. Let me give you some examples:
  1. Imagine you have a database program that stores tsume Shogi problems. Your computer is Mac with English OS, your friend has Japanese Windows and he uses different database program and you want to share the problems with him.
  2. You post some positions from games of masters as a diagram on your web page using some flash application. The application is faulty and you want to switch to other program, let's say Java applet.
  3. You want to have a test suit of 100 positions for benchmarking different Shogi engines.
In all these situations, if there is a standard way to store positional data, there is no additional work required on your side. Otherwise there should be some conversion mechanism provided. Moreover, to be able to convert between proprietary standards you have to know them both.

What's so good about SFEN

Nothing :-). At least nothing until it becomes a standard. But what are the 'pros' of it?

It's more compact than traditional ASCII-diagram notation. The whole position data fits a sigle text line. In my opinion they are also easier to interpret by programs and quite readable by humans at the same time.

The idea of similar standard succeeded in chess world. I think we could learn from their experience and adopt similar solution.

Why wouldn't we want SFEN

I can think about only one good reason: "We already have a good standard for this and don't need another one".

If this would be the situation, I probably wouldn't bother making this post. But, as I see it, there are some solutions 'on the market', but:
  1. They are not really standards -- there is many flavors of single 'standard'.
  2. There is no formal specification for them -- at least none non-Japanese.
If you know of some standards, real or almost real, their specification on the net, please drop me a note. I'll be happy to post links to them and discuss them here.

Live demo


I prepared a site where you can see SFEN in action.

It's a nice moment for me, because the puzzles of my ShogiTools project start to fit together. In my earlier post about Tsume Parser I described how I translated tsume problems from shogi-l into computer-readable form.

Here I used the product of that project and made a simple converter to SFEN data.

Finally, I put all (almost 300) tsume on the page. You can see on-line SFEN to diagram conversion (and solve some tsume at the same time! ;-) ).


Note. When runing applications, don't worry if you see something like Can't contact servlet runner at 127.0.0.1:6905. MyJavaServer.com does this kind of things from time to time. Wait few moments and try again. MyJavaServer is down for good. The example has been moved to Google AppEngine.


Note 2. The page is best viewed with Mozilla browser. I could force Internet Explorer to cooperation. The elements are slightly misplaced. I think I finally won the IE battle.


Other works

After publication of the post there was some comments on shogi-l.
Bernhard C. März pointed out that there is similar way of storing Shogi positions described earlier. He gave a link to the archived shogi-l message: http://www.shogi.net/shogi-l/Archive/2002/Nsep29-03.txt.



Thank you for your attention. As always -- any comments and suggestions are welcomed.

Monday, January 7, 2008

What we can do to make Shogi more popular?

Shogi is a great game. No doubts about it. But Shogi is mainly played in Japan. There are some, maybe thousands, enthusiasts outside Japan.
Where this disproportion comes from?
The Japanese group is naturally highly privileged. Shogi is native to Japaneses. There is wealth of information for them: books, theoretical materials, web sites, online game servers. In presence of such an obvious and natural division I will try consider the subject separately for both groups. But before that, let us consider what makes people attracted to the game.

What makes us attracted to the game

I think there are several factors that make an ordinary man a board game fan. I am new to Shogi but I can judge from my experience with chess.

As I contemplate the matter I become to think that on of the most important things is a hero. We like to have someone we admire, whose steps we follow, who is an example for us.
In chess we had our Titans. Capablanca, Tal (the magician of Riga, genius tactician and attacker, my favourite), Alekhine (timeouted to have his 6 teeth extracted during world championship match to come back and win it!), Fisher (great individuality, the man who broke Soviet chess domination lasting for decades), Kasparov (great charisma, some claim that he is the best chessplayer of all time).

I am sure there are plenty of Shogi Heroes out there. But I cannot read a single line about them. Except news posted on discussion board by Mr. Manabu Terao or Mr. Reijer Grimbergen (sorry if I failed to mention other people that try to help us in similar way) there is no information in English.

So, heroes was one thing. The second thing is the community. We need to share our joy from the game. We want to hear how others are doing, what's the latest news in 'our world'. We want to share tips, how to improve. We want to meet to play a game or two (over the board or via Internet). I think there is no need to dwell on this one -- it's quite obvious.

The third think is the struggle for improvement. We love to prove to others that we are good at our game. And we have a chance to do it in very civilized way: by winning a game. There is healthy competition between us and that's good. But there is even more. We struggle with ourselves to get better. We learn from our mistakes, from books, from the articles on the net.

But wait. How can we learn from our mistakes when there is virtually no Shogi software to store and browse our non-Japanese games? How can we read articles when we don't know the language?

There are probably many more reasons that make us interested in a game. Some more important then the others. I just mentioned the reasons I consider most important. I also tried to point out what blocks the factors to make the game of Shogi more popular outside Japan.


I think there something we can do about it.

So, what Japaneses could do?

First of all, make the information flow. Let us know what is going on in Shogi world? How the fight for dominance is going between masters? How our heroes are doing?
The Japan Shogi Association (JSA, http://www.shogi.or.jp/) page is Japanese only. If I am not wrong (and I cannot confirm it, because there is no English information about it) it is the main Shogi federation. I think it is reasonable to require international version of the site from them.
I don't know if there are any, but chess world has few news sites. The most notable, in my opinion, is chessbase.com. Similar site for Shogi would be great.

Second thing is: share your knowledge. There are people doing this already -- you can see their effort on http://shogi-shack.net/default.aspx, http://shogi.typepad.jp/eweblog/ or http://www.teu.ac.jp/gamelab/SHOGI/shogipage.html.

The third thing: translate some software.

The forth: play Shogi with us. Kick our butts so we can learn new ways of doing it.

So, what Gaijins could do?

Well, we could learn Japanese. I never tried it myself but I think it's is quite reasonable. Shogi is a part of Japan culture and it's an opportunity to get it now better.

Before we learn Japanese, though, we could do one simple thing. We can ask our Japanese friends to do all the things we think could help spread Shogi over the world (see above). We could write to JSA and ask them to translate their site.

And, of course, we can try to help ourselves. Once there was this great effort, the Shogi portal called shogi.net. It seems to be dead right now (last update December 2004). Why don't we revitalise it or try something similar?

From what I see on shogi-l, there are some folks that are eager to write some new Shogi software. If there is any way to help, we should try.

OK, that's all for this short divagation.

Any comments are welcome...

Thursday, January 3, 2008

Tsume Shogi Parser (or "How to store 28k of data into 802k file and be happy about it")

What is Tsume Shogi Parser?

I am a huge shogi patzer. I am also a poor Java programmer. Well, all in all, I am a miserable creature. But even though I am so old that I remember the era of black&white TV, I think I can improve. (Not in being miserable, I mean. The other way.)

I wanted to strengthen my shogi skills by solving mating problems. You would be surprised how hard it is to find some good materials on the net. If you have some experience with Go or Western Chess you think that the Internet is the ultimate source for this kind of stuff. You couldn't be more mistaken -- at least when you don't read Japanese.

Fortunately, there are good folks out there. Shogi-l email discussion list is a place where people like these meet. Reijer Grimbergen, i.e., posted series of 300 tsume shogi problems. Roger Hare was so kind to collect some of them into a single file:

That's how I got my learning materials. The only problem left was it's form:
...
4. Black: R4d, +B4c, +P2a In hand: G
White: K2c, G3c, S4b, L1b, P4a

5. Black: R2b, G3e, S3a, L2e In hand: None
White: K3c, G4c, S1d, P4e
...

A beginner like me could use some more "visually attractive" format. By the way, it's a human nature I think: people always want more. First I complained that there are no materials at all, and then (after I found them) I wanted them to be full of diagrams and nicely formated.
Anyway, that's how I decided to write a converter for the problems. I called it Tsume Shogi Parser.

The process

Tsume Shogi Parser is intended to be a building block to use in other applications (these applications are meant to provide user interface for user convenience). In the near future I plan to provide a web app that would allow the user to upload a text file and get the resulting pdf. The parser could also be used in shogi game database to produce handouts on the fly.

Ok, let's face it. The parser will be not for much use. After all, there is only one source of data stored in this format. I treat this thing as an exercise before more important challenge: writing a parser for "This week in Shukan Shogi" posted by Reijer Grimbergen on shogi-l. The second benefit from it is trying out the part that generates pdf. That's IS going to be useful in other projects.

Let's go back to the parser. For know I’ll describe the inner mechanics of the Tsume Shogi Parser.

Technologies

For this piece of software I chose to use:
  • Java -- of course ;-),
  • JavaCC -- for defining the input file grammar and automatically generate a parser,
  • XML -- for storing the data into format that can be converted into virtually anything else,
  • JiBX -- for translating Java objects to XML (marshaling)
  • XLS-FO -- for storing information about expected layout of the handout,
  • XSLT 2.0 -- for defining a way of injecting tsume data to layout template,
  • Saxon -- the only XSLT processor I know that supports XSLT 2.0,
  • Apache FOP -- for generating PDF.
So, the process can be diagrammed as follows:

Shogi-l file->(.jj + javacc + jibix)->xml file->(xslt 2.0, saxon)->(fo, fo)->pdf

and in the future

-> spd, psn
-> database

Reading tsume

I have put all the tsume problems I found on shogi-l (most of them posted by Reijer Grimbergen) to a single file. If you're interested in it, you can download it from Tsume Shogi Project download pages. I also collected in a single file the answers for the tsume problems.

Then I wrote a JavaCC grammar for the file -- I made the computer understand what which field in the file meant. You can see the grammar on the ShogiTools project's wiki.

It was my first contact with parsers and it cost me a lot of sweat. I am still no expert here but I manage to write a simple grammar and generate a parser from it. JavaCC is of great help here. It automates most of the work so you can focus on the merit, although I had lots of problems with it. Partly because I was a beginner in the matter of parsers, partly because of lousy project documentation and community support. I've read that similar program, ANTLR, is much better in these matters. Next time I should try it so I could make an honest comparison. (If you can share your experience in the subject, please, drop me a note.

The thing is, that with the help of JavaCC and JavaCC Eclipse Plugin I generated a program that read tsume problem file and stored it in memory in Java objects. (The class diagrams of the value object used for it should be on ShogiTools pages.)
It turned out that the input data was a bit inconsistent in form. The parser showed few places and I had to do some corrections by hand. But this was not a big problem.

Producing XML

Now I wanted the data stored into an XML file.

Why XML? It is license-free, platform-independent and well-supported. Also because of the promise of easy transformations to presentation formats (without coding).

Anyway that's what the theory says. I wanted to see this in practice.

The process of transforming the memory representation of an object to a data format suitable for storage or transmission is called Marshaling. So I typed "fastet marshaller" into google search engine and got JiBX on pole position. And I used JiBX.

The interesting thing about JiBX is it's byte-code injection mechanism. In short: you define the mapping between classes and the XML. Then the mapping information is injected into your existing classes' bytecode. This means you can structure the Java classes the way you want -- they doesn't need to match the structure of the XML. It also turns out that this is a fast way do the conversion.

This part was quite quick. The program read 11k of tsume definitions and spat out 802 kB XML file. The description of XML structure can be found on ShogiTools pages.

The output

So, what is so good about having such a huge file instead of small one? And why it is so big?

Let's compare the entry for a single position in input text file and output xml file.
The text entry goes like this:
1. Black:+B3d, +B1c In hand: G
White: K2a, +R3c, L1a

Equivalent XML fragment is:
<Position>
<number>1</number>
<BlackDescription>
<PiecesPositions>
<PiecePosition>
<Piece>
<isPromoted>true</isPromoted>
<rank>B</rank>
</Piece>
<col>3</col>
<row>d</row>
</PiecePosition>
<PiecePosition>
<Piece>
<isPromoted>true</isPromoted>
<rank>B</rank>
</Piece>
<col>1</col>
<row>c</row>
</PiecePosition>
</PiecesPositions>
<Hand>
<Piece>
<isPromoted>false</isPromoted>
<rank>G</rank>
</Piece>
</Hand>
</BlackDescription>
<WhiteDescription>
<PiecesPositions>
<PiecePosition>
<Piece>
<isPromoted>false</isPromoted>
<rank>K</rank>
</Piece>
<col>2</col>
<row>a</row>
</PiecePosition>
<PiecePosition>
<Piece>
<isPromoted>true</isPromoted>
<rank>R</rank>
</Piece>
<col>3</col>
<row>c</row>
</PiecePosition>
<PiecePosition>
<Piece>
<isPromoted>false</isPromoted>
<rank>L</rank>
</Piece>
<col>1</col>
<row>a</row>
</PiecePosition>
</PiecesPositions>
</WhiteDescription>
</Position>

The second fragment is huge. It is well structured, data are organized in logical chunks. You may ask here: So what!?

And I agree. It's is no good to have kosher data structures for the sake of kosherness only. The real issue is what you can do with the data. There are the benefits of data conversion. Let me show you how our XML can be transformed.

My first try was to write XSL transformation to get an ASCII diagrams of the positions. For the given position (XML fragment above) I got this:

1.

White in hand:
9   8   7   6   5   4   3   2   1
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | wK| wL|a
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |b
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |+wR|   |+bB|c
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |+bB|   |   |d
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |e
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |f
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |g
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |h
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |i
+---+---+---+---+---+---+---+---+---+
Black in hand:G

The whole file can be downloaded from here.
Surly, we can do better than this! Well, we're almost there :-) This ASCII diagram thing was just a warm up before writing XSLT to produce PDF file. First I had to do xsl-fo my homework. For the PDF renderer I chose apache FOP which is quite well documented. So, I was able to learn some xsl-fo from apache documentation. I also used w3schools tutorials (http://www.w3schools.com/xslfo/default.asp).
I wanted my tsume shogi handout to have 6 problems per page and some tsume definition as an introduction. It was quite a bit of tedious work but I think it was worth it.
Judge for yourself. Here is the output pdf file.


Future development


I have my handouts for doing some shogi exercises off-line. My goal is reached so I stop my experiments for now. Instead I will list possible improvements below.

The pdf I managed to produce has English description of pieces on the board (i.e. wG for white gold, bK for black king). I could use Kanji characters instead. But first I need to know the unicode for each piece character and own some unicode font.

The whole thing is not a big deal. But during the process of converting my tsume text files into pdf I managed to learn few things. I think I also broke fresh ground for future conversion component that could be used in shogi programs. Imagine, you have your shogi database and you are able to add ability to render you games in the format you need just by supplying suitable transformation (XSLT) file.



See You next time...

Tuesday, January 1, 2008

Shogi Tools

Who is Fat Bold Cyclop?


My real-life alter ego works in the software industry, has a beautiful wife, two great kids and a dog.

We both like the same things but when it comes, after hard day of work, he's time to get rest I take over the control and do some fun stuff. These include playing chess or shogi over the net, watching movies, reading books. He is always puzzled why he is so tired :-)

For more information about me, please visit FBC's homepage.

One of the things of our interest is shogi. The other is developing software.

What are Shogi Tools

The whole idea of this appeared when I was browsing shogi-l discussion list.

I was looking for some tsume shogi problems to solve. Finally, I found in their archives a file http://www.shogi.net/arc/shogi-l/tsume_faq.txt. Roger Hare collected there 131 problems (mostly submitted by Reijer).

I wanted to have the tsume collection in some printable format so I could make a handout.

So I started to write a tool which I called Tsume Parser. It is supposed to read a file in the descriptive format (the format used by Roger) and convert it into more "visually attractive" one.

I also wished I had a program to help me to enhance my "board vision" in shogi. There are some similar programs for chess (i.e. http://chesstraining.sourceforge.net/) but none for Japanese chess.

I have other ideas for software that could help organize my shogi.
These led me to the conclusion that I have to take active part in developing some shogi software.

That's how Shogi Tools appeared as a project on code.google.com. There are two main goals of the project:

  • Documenting shogi community standards for storing, representing, transmitting shogi-related data (games, tsume, etc.).
  • Building tools to translate between the formats.
Future plans contain, after building mentioned set of tools, production of turn based on-line game server for shogi players.

On the pages of this blog You will be able to trace the progress of my work on the subject. I'll try to describe the problems I encounter and how (or if) I solved them.


See you!