MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

converting annotations using String Manipulators, outputting

  • To: mathgroup at
  • Subject: [mg75738] converting annotations using String Manipulators, outputting
  • From: gauerkk at
  • Date: Wed, 9 May 2007 04:40:46 -0400 (EDT)

I used to be a Mathematica user in University, but no longer 
use the software that much. However, a couple of current University 
friends were looking at an approach for recommendations on their 
problem below. I have continued to follow the Mathematica newsgroup in 
recent years, an interesting and relatively active group (version 3, 
1996, but was reading about it, way before then).

It doesn't contain much Mathematica code per se, but last I talked 
with them, they were still seeking ideas. However, I'm not sure that 
this would be considered to be: on-topic (I had read in the on-line 
documentation that Mathematica supports functions such as Riffle, and 
Card-font displays, but not other Game-font ideas, etc). 

It's also a bit lengthy, but described for those who don't know much 
about a .pgn input standard, and also discussing a history and 
motivation of the idea. Perhaps it may be wished to be edited down or 
not? Also, I'd prefer to post it without my return signature, since 
they and I would only be interested in helpful ideas that could be 
accessed by the archive, as opposed to private postings, just to me.

Again, as mentioned below, I'm not even sure how far my friends could 
get with such an idea, but feel free to forward what is below the line 
to the list, if someone from the list can offer a few tidbits to help 
tackle the idea(s).

They're basically trying to find a way to convert a key annotation tag 
from parenthesis, search and operate on it, with a possible string-
matching technique, returning some modified annotations at that 
annotation key, and aren't sure where to start. I don't think at this 
point that they can use the idea for much more than a recreational 
coding project, and not intend to create a chess evaluator function in 
Mathematica for an academic or similar project.

Of course, it's also a busy time on the list, with the new version 
recently released.


<Group, please reply publicly so that answers can be viewed in the 
archives, as persons interested in the task are different than the 
person who suggested the idea - since a private reply might not pass 
the spam filter - thanks>

sampleInput ->
{[Date "1869.??.??"]
 [White "Composition, #3"]
 [Black "win, white"]
 [Result "1-0"]
 [Annotator "Composer Sam Loyd"]
 [SetUp "1"]
 [FEN "5N1k/5Ppp/8/8/2Q3p1/8/8/b6K w - - 0 0"]
 [PlyCount "5"]

1. Qf1 h6 (1... Bc3 2. Qd3 g5 (2... g6 3. Qxc3#) (2... h5 3. Qh7#) 
(2... h6 3. Qh7#) (2... Ba1 {transposes}) (2... Bb2 {transposes}) 
(2... Bf6 {transposes}) (2... Be5 {transposes}) (2... Bd4 3. Qxh7# 
{transposes}) (2... Ba5 3. Qxh7#) (2... Bb4 3. Qxh7#) (2... Bd2 3. 
Qxh7#) (2... Be1 3. Qxh7#) 3. Qxc3# (3. Qxh7#)) (1... Bd4 2. Qd3 g5 
(2... Bg1 3. Qxh7#) (2... h5 3. Qh7#) (2... h6 3. Qh7#) (2... g3 3. 
Qxh7#) (2... g6 3. Qxd4#) (2... Be5 3. Qxh7# {transposes}) (2... Bc3 
3. Qxh7# {transposes}) (2... Bb2 3. Qxh7# {transposes}) (2... Ba1 3. 
Qxh7# {transposes}) (2... Bf6 3. Qxh7# {transposes}) (2... Ba7 3. 
Qxh7#) (2... Bb6 3. Qxh7#) (2... Bc5 3. Qxh7#) (2... Be3 3. Qxh7#) 
(2... Bf2 3. Qxh7#) 3. Qxd4# (3. Qxh7#)) (1... Be5 2. Qf5 h5 (2... Bf6 
3. Qxh7# {transposes}) (2... Bd4 {transposes}) (2... Bc3 {transposes}) 
(2... Bb2 {transposes}) (2... Ba1 {transposes}) (2... g5 3. Qxh7#) 
(2... g6 3. Qxe5#) (2... h6 3. Qh7#) (2... g3 3. Qxh7#) (2... Bh2 3. 
Qxh7#) (2... Bg3 3. Qxh7#) (2... Bf4 3!. Qxh7#) (2... Bd6 3. Qxh7#) 
(2... Bc7 3. Qxh7#) (2... Bb8 3. Qxh7#) 3. Qh7# (3. Qxh5#)) (1... Bf6 
2. Qf5 h5 (2... Be5 3. Qxh7# {transposes}) (2... Bd4 3. Qxh7# 
{transposes}) (2... Bc3 3. Qxh7# {transposes}) (2... Bb2 3. Qxh7# 
{transposes}) (2... Ba1 3. Qxh7# {transposes}) (2... g5 3. Qxf6#) 
(2... g6 3. Qxf6#) (2... h6 3. Qh7#) (2... g3 3. Qxh7#) (2... Bh4 3. 
Qxh7#) (2... Bd8 3. Qxh7#) (2... Be7 3. Qxh7#) (2... Bg5 3. Qxh7#) 3. 
Qh7# (3. Qxh5#)) (1... Bb2 2. Qb1 g5 (2... Bc1 3. Qxh7#) (2... h5 3. 
Qh7#) (2... h6 3. Qh7#) (2... g3 3. Qxh7#) (2... Ba1 3. Qxh7#) (2... 
Bc3 3. Qxh7#) (2... Bd4 3. Qxh7#) (2... Be5 3. Qxh7#) (2... Bf6 3. 
Qxh7#) (2... g6 3. Qxb2#) (2... Ba3 3. Qxh7#) 3. Qxb2# (3. Qxh7#)) 
(1... g6 2. Qxa1#) (1... g5 2. Qxa1#) (1... h5 2. Qb1 g6 (2... g5 3. 
Qh7#) (2... g3 3. Qh7#) (2... h4 3. Qh7#) (2... Bf6 3. Qh7#) (2... Be5 
3. Qh7#) (2... Bd4 3. Qh7#) (2... Bc3 3. Qh7#) (2... Bb2 3. Qh7#) 3. 
Qxa1#) 2. Qb1 h5 (2... g6 3. Qxa1#) (2... g3 3. Qh7#) (2... g5 3. 
Qxa1#) (2..!. Bb2 3. Qh7# {transposes}) (2... Bf6 3. Qh7# 
{transposes}) (2... Be5 3. Qh7# {transposes}) (2... Bd4 3. Qh7# 
{transposes}) (2... Bc3 3. Qh7# {transposes}) 3. Qh7#

} // end sampleInput

The notation is called .pgn notation, black is small letters, and 
White capitalized letters (N: Knight; K: King, a numeral means leaves 
that amount of spaces, working leftwards along ranks from the a8 
position, a slash separates ranks, and the remaining FEN info says 
less usual things, like possibilities for Castling, and whose move it 
is). Other details about the syntax of a .pgn are that x means a 
capture, + means a check, and # a checkmate, the other parts being 
self-explanatory (one could search about the .pgn standard for further 

One could parse (We're not sure how the parse would work, but I do 
know that we could save each of the variations as .pgns, but without 
the "()" stuff ever occurring in a paragraph, as a list of 
separate .pgn's) the line note starting str1 = " 1. Qf1 Bc3 2. Qd3 Bb2 
{transposes} " from the paragraph and try to match it to another line, 
such as str2 = " 1. Qf1 Bd4 2. Qd3 Bb2 ". Is there a string-matching 
solution that would replace the "{transposes}" portion of str1 being 
checked for by the line found [ie: {transposes} -> {transposes to 
1 ... Bd4 2. Qd3 Bb2, so see that move-order for subsequent details}] 
from str2 once str2 no longer "matches" str1?>  > For instance, here, 
str1 = str2 again equals one another at ply=4, since at ply=4, the 
Queen has relocated to d3, and the Bishop has since retreated to b2, 
from two different paths, with no other pieces having been relocated 
to other squares. Another way that a transposition can occur is using 
different move-orders, rather than different square-connection paths. 
An example is str3 = " 1. Qf1 h6 2. Qb1 Bb2 3. Qh7# {transposes} " and 
str4 = " 1. Qf1 Bb2 2. Qb1 h6 3. Qh7#". In this case, the author has 
seen that he has added too much to the end of str3, and wants to see 
whether he can insert the {transposes} clause earlier, since it 
matches str4 at ply=4, rather than ply=5. So str3 would eventually 
read as " 1. Qf1 h6 2. Qb1 Bb2 {transposes} 3. Qh7# {user: check 
safety to chop starting here} " and later replaced by " 1. Qf1 h6 2. 
Qb1 Bb2 {transposes to 1 ... Bb2 2. Qb1 h6, so see that move-order for 
subsequent details} ". Also, one would not do the {}-replacement if 
str5 = str4!, and were somehow found twice using the same move order 
in the .pgn (it occasionally occurs).

One could be mainly interested in seeing what the graph of such 
a "spectrum" of minimal move possibilities would look like, where the 
nodes could be represented as a common graphic format generated by 
Chessbase, and the arrows would show the paths (in this case, the user 
had hopefully checked to draw out the entire spectrum of paths for 
checkmate in 2n-1 plies, but that is the chess-analyst's 
responsibility) from ply=k to ply=1+k, labelled with the appropriate 
move. Of course, two or more pictures would connect into one node, if 
and only if a transposition were found. One might also wish to throw a 
UserCheck:flag} if a position without a {transposes} label on it is 
found that apparently matches a different move sequence is found.

A friend & a couple others who use Chessbase a bit for leisure only 
recently got involved with string matching ideas, and asked whether 
this is a good or easy approach. He asked about trying to use a string 
matching solution (maybe there's some way to update the FEN and store 
FEN[ply] at each ply, but perhaps it may not need to be stored?? ... 
one may not necessarily wish to write a legal/illegal move policing 
function that flags when to jump from one ply to another for 
Mathematica), mainly because he might try some simple mate in 4's or 
5's, where positions can sometimes be match with the same player to 
move, but not on the same ply number, where the ply is small. He seems 
to only be interested in cases of moves which try to reduce a mate in 
k moves to one of a mate in k-n moves, n a positive integer (when the 
same position has occurred with the parity (even/odd) of ply 
different, the position would be considered different, and there are 
also other special rules about what !to do for repetition when the 
same or different spectrum of moves occurs at a position, but instead 
of worrying about this, just reference an arbiter who talks about 
these problems in a chess column: and seek the archived 
papers of Gijssen for ideas about en passant, etc). Generally, white 
wishes to minimize ply, when black seeks to maximize the ply.

[ Seeing the graph of the spectrum of a defensive piece when
[ comparing it to its choices of moves of ply-maximizing possibilities
[ within k plies is a (conjectured to be - by chess theorists) good
[ measure of the strength of an army's Mobility, and the relative
[ strength of any one single piece of ArmyB, relative to the entire
[ attacking power of ArmyW, given that ArmyW is known to be able
[ to mate in maxPly moves or fewer. Similar arguments are made for
[ other chessic concepts, such as Space (ie "controlled" /
[ "contested" / "(un/)occupied" squares, some or neither of
[ ArmyW/ArmyB - closely related to the concept of Space is to what
[ degree a Position's Mobility for one side is as compared to that of 
[ what the opposing side's Mobility is, and relative to the quantity of
[ UsedSpaceControlled, as a quotient of some sort of the
[ TotalAvailableSpace available is in Contest - approximately called
[ the degree of closedness or locked-ness of the position, particularly
[ useful when the position is locked, such that a side is attempting to
[ convert a modest relative SpaceControlled Contest to a much larger
[ one, hoping to converting a point-score to a better one), KingSafety,
[ Tempo and Material, etc.

Preferably, the method might also be useful for other sized boards, 
and this would be why the user might not wish to use the 1. Qf1 
Any/Only, 2. Qb1, etc notations, 1. Qf1 & 2. Qb1, etc or 1. Qf1 -- 
{threatening} 2. Qb1, notations (here, -- is what is called a null-
move, where the same player gets to analyze as though he has two moves 
in a row; and a move such as K-Only or K-Any is slightly too fuzzy to 
search for a matching later FEN on), since a boundary of a board can 
also play a mating role. For now, though, the 8x8 idea would be the 
default. They might also try it on a couple of Shatranj puzzles which 
use different move possibilities. There might also be a future idea of 
matching some diagonal-mirror symmetries and other mirror symmetries 
(there are are even some colour-transposition symmetries, where white 
is best to transpose into a position that black to move previously 
had, etc), especially for Pawn-less endings. Or maybe even some 
translational shift patterns if th!e string-matcher calls doesn't have 
to care about the board-size and boundaries (ie mating in the Centre 
of the board).

It is not necessary to put the lines back into "()"-nested notation, 
since Chessbase has a nice feature called merge which can do this, as 
long as the starting FEN string matches. It would, however, be nice to 
not have to chop up the nested-notation (except for the header 
details, which aren't such a big deal - the idea is to not carry the 
FEN string each time for separate lines).

While I didn't take much about graph theory or programming, I was 
lightly introduced to it in a course called Discrete & Combinatorial 
Math as a math student, but the approach using strings seems to be 
better than trying to create a custom Object class or data-type box to 
hold this type of input in. Any opinions? Would a string (without the 
(), {} brackets) of 5 ply length be too long to try and match? They 
don't know either...

Asked by a B. Sc., math (in other words: (i) this is not homework; 
(ii) I'm not sure where to recommend a start to learn about string 
matching by example, or how complex the idea would be to implement for 
a small size length and relatively small forking size at a given 
node). A similar example is included below, where the tree has fewer, 
but longer branches:

[White "Horwitz, Bernhard"]
[Black "win, white"]
[Result "1-0"]
[Annotator "Bernhard Horwitz"]
[SetUp "1"]
[FEN "1k4B1/8/8/n1K3N1/8/8/8/8 w - - 0 0"]
[PlyCount "17"]

1. Kb6 Nb7 2. Nf7 (2. Ne4 Kc8 3. Be6+ Kb8 4. Bc4 Kc8 5. Bb5 Kb8 6. Bd7 
Nd8 7. Nc5 Nf7 (7... Nb7 8. Na6+ Ka8 {transposes}) (7... Ka8 8. Na6 
Nb7 9. Bg4 Nd6 10. Bf3+ Nb7 11. Bxb7#) 8. Na6+ Ka8 9. Bc6#) 2... Kc8 
3. Bh7 Kb8 4. Bf5 (4. Be4 Nd6) 4... Ka8 5. Bd3 Kb8 6. Ba6 Nc5 7. Kxc5 
Kc7 8. Bb5 Kb7 9. Bc6+ (9. Ba4) (9. Bd7) (9. Be8) (9. Nd8+ Kc8 (9... 
Kc7 10. Ne6+ Kb7 {transposes}) 10. Ne6 Kb7 11. Bc4 (11. Bd3 Kc8 (11... 
Kb8 12. Ba6 {transposes} (12. Kb6 Kc8 13. Bb5 {transposes})) (11... 
Ka7 12. Kc6 Ka8 (12... Kb8 {transposes}) 13. Ba6 {transposes} (13. Kb6 
{transposes})) 12. Kc6 Kb8 13. Ba6 {transposes}) (11. Be2 Kc8 (11... 
Kb8 12. Ba6 {transposes} (12. Kb6 Kc8 13. Bb5 {transposes})) (11... 
Ka7 12. Kc6 Ka8 (12... Kb8 13. Ba6 {transposes}) (12... Kb8 
{transposes}) 13. Ba6 {transposes}) 12. Kc6 Kb8 13. Ba6 {transposes}) 
(11. Bf1 Kc8 (11... Kb8 12. Kb6 Kc8 13. Bb5 {transposes}) (11... Ka7 
12. Kc6 Kb8 {transposes} (12... Ka8 13. Kb6 (13. Ba6 Ka7 {transposes}) 
13... Kb8 14. Ba6 {transp!oses})) 12. Kc6 Kb8 13. Ba6 {transposes}) 
11... Kb8 (11... Ka7) (11... Kc8 12. Kc6 Kb8 13. Ba6 Ka8 (13... Ka7 
14. Nc5 Ka8 (14... Kb8 15. Kb6 {transposes}) 15. Kb6 {transposes}) 14. 
Kb6 {transposes}) 12. Kb6 (12. Ba6 Ka7 13. Kb5 Kb8 (13... Ka8 14. Kb6 
Kb8 15. Nf8 (15. Nd8 Ka8 16. Bb7+ Kb8 17. Nc6#) (15. Nd4 Ka8 16. Bb7+ 
Kb8 17. Nc6# {transposes}) (15. Nc5 Ka8 16. Bb7+ Kb8 17. Na6# (17. 
Nd7# {transposes})) 15... Ka8 16. Bb7+ Kb8 17. Nd7#) 14. Kb6 Ka8 15. 
Nf8 (15. Nd8 Kb8 16. Nc6+ Ka8 17. Bb7#) (15. Nd4 Kb8 16. Nc6+ 
{transposes}) (15. Nc5 Kb8 16. Nd7+ {transposes}) 15... Kb8 16. Nd7+ 
Ka8 17. Bb7#) 12... Kc8 13. Bb5 Kb8 14. Ba6 (14. Bd7 Ka8 15. Nc7+ Kb8 
16. Na6+ Ka8 17. Bc6#) 14... Ka8 15. Nc5 {transposes} (15. Nd4 
{transposes}) (15. Nd8 {transposes}) (15. Nf8 {transposes}))


  • Prev by Date: Re: Re: Re: Re: MathPlayer???
  • Next by Date: navigating hyperlinks with LinksBar in Mathematica 6.0
  • Previous by thread: Re: Re: Format->Magnification does not work
  • Next by thread: navigating hyperlinks with LinksBar in Mathematica 6.0