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}))