converting annotations using String Manipulators, outputting
- To: mathgroup at smc.vnet.net
- Subject: [mg75738] converting annotations using String Manipulators, outputting
- From: gauerkk at uregina.ca
- 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
questions).
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:
http://www.chesscafe.com/archives/archives.htm 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}))