Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Warp wrote:
And also, I wonder if it would be possible to make the emulator pause automatically when the game makes a move.
It appears that when a move has been made, and the game plays a sound, the value at memory address 9E changes from 64 to 32. Then, when the sound has done playing, it changes back to 64. This might be a good trigger for pausing the emulation. Could someone give me some hints on how to write a piece of lua to do this?
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
I figured out how to do the above, so I suppose my question isn't relevant anymore. This is the shortest game I have managed so far (once again at maximum strength, opening book enabled), Chessmaster playing white. 27 moves. Still took 1 hour and 50 minutes. The mate in the end is just beautiful. Stockfish is a monster. 1. f4 e6 2. Nc3 b6 3. e4 Bb7 4. d4 Bb4 5. Qg4 Nf6 6. Qxg7 Rg8 7. Qh6 Bxe4 8. Nf3 Nc6 9. Qh3 Bxc2 10. a3 Bf5 11. Qh4 Be7 12. Qf2 Na5 13. Nd2 Ng4 14. Qg1 c5 15. d5 exd5 16. Nxd5 c4 17. Bxc4 Bc5 18. Qf1 Rg6 19. b4 Bd4 20. Ra2 Re6+ 21. Be2 Qc8 22. Bb2 Bxb2 23. Nc4 Qxc4 24. Nf6+ Bxf6 25. Kd1 Qb3+ 26. Kd2 Bc3+ 27. Kc1 Qb1#
Aran_Jaeger
He/Him
Banned User
Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany
I'm not familiar with the game, but under the assumption that the AI's calculation time depends on the number of remaining pieces on the board such that one would expect shorter calculation times for it to get to a resulting turn, couldn't it possibly be a viable approach to (among the set of turns that are within its ''book'') keep doing turns that quickly reduce the number of pieces on the board with trades (to get rid of a bunch of pawns, for example), and to then break out of the AI's known set of turns after a whole lot of pieces are off the board (in the hope that the calculation times now would be significantly smaller) and to then try to win the game? However, considering that pawns don't have such a big variety of turns that can be done with them (and hence they might not add or carry as much calculation time with them), reducing their number might not be worth the turns needed to get them off the board. So here is a slightly altered suggestion: There's reason to assume that the extra-ordinairily long calculation time rather depends on all the turns that could happen in the near future, so one maybe even would want to use some kind of ''Low%'' (in the sense of trying to win with as few as possible remaining pieces, but to first quickly get to this small number of pieces) approach where one would early on sacrifice mainly many of those pieces (or take them away from the AI) that have the largest number of moves they can do (either the theoretical number of different moves that in a given situation might be diminished because of some moves not being possible anymore in some constellation, or the actually remaining possible moves, but I'd assume the AI might need to determine first which moves among the theoretical ones are still possible and which aren't, so theoretical moves might still account towards calculation time to some degree). On the other hand side (as an aspect that opposes this strategy), the less turns that remain available (for the player and the AI), the harder it probably would get to still trick the AI (especially if one kept one's own turns for a long time within the set of turns that are known to the AI, because its resulting turns are expected to be good), since the AI then should have it easier to find a good turn quicker. So one might want to reduce pieces near the end in a way with some sort of trade such that the resulting constellation is unwinnable for the AI (so that one is certain that one can enforce a win, even if it will take many more turns than usual, on a board with far less remaining pieces) so that the AI can only delay its loss with turns that are in the way of the player's winning strategy, but if there aren't many pieces on the board anymore, a high number of remaining turns to win hopefully might not hurt as much anymore, provided that the AI proceeds quickly with its last turns. Edit: Another aspect of this strategy could be to do (preferably still acceptable) turns such that the number of turns that are now possible in the new constellation doesn't grow all so much. 2nd edit: Another approach could be to take a given solution process and add a tiny (and for the sequence of turns that leads to the checkmate irrelevant) turn at some intermediate step in the hope that the calculation times for the new constellation reduces (even though everything is the same, except some pawn is 1 step further or something like that). This could maybe be done by either doing a trade at a ''secondary battlefield'' or section that is independent (if possible) of the area on the board that is used for the checkmate, or to not reduce/trade pieces, but to add some irrelevant turn with some piece that will not change the winning process.
collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)
Joined: 10/28/2013
Posts: 130
Location: United States
Warp wrote:
I think that the suggestion of finding an opening trap (that's not in Chessmaster's opening book, or if not using the book) could be the most promising approach. It's just that I don't have enough chess opening knowledge to remember such traps by heart, and there are quite tons of them.
Is it possible to dump the opening book? If it were available in a human-readable format it might be possible to identify the worst line that Chessmaster will voluntarily play. It's unlikely that one leads to a forced mate, but not impossible. Or, if any kind of ACE exploit can be found, we could potentially get the program to believe that 1. f3 and 2. g4 is in its opening book.
Warp wrote:
Also, from some quick testing it seems that it's really hard to induce Chessmaster to select a given opening line. Its randomization does not seem to work by using the timing of user input. (For example, if I let it start with white, it will for some reason start with c4 like 95% of the time. Sometimes it will do e4, or even f4, but I can't figure out how that decision is made. Timing of keypresses seems to have very little to no effect.)
Huh, very interesting. I wonder what the source is? Consumer chess engines generally include non-deterministic elements in their algorithms to avoid playing the same game over and over again, so there must be one in there somewhere. I strongly suspect that, as a very early release for the system, SNES Chessmaster is a barely-altered version of NES Chessmaster, so maybe the NES game would initially be an easier target to unpack (both its opening book and RNGs).
Joined: 10/28/2013
Posts: 130
Location: United States
Aran Jaeger wrote:
I'm not familiar with the game, but under the assumption that the AI's calculation time depends on the number of remaining pieces on the board such that one would expect shorter calculation times for it to get to a resulting turn, couldn't it possibly be a viable approach to (among the set of turns that are within its ''book'') keep doing turns that quickly reduce the number of pieces on the board with trades (to get rid of a bunch of pawns, for example), and to then break out of the AI's known set of turns after a whole lot of pieces are off the board (in the hope that the calculation times now would be significantly smaller) and to then try to win the game?
In my experience as a player of old console chess games, this usually isn't a viable strategy -- some engines take the same amount of time even when they have only one, absolutely forced move with no alternatives! -- and when it is viable, it only works once the number of pieces drops to 5 or fewer.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
It seemed like it was much easier to make Chessmaster go quickly off-book by making it play white, and then making a move with black that isn't in its opening book. Much harder to do that with Chessmaster playing black, as the white moves need to be somewhat reasonable. I tried it anyway. In this game move 3. Nd2 threw it off its book (incidentally, this move was the primary move suggested by Stockfish, so it was good.) The game ended being one ply shorter than the previous one I posted. And the mate is even more beautiful. At move 17 Chessmaster was greedy and went for the hanging pawn with Qxb2, which was a grave mistake: Stockfish found a mate in 11. Of course Chessmaster didn't see that, and went for the greedy continuation of taking the hanging rook, with Qxa1, which only sped up the mate by a move. Essentially, this mate sacrifices both rooks (seemingly in exchange for a single knight), which is just absolutely beautiful. 1. e4 e6 2. d4 d5 3. Nd2 Ne7 4. Ngf3 Ng6 5. h4 Nd7 6. h5 Ne7 7. h6 gxh6 8. Bd3 Bg7 9. exd5 exd5 10. Nf1 c5 11. Ng3 Qa5+ 12. Bd2 Qb6 13. Nh5 Bxd4 14. Nxd4 cxd4 15. Ng7+ Kf8 16. Bxh6 Kg8 17. Qe2 Qxb2 18. Qxe7 Qxa1+ 19. Ke2 Qxh1 20. Nf5 Qxh6 21. Nxh6+ Kg7 22. Qg5+ Kf8 23. Nf5 Nf6 24. Qg7+ Ke8 25. Bb5+ Kd8 26. Qxf6+ Kc7 27. Qd6# 1-0
Joined: 10/28/2013
Posts: 130
Location: United States
Warp wrote:
In this game move 3. Nd2 threw it off its book (incidentally, this move was the primary move suggested by Stockfish, so it was good.)
Huh, that's the Tarrasch Variation of the French Defense, which featured prominently in the Karpov-Korchnoi world championship matches. It's by no means an unusual move -- quite the contrary -- so it's odd that the Chessmaster opening book doesn't have anything for that, but covers the Ruy Lopez up to move 11+. Chessmaster's Ng8-e7-g6-e7 maneuver looks pretty misguided to me; the main responses are either 3...Nf6, 3...c5, or 3...dxe4.
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3573)
Joined: 11/3/2004
Posts: 4754
Location: Tennessee
Warp wrote:
Essentially, this mate sacrifices both rooks (seemingly in exchange for a single knight), which is just absolutely beautiful.
That is indeed a nice checkmake! Btw, I'm fascinated by what you are doing here, keep it up!
It's hard to look this good. My TAS projects
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
There's a Wikipedia article listing checkmates that are close to a known opening sequence. Finding one that isn't marked as a trap to be avoided in the openings book and is too deep for the engine to see may be a problem, though. The Légal Trap probably doesn't work against a computer because it's hard to persuade it to play the moves necessary to get into the position seen after move 4 (it might potentially be possible if you play the moves out of order?). It's slow enough that a tactical analysis might not find it, though. The Blackburne Shilling Gambit is the sort of thing that lower-skilled computers often fall for but it may well be in the openings book. Those are likely both worth trying before moving on to some of the more blundery mates.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
ais523 wrote:
The Blackburne Shilling Gambit is the sort of thing that lower-skilled computers often fall for but it may well be in the openings book.
Unfortunately that opening is in its book, and thus it doesn't fall for it. (It plays 4. c3.)
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Just out of curiosity I wanted to see how much of a difference the difficulty level in Chessmaster makes, so I let the level at its default (which is 1), to see how fast Stockfish could beat it. Since I wanted Chessmaster to get off book as soon as possible, I induced it to play the same opening as before (with Chessmaster playing black). The resulting game was indeed much shorter (and in terms of time took just a couple of minutes because Chessmaster was moving in just a few seconds.) 1. e4 e6 2. d4 d5 3. Nd2 Nf6 4. e5 Nfd7 5. c3 Be7 6. Qg4 O-O 7. Bd3 c5 8. Ne2 cxd4 9. cxd4 Bb4 10. O-O Nc6 11. Nf3 Qe7 12. Bxh7+ Kxh7 13. Qh3+ Kg8 14. Ng5 Nf6 15. exf6 Rd8 16. Qh7+ Kf8 17. Qh8# 1-0 But not having Chessmaster play at its strongest is a bit boring, so this was just a test done out of curiosity rather than anything else.
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
goldenband wrote:
Barring that, the next-best option is likely to be (1) either a closed position in which one player builds an attack on one side -- something computers are notoriously bad at evaluating -- until checkmate is inevitable; or (2) some wild sacrificial line where, again, the CPU wolfs down material until it's too late. Here's a post that features some work in that direction by Eduard Nemeth: https://timkr.home.xs4all.nl/chess2/honor.htm And SNES Chessmaster is, of course, far far weaker than the engines featured in that post.
I asked Stockfish to evaluate the Nemeth Gambit out of interest. Amazingly, it turned out that it was actually in its openings book. If playing the "standard variation" that the computers fell for, though, it believes 8. Kd5 – a natural move for lower-skilled computers – to throw away all the advantage that Black has accrued, though. I wonder if we can force Chessmaster into that line? (Incidentally, Stockfish's analysis is that Black's correct continuation is to sacrifice its Knight to buy time to move its King back home. In fact, it believes that Black has to counter-sacrifice a minor piece in more or less any plausible line after Nxe4 has been played, if it wants to keep an advantage. No wonder the line works so well against less advanced engines.)
Masterjun
He/Him
Site Developer, Skilled player (1987)
Joined: 10/12/2010
Posts: 1185
Location: Germany
Interestingly enough, the way the game handles chess logic and moves is by calculating every single move first and saving it in an array with space for 110 moves. Then, when a move is attempted, it first checks if the move is inside the calculated array, to see if it's legal or not. This results in clearly legal moves seen as illegal if you have over 110 available moves. In this case, white has 192 moves to play in total, including 23 game ending ones: 17 stalemates and 6 checkmates (Qbxb2#, Qcxa2#, Qaxb2#, Qaxa2#, Qdxb2#, Nb3#).
Warning: Might glitch to credits I will finish this ACE soon as possible (or will I?)
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
One would think that checking the legality of a move in the "naive" way would be quite easy, and absolutely within the capability of an SNES chess game. I suppose the chess engine uses that array for its calculations in each position, and the programmers decided to reuse it for checking the user's moves quickly and easily. Maybe they estimated that in a normal game there would never be over 110 possible moves.
Player (206)
Joined: 2/18/2005
Posts: 1451
An interesting idea to go for the quickest checkmate specially on the hardest difficulty. This provides a decent challenge, since on that level Chessmaster shouldn't fall into obvious traps such as the Scholar's or Fool's Mate quickly, and thus needing a more creative approach. Using a strong engine for assistance is certainly helpful to reach that goal, as Warp already demonstrated with those relatively short games, but picking sharp lines that exploit Chessmaster's weaknesses, even if not recommended by the engine as the best continuation at first, is IMO the most important thing. Anyway, here's my take on it after experimenting around with various openings (Chessmaster on hardest difficulty as black with opening book enabled): Mate in 19, King's Gambit 1. e4 e5 2. f4 exf4 3. Nf3 g5 4. d4 g4 5. Bc4 gxf3 6. Qxf3 Nc6 7. Bxf4 Bg7 8. Nc3 Nxd4 9. Bxf7+ Kxf7 10. Qh5+ Ke7 11. Nd5+ Kf8 12. O-O Nf6 13. Bh6 Kg8 14. Rxf6 Ne2+ 15. Kh1 Qf8 16. Rxf8+ Kxf8 17. Rf1+ Nf4 18. Rxf4+ Kg8 19. Ne7# 1-0 Mate in 17, Caro-Kann Defense 1. e4 c6 2. d4 d5 3. Nc3 dxe4 4. Nxe4 e5 5. Nf3 exd4 6. Bc4 b5 7. Bxf7+ Kxf7 8. Ne5+ Ke7 9. Bg5+ Nf6 10. Qf3 Ke6 11. O-O-O Bb7 12. g4 c5 13. Qf5+ Kd5 14. Nd7+ Kc4 15. Nd2+ Kb4 16. Qd3 Nbxd7 17. Qa3# 1-0 That line already looked to be hard, if not impossible to beat due to how well everything worked out, but surprisingly enough, I got one more major improvement in with my final attempt: Mate in 12 on hardest difficulty CM's total thinking time is 38 minutes and 11 seconds, so these delays are sped up in the video to make it less boring. This line is also reproducible on NES's version of Chessmaster at max difficulty. (in fact, both versions seem to generally play very similar) Looks like it might well be the limit now on this level, but of course it's impossible to know for sure.
See my perfect 100% movie-walkthroughs of the best RPG games on http://www.freewebs.com/saturnsmovies/index.htm Current TAS project (with new videos): Super Metroid Redesign, any% speedrun
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Saturn wrote:
CM's total thinking time is 38 minutes and 11 seconds
I wonder if that's starting to be acceptable in terms of how long the TAS is (assuming it would otherwise be publishable). By the way, how did you find these?
Player (206)
Joined: 2/18/2005
Posts: 1451
Warp wrote:
By the way, how did you find these?
By trial and error until something works against this specific opponent. It's the same approach as saving frames by trying different moves in any other game.
See my perfect 100% movie-walkthroughs of the best RPG games on http://www.freewebs.com/saturnsmovies/index.htm Current TAS project (with new videos): Super Metroid Redesign, any% speedrun
Aran_Jaeger
He/Him
Banned User
Joined: 10/29/2014
Posts: 176
Location: Bavaria, Germany
Turns from Saturn's video: 1. e2-e4 e7-e5 2. g1-f3 f7-f5 3. f1-c4 d7-d6 4. d2-d4 f5xe4 5. f3xe5 d6xe5 6. d1-h5+ e8-d7 7. h5-f5+ d7-c6 8. f5xe5 g8-f6 9. e5-b5+ c6-d6 10. c1-f4+ d6-e7 11. b5-e5+ c8-e6 12. e5xe6+ Would those specific 12 turns to checkmate black work on an accurate SNES emulator aswell in this way, or is this quick checkmate possibly only obtainable due to emulation bugs? I'm not sure what emulator Warp and what emulator Saturn used.
collect, analyse, categorise. "Mathematics - When tool-assisted skills are just not enough" ;) Don't want to be taking up so much space adding to posts, but might be worth mentioning and letting others know for what games 1) already some TAS work has been done (ordered in decreasing amount, relative to a game completion) by me and 2) I am (in decreasing order) planning/considering to TAS them. Those would majorly be SNES games (if not, it will be indicated in the list) I'm focusing on. 1) Spanky's Quest; On the Ball/Cameltry; Musya; Super R-Type; Plok; Sutte Hakkun; The Wizard of Oz; Battletoads Doubledragon; Super Ghouls'n Ghosts; Firepower 2000; Brain Lord; Warios Woods; Super Turrican; The Humans. 2) Secret Command (SEGA); Star Force (NES); Hyperzone; Aladdin; R-Type 3; Power Blade 2 (NES); Super Turrican 2; First Samurai. (last updated: 18.03.2018)
Player (36)
Joined: 9/11/2004
Posts: 2630
I haven't been able to reproduce the game on my flash cart. I get mostly e5 for the first turn, but for the second turn I get a lot of Nc6, some Qf6, very few d5, and one f6. This is after a couple of hundred attempts over an hour or so. So this path, if possible on a cart, is very unlikely. f5 is a rather bad move, so I guess it's not surprising that the engine almost never chooses it.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
From the little experimentation I have done, it seems that the randomness in Chessmaster is very hard to manipulate. There is no obvious way of doing it (for example delaying your own move by some amount seems to have little to no effect; from just trying this I haven't figured out any way to manipulate the program to choose a particular book move.) I fear that in order to understand how the program chooses a particular book move a lot more in-depth research would be required. And of course, after it goes off-book, I have absolutely no idea whether it always makes the same moves or whether there is randomness involved. That would also require testing and research.
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
Aran Jaeger wrote:
Turns from Saturn's video:
That's in a nonstandard format, so I translated it to PGN so that it can be loaded by computer chess programs:
[Date "2017.12.18"]
[White "Saturn"]
[Black "The Chessmaster"]
[Result "1-0"]
[Opening "Philidor Defense: Lopez Countergambit"]

1. e4 e5 2. Nf3 f5 3. Bc4 d6 4. d4 fxe4 5. Nxe5 dxe5 6. Qh5+ Kd7 7. Qf5+ Kc6 8. Qxe5 Nf6 9. Qb5+ Kd6 10. Bf4+ Ke7 11. Qe5+ Be6 12. Qxe6# 1-0
Here's an example computer analysis of the game: https://lichess.org/J083EPLs#0
Alyosha
He/Him
Editor, Emulator Coder, Expert player (3821)
Joined: 11/30/2014
Posts: 2829
Location: US
Wow, there's a lot of impressive work happening here. I hope it will eventually get translated into something that works on console. Good Luck!
Masterjun
He/Him
Site Developer, Skilled player (1987)
Joined: 10/12/2010
Posts: 1185
Location: Germany
Did somebody say testing and research? So I researched the opening book moves for now and the randomness involved is only dependent on the 1 byte frame counter at $007B, which increases every frame. For some opening moves, the game has a list with a set order of possible moves to respond with. The way random choices are handled is by taking the first move, and then checking the lower two bits of one of the 256 bytes (chosen by adding the frame counter value) at the start of a subroutine (at $00C0AF, yes, it uses bytes of code as entropy). If the bits are 0 then it advances to the next opening and tests again. If it reaches the final book move and the tested bits happen to be 0 again, it chooses the first one. Due to ROM being quite read-only, the bytes are set and the results will repeat every 256 frames, and can be tested easily. There are 106 out of the 256 bytes which have the lower two bits of 0. So the probability of the first response move to be chosen is 150/256 ≈ 58.6%. The probabilites of the next response moves can't be calculated that easily though. They are not even the same for different openings, due to the game doing several other move calculations between checking the bits (thus eventually advancing the frame counter). Here are three examples for the e4 opening: 1) The first check happens at a frame count of 0x48. 0xC0AF+0x48 = 0xC0F7 which holds 0xC5. The lower two bits are 01 so it chooses the first response opening, which in this case is e5. 2) Waiting a single frame from the previous example gives a frame count of 0x49, which results in a byte with lower two bits of 00, so it advances the opening. The next test occurs at a frame count of 0x5A which still results in 00, so it advances again. The next test happens at a frame count of 0x68 which is 01 so the third opening is chosen, which is e6. 3) Starting at a frame count of 0xF1 gives, 0xF1 -> 0x02 -> 0x10 -> 0x13 -> 0x15 -> 0x15 -> 0x16 -> 0x16 -> 0x17. So it chooses the 9th opening, which is Nc6. For a given random opening, the time it takes for the next test to occur is always the same (0x49 to 0x5A to 0x68 (example 2) are the same jumps as 0xF1 to 0x02 to 0x10 (example 3)). This is why example 3 is interesting, because the change between test 5 and 6, and also 7 and 8 is zero, so the 6th and the 8th opening (as a response to e4) can never occur. For the specific e4 opening, there are - 150 values for the 1st (e5) - 60 for the 2nd (c5) - 25 for the 3rd (e6) - 15 for the 4th (c6) - 4 for the 5th (d5) - 1 for the 7th (d6) - 1 for the 9th (Nc6) opening. Remember how I said this only holds for some openings. There are openings which seem to not have any randomness at all.
Warning: Might glitch to credits I will finish this ACE soon as possible (or will I?)
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Cool research. I wonder how it could be applied to make it easier to have Chessmaster choose a particular opening. Could perhaps a piece of lua code show that "if you make your move at the current frame, the program will respond with move X"?
Joined: 10/28/2013
Posts: 130
Location: United States
Great stuff. If the opening book could be dumped in human-readable form, we could look for any errors or refuted lines, knowing that Chessmaster would move (or could be made to move) into them instantaneously. The odds of finding a forced mate are very low, but it's possible nevertheless. EDIT: Also, Saturn's line with the Philidor Countergambit is already a much better result than I would have expected. That's a perfect example of the kind of refuted opening that can get Chessmaster in trouble very quickly, but is in the opening book just because it exists.