Current status of microscope puzzle difficulty in T7G (& possible feature request for Groovie engine)

[Robot_Maker20]

Can anyone please tell me if the microscope puzzle difficulty in the 7th Guest is currently capped in any way, or is the code a direct reproduction of how the scripting functioned in the original release?

I can't find the link now (I'm sorry, I swear I bookmarked it, but now I just can't find it either in my bookmarks list or browser history! If I find it, I'll append it to this post when I do), but I recently tracked down a site where someone finally laid out, in detail, the exact problem with the microscope puzzle's infamous difficulty level, as originally implemented in the DOS release. It turns out that, in order to ensure the puzzle wasn't agonisingly slow for people running on less-than-then-current hardware (so anything less than about a 486DX with something of the order of ~8MB RAM, I think?), the game logic is rigged with a simple timeout to limit the opponent algorithm's search tree depth, such that it never takes more than a certain number of seconds per turn (I think the number 1.2 was mentioned somewhere in the article, possibly the turn limit in seconds?)

The trouble with this approach is, it only puts a practical limit on how deep the algorithm can search on a slower-than-1993-standard machine. If you run it on a machine faster than the benchmark setup T7G was originally designed for, there is literally no other limit on how deep the search tree can get within the fixed computing time per turn, thus difficulty will directly scale with CPU speed relative to 1993 standard, and on any modern computer the puzzle will simply be unbeatable for any human player. Back in the day, I ran my original copy on a CX586 machine with 16MB RAM, and even that was quite enough to ensure that I never beat it, though I admit I'm pretty bad at that kind of puzzle anyway.

So, my question is, does the current ScummVM Groovie implementation reproduce this original scripting error and thus make the puzzle unbeatable, or has it been modified in some way so as to place a hard upper limit on the difficulty? If so, what is this difficulty set to, and would it be possible to have a variable parameter added to the config file (and maybe game launcher menu?) to allow for its adjustment? I'd suggest making it a fractional multiplier for a hard numerical limit on the algorithm's search depth, with a value of unity corresponding to the search depth that would be achieved on a machine matching the original game's "ideal" system requirements, running the original DOS executable, if that number can be reliably determined now without undue effort.

[Praetorian]

Can anyone please tell me if the microscope puzzle difficulty in the 7th Guest is currently capped in any way, or is the code a direct reproduction of how the scripting functioned in the original release?

I can't find the link now (I'm sorry, I swear I bookmarked it, but now I just can't find it either in my bookmarks list or browser history! If I find it, I'll append it to this post when I do), but I recently tracked down a site where someone finally laid out, in detail, the exact problem with the microscope puzzle's infamous difficulty level, as originally implemented in the DOS release. It turns out that, in order to ensure the puzzle wasn't agonisingly slow for people running on less-than-then-current hardware (so anything less than about a 486DX with something of the order of ~8MB RAM, I think?), the game logic is rigged with a simple timeout to limit the opponent algorithm's search tree depth, such that it never takes more than a certain number of seconds per turn (I think the number 1.2 was mentioned somewhere in the article, possibly the turn limit in seconds?)

The trouble with this approach is, it only puts a practical limit on how deep the algorithm can search on a slower-than-1993-standard machine. If you run it on a machine faster than the benchmark setup T7G was originally designed for, there is literally no other limit on how deep the search tree can get within the fixed computing time per turn, thus difficulty will directly scale with CPU speed relative to 1993 standard, and on any modern computer the puzzle will simply be unbeatable for any human player. Back in the day, I ran my original copy on a CX586 machine with 16MB RAM, and even that was quite enough to ensure that I never beat it, though I admit I'm pretty bad at that kind of puzzle anyway.

So, my question is, does the current ScummVM Groovie implementation reproduce this original scripting error and thus make the puzzle unbeatable, or has it been modified in some way so as to place a hard upper limit on the difficulty? If so, what is this difficulty set to, and would it be possible to have a variable parameter added to the config file (and maybe game launcher menu?) to allow for its adjustment? I'd suggest making it a fractional multiplier for a hard numerical limit on the algorithm's search depth, with a value of unity corresponding to the search depth that would be achieved on a machine matching the original game's "ideal" system requirements, running the original DOS executable, if that number can be reliably determined now without undue effort.

Wow, that is a good analysis!

Sev would probably be the one to explain in detail how the puzzle currently works in the ScummVM Groovie engine implementation.

In the MojoTouch release of The 7th Guest Anniversary Edition, they made that puzzle optional, and later on (patch 1.0.5) reduced its difficulty. From a quick glance at the code, they set "depth" explicitly to 0 for when Stauf plays, and the comment is "// set depth to 0 in order to make difficulty reasonable on current CPUs".

Their change is here (I'm linking to the ScummVM current code -- theirs have "0" where ScummVM uses "depth"):
https://github.com/scummvm/scummvm/blob ... l.cpp#L791

I don't know if the "depth" variable here corresponds to the search tree depth for the algorithm to play the game.

As far as I know, we haven't integrated any of the changes that MojoTouch made, yet. There are some improvements (eg. subtitles) that would be nice to have. But, as with everything, there needs to be someone with enough spare time and no other ongoing tasks to do this.

(I can brag that I was able to solve the puzzle on my PC before they introduced the 1.0.5 patch, after only a couple of attempts, but perhaps it was already nerfed before or I was very lucky).

[sev]

Yes, that is correct. The 'depth' parameter specifies the recursion level of the algorithm, and no, there is no timer in the original game. When 'depth' is set to 0, then the algorithm is dumbed down significantly. Otherwise, a more complex logic of up to 3 levels of recursion is used with gradually increased AI power, see the 'depths' array which specifies deeper recursion when you go further in the game: https://github.com/scummvm/scummvm/blob ... l.cpp#L761

MojoTouch/iPhSoft wanted to dumb down the game, and while I am personally not happy about the number of their "improvements" to the games, they work closely with the current IP owners, and those apparently are fine with these changes.

And to clarify: the original AI is not scripted, it is all in hardcore C. The only thing which is scripted is the difficulty level which I assume, is either calculated or used as a setting somewhere deep in the scripts. You may see, that the above mentioned 'depth' parameter comes directly from the scripts (but then overridden in MojoTouch version of the engine): https://github.com/scummvm/scummvm/blob ... .cpp#L1595


Eugene

[Robot_Maker20]

The only thing which is scripted is the difficulty level which I assume, is either calculated or used as a setting somewhere deep in the scripts.

Well, that's exactly it - feverishly wracking my brains some more to try to remember the details of what I read in that article 2-3 months ago*, I think the "move timer" was actually implemented not as an explicit timer per se, but by means of the difficulty setting itself; that is, a naive algorithm somewhere or other in the code checks the machine speed at runtime, then estimates and sets the maximum difficulty level that can be achieved within the set time limit per move on such a machine, but that difficulty setting algorithm was allegedly never given an upper cap on how high it was allowed go - presumably because they picked a time limit within which a then-state-of-the-art machine would just happen to nicely hit the desired maximum difficulty.

I suppose a quick test to see whether I've got this right or not, prior to potentially wasting effort digging through raw C code to actually find and analyse said algorithm, would be just to do a bit of good old-fashioned "printf() debugging" to verify what the difficulty parameter is actually being set to whilst the game is running on a modern rig, but I'm afraid I'm nowhere near familiar enough with the ScummVM/Groovie code to attempt a trick like this myself right now, or for the foreseeable future. Heck, I've got so much on the go right now that I barely even have time to make these forum posts, but I wanted to get them out there whilst I still remembered this happened at all!

Anyway, sorry for the vagueness and my inability to provide a reliable source for this information as yet, but I hope what I've struggled to recall is at least somewhat accurate and useful. Out of curiosity, has any human being ever actually been confirmed to have beaten the puzzle, without machine assistance, whilst playing the original release of T7G on ScummVM?

*As soon as I read it, shortly after trying and failing to beat the puzzle many times during a bout of terrible insomnia at like 0300h, I resolved to ask about it on these forums and then promptly forgot about it until now, and now also cannot find anywhere for the life of me - maybe it was some obscure link I followed to a long-vanished article on internet archive, hence why I can't seem to find it in search engines today! I think it may even have been written by Graeme Devine himself or one of the T7G team; assuming my own memory hasn't been totally corrupted by the considerable sleep deprivation I was experiencing, I do distinctly recall that it explicitly acknowledged a mistake was indeed made in the original code.

[sev]

I was playtesting the game during development. Also, if you would just open the code, you would see:

Code: Select all

	if (newDepth >= 20) {
		assert(0); // This branch is not implemented

E.g. you get an assert if the depth is too big, or in the release builds, the game is skipped. I will check what is the value of depth on my computer.


Eugene

[Robot_Maker20]

Why is the depth limit 20? That sounds awfully high; IIRC a depth of 3 is quite challenging enough for the average human, and the lookup table depths[] doesn't exceed it. It looks from the following code snippet as if the actual depth is supposed to vary between 1 and 3 for each move, jumping around pseudo-randomly within the table.

Though it may or may not be relevant here, I do think I can spot a potential fragility in the following code:

Code: Select all

const int8 depths[] = { 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 3, 3 };

int16 CellGame::calcMove(int8 color, uint16 depth) {
	int result = 0;

	_flag1 = false;
	++_moveCount;
	if (depth) {
		if (depth == 1) {
			_flag2 = true;
			result = doGame(color, 0);
		} else {
			int newDepth;

			newDepth = depths[3 * (depth - 2) + _moveCount % 3];
			_flag2 = true;
			if (newDepth >= 20) {
				assert(0); // This branch is not implemented
			} else {
				result = doGame(color, newDepth);
			}
		}
	} else {
		_flag2 = false;
		result = doGame(color, depth);
	}
	return result;
}

It appears that if the initial value of the depth argument passed to calcMove() is greater than 8, it is possible for the function to attempt to read beyond the end of the array depths[] when assigning newDepth; this could then potentially give NewDepth any random value up to the assertion limit of 20, when working from the lookup table it should never exceed 3.

Interestingly, I can't see any obvious sign of the depth cap that was supposed to originally have been implemented to compensate for slower machines, or even, in fact, much ability of this function to support it with any degree of granularity; if calcMove() is called with a depth of either 0 or 1, it consistently calls doGame() with a depth of 0 (is this possibly another bug, and should the placements of doGame(color, 0) and doGame(color, depth) actually be reversed in the above snippet?); if called with a depth of 2 or greater, it always follows the same pattern of pseudo-random depths using the initial depth value as a random seed, if I'm understanding the code correctly. One would have thought following the same pseudo-random pattern but then manually clamping the value returned by the lookup table to be at or below 3, 2 or 1 according to machine speed would be how it was originally done, or some similar arrangement, if this code follows the original game's supposed implementation.

[criezy]

The `depths` array is clearly not random. Values in it roughly increase so that if you initial depth is small you are more likely to get a `newDepth` of 1 (or even 0 if your initial depth is smaller than 2) while with a high initial depth you are more likely to get a `newDepth` of 3. So if this initial depth depends on the computer speed, that would indeed have the effect of using more depths for faster computers (but never more than 3). And indeed hopefully the initial depth is always between 0 and 8 as otherwise you would get out of bound access to he `depths` array.

And I am puzzled by that `newDepth >= 20` check since `newDepth` is a value from the `depths` array which doesn't have any value above 3.

[Robot_Maker20]

Ah, I think I can see that now. Thanks. I had instead got the notion that it was a recursive call of some sort, using the modulo of the turn number combined with the current depth to select where in the array it jumped to for the next turn a bit like an Enigma cipher, hence the pseudo-random aspect. I was guessing a bit so that I wouldn't have to dive deeper into the code to see exactly when and how this function is actually called, and since I've been doing a lot of functional programming lately, I guess I've just got recursion on the brain... I think maybe I also assumed they would have done it that way because if the level of "brilliance" of the opponent were to vary unpredictably between moves, instead of on a simple 3-step cycle through a list with the modulo of the turn number, it would probably feel more like playing against a person than a machine.

Mayhap this could potentially even be made an optional enhancement to the engine over the original, then?

[criezy]

It certainly does not help that two seemingly different quantities are both called depth (or rather "depth" and "newDepth"). I also assumed initially there might be a recursion! But looking a bit more at the code I think the "depth" value is not really a depth but some other thing from which the depth (the "newDepth" value) is inferred. But I only looked at the code you posted here, and didn't check what the engine actually does. So I could be wrong.

[sev]

It all came straight from the disassembly. Thus, the better names would be 'difficulty' for 'depth' and 'depth' for 'newDepth'. And yes, depth (e.g. newDepth) is the recursion depth.


Eugene

[ScottT]

The only thing which is scripted is the difficulty level which I assume, is either calculated or used as a setting somewhere deep in the scripts.

Well, that's exactly it - feverishly wracking my brains some more to try to remember the details of what I read in that article 2-3 months ago*, I think the "move timer" was actually implemented not as an explicit timer per se, but by means of the difficulty setting itself; that is, a naive algorithm somewhere or other in the code checks the machine speed at runtime, then estimates and sets the maximum difficulty level that can be achieved within the set time limit per move on such a machine, but that difficulty setting algorithm was allegedly never given an upper cap on how high it was allowed go - presumably because they picked a time limit within which a then-state-of-the-art machine would just happen to nicely hit the desired maximum difficulty.

I've heard the claim before as well, although never from a direct source - only ever claimed that someone heard from someone else. Indeed, there is similar claims about using the library book gave a so-called good vs bad ending too. Even if it was originally planned, the final game never had such a feature. Honestly, I think the AI is just brutally difficult by default

For the depth parameter, the scripts either hand in 1, 6 or 7 (driven by a couple of conditions - not sure on specifics but looks to be based on the current board state, possibly how many 'resets' the player has done, and also if you've visited the library book?). From what you said, this means the limit of 20 would never be hit (as it's never above

[Robot_Maker20]

For the depth parameter, the scripts either hand in 1, 6 or 7 (driven by a couple of conditions - not sure on specifics but looks to be based on the current board state, possibly how many 'resets' the player has done, and also if you've visited the library book?). From what you said, this means the limit of 20 would never be hit

Ah, that might also mean that the other apparent bug I spotted (calcMove() calls doGame() with a depth of 0 when it is passed a depth of either 0 or 1) probably is indeed a programming error, but the conditions presumably never arose to make it a noticeable issue?