Demo identification heuristics

[Gez]

Suppose you want to identify if a demo is for Doom, Heretic, Hexen, or Strife (let's ignore source ports for now) -- how would you do it?

I've thought about it a bit (my notes are below) but maybe someone has already some more indepth method?

Spoiler

Strife is relatively easy because its demos have an odd size: 12 bytes for the header, 6 bytes per tic and per player, and then one byte to mark the end, so the size is 13 + 6pt.

Doom post 1.2 demos are also relatively easy to identify because they have a bigger header which begins with exe version -- if the first byte is 109, it's a Doom v1.9 demo. They have a 13 byte header and four bytes per tic and per player, so the size is 14 + 4pt.

The problem comes with Doom 1.2 demos or older, and especially Heretic and Hexen demos. They have a simple, non-versioned header (first byte between 0 and 4, for skill level) with only seven (Doom, Heretic) or eleven (Hexen) bytes. Heretic and Hexen have six bytes per tic and per player. So size:

Doom: 8 + 4pt (size % 4 == 0)
Heretic: 8 + 6pt (size % 6 == 2)
Hexen: 12 + 6pt (size % 6 == 0)

But those aren't enough to identify with certainty. Suppose you have a single player demo with a size of 24, is it four tics of Doom or two tics of Hexen? If the size is 20, is it three tics of Doom, or two tics of Heretic?

(If you want more realistic values, 3428 can be a 855 tics demo for Doom or a 570 tics demo for Heretic.)

If the demos are multiplayer, it's a bit easier because the size, not counting the header and end marker, must be a multiple of the number of players present. So 3428 couldn't be the size for a two-player Doom demo, but it could be the size for a two-player Heretic demo -- or a three player Doom demo (285 tics in either case).

I guess one possible method to help refine the results would be through analysis of the tic commands; for example if we get a forward move greater than 50 it's probably not actually a forward move, if we get a Hexen weapon switch to slot 7 it's probably not actually a weapon switch, etc.

[Maes]

Well, implement your method and then apply it on a large dataset, produce results and publish a research paper :)

[scifista42]

First check file size. If there becomes ambiguousness between Doom-Heretic or Doom-Hexen, check all tic commands for those values which as you say are impossible in one of the games - as I read about the formats on doomwiki, I believe there can be many different instances of such impossibility-revealing values. If this also fails to provide a 100% clear proof, I suggest to check all of the commands again, doing a kind of a probabilistic analysis, considering both the command values and differences between them in consequent tics. For example if there is uncertainty whether a tic is actually Doom's turning or Heretic's/Hexen's artifact usage, it can help to assume that turning values change more often and for longer time, while artifact usage tends to have non-zero values only occasionally and for a brief moment. So if you observed that the majority of these commands showed either of the abovementioned tendencies more than the other, you would estimate that one of the games is more probable than the other. Combine several such analyses and decide the game simply by choosing the one with greater estimated probability.

[Linguica]

I was hoping this thread would be about IDing players by their movement signatures or something :(

[Gez]

Linguica said:

I was hoping this thread would be about IDing players by their movement signatures or something :(

Now that would be worthy of a research paper!

[Maes]

Aren't some movement heuristics already used to spot TAS demos?

[kb1]

Are you identifying them for a lump editor, so that it can show properties?
Your MOD 6 stuff is a great start. If it were me, I'd use a grading system. In other words, how likely is one vs. the other.

I'd start with the sizes MOD 6 and 4, and if that equals 0 (or 2), apply a large score for each port that fits.

Then parse thru the tics, and make a heuristic of how likely it is that a player would do an action, following another action, and, accumulate that value, whether positive or negative. The best score wins. If this is for a lump editor, you could always show all possibilities, sorted by a confidence level.

When evaluating tics, it's safe to say that the user will not hold down the "open door" action. But, they may strobe it for a while (wall humping). Also, most users fire once, wait a few tics, and fire again, OR hold down fire for a while. A heuristic could be made there.

Also, it's more likely to move from a left-right direction to a forward-reverse direction, vs. left-right-left-right. That's a bit sketchy, though.

Here's a very interesting idea:
Make an analysis tool, and feed it the whole archive of Doom 1.9 demos, and use it to identify patterns based on the available actions. In fact, you could store a database of every possible combination of, say, 8 tics, complete with how many times each one occurs, across all demos in your archive.

That alone would allow you to judge the likelyhood that the demo in question is for Doom, Heretic, Hexen, or whatever. Oh wow, that's a super interesting cool project. Not a 10 minute answer by any means, but pretty straight-forward, and a massively slick way to accomplish your goal.

If you don't do it, I just might (when I get hold of tons of free time, that is ... :( ).

That tool could also identify TAS demos, probably very accurately. What are all the possible actions in a demo? It's not only the movements, but also amount of movement, right? That would cause your database to grow huge, but, it'd be worth it. I imagine it could also tell you who was playing the demo, with a fair degree of accuracy.

Hell, you just wanted to identify the game, but this project is way more fun, huh? :)

What do you think of my idea?

[Gez]

kb1 said:

Are you identifying them for a lump editor, so that it can show properties?

Yes.

kb1 said:

When evaluating tics, it's safe to say that the user will not hold down the "open door" action.

Yes, though a button press will generally last more than a single tic. (1/35th of a second is a very short time to move back and forth, as far as our fingers are concerned!)

kb1 said:

What do you think of my idea?

It goes quite a bit beyond my ambitions. :)

[dew]

kb1 said:

That tool could also identify TAS demos, probably very accurately.

Colour me a skeptic. First of all, TAS is a very broad term and I'm pretty sure whatever you have in mind will only work on a small subset of it.

The most worrying and hardest to detect cheat is segmenting (stitching demos). I see very little hope for any algorithm being able to discover them, unless the cheater is clumsy about it or the port releases invisible paint on it (which entryway refused and it'd probably be useless with free source anyways). Visual-based cheats (wallhacks, smart HUD, bright spectres, etc) seem undiscoverable and aimbots serve extremely limited purpose in singleplayer Doom. Constant sr50 or sr50 on turns are trivial to discover. So what's left? Slo-mo? People have been accused of that several times, but it takes a lot of interpretation by experienced players and it's rarely been clear cut.

Basically for anything useful you'd need a "biological passport" like they have in athletics or cycling. A lot of demos of the same player on which you'd observe all the statistics of typical behaviour by every player and report on anomalies. Then again, almost all of the super-polished speedruns would be false positives.

But perhaps I'm underestimating your proposal?

[scifista42]

kb1 said:

Here's a very interesting idea:
Make an analysis tool, and feed it the whole archive of Doom 1.9 demos, and use it to identify patterns based on the available actions. In fact, you could store a database of every possible combination of, say, 8 tics, complete with how many times each one occurs, across all demos in your archive.

That alone would allow you to judge the likelyhood that the demo in question is for Doom, Heretic, Hexen, or whatever.

I think these "probable patterns" should be selected by a human rather than discovered by an automatic analysis tool. Such tool might come to not-entirely-right conclusions when observing the more unstable values such as running/turning speed, and it doesn't help that some demos are recorded with keyboard-only while others with a mouse, which show different characteristics that may influence the automatic tool's judgement while "learning".

[Maes]

Don't underestimate what a statistical analysis can reveal about a player. E.g. is the "accelerator" released before turns, and how soon? How soon is it "hit again"? Does the player have a particular wobbling pattern or a preferred turning speed? Does the player slow down/backpedal after being ambushed, even so slightly, or does he act as if he expected them or knows that he can easily dodge them? All those things are tiring to observe by a human, simply because they are too common/numerous, but not by an algorithm.

[boris]

Gez said:

for example if we get a forward move greater than 50 it's probably not actually a forward move

Is that true? The wiki page says that "50 is normally the highest achievable speed if running", but doesn't say what "normally" is. I guess it means holding the shift button to run. But what happens with the -turbo parameter?

[Maes]

boris said:

But what happens with the -turbo parameter?

That's actually a good question...the -turbo param surely will give you a greater acceleration, but AFAIK it doesn't change the parts of the code that actively limit Doomguy's speed, so in practice a player shouldn't be able to move faster than the wallrunning speed (30 mu/tic per axis). Making -turbo larger should, in theory, just let you accelerate faster to this speed.

BTW, the "normal" speeds under certain conditions (in mu/tic) have been already calculated.

Edit: second BTW: the demo only records the intensity or "strength" of the inputs, but does not store effective position or achieved speed. So you can have all the oversized/superstrength inputs you want, but ALONE, they are not enough to determine what speed Doomguy is achieving. You can however determine if abnormal input controls are being applied (e.g. hyper-sensitive mouse inputs, always-run joystick speed trick etc.).

[Gez]

boris said:

But what happens with the -turbo parameter?

Good point; turbo increases the max player move speed. So that can't make a valid test.

Maes said:

That's actually a good question...the -turbo param surely will give you a greater acceleration, but AFAIK it doesn't change the parts of the code that actively limit Doomguy's speed, so in practice a player shouldn't be able to move faster than the wallrunning speed (30 mu/tic per axis).

Yes it does. Here's (the relevant part of) our good friend G_BuildTiccmd():

    if (forward > MAXPLMOVE) 
	forward = MAXPLMOVE; 
    else if (forward < -MAXPLMOVE) 
	forward = -MAXPLMOVE; 
    if (side > MAXPLMOVE) 
	side = MAXPLMOVE; 
    else if (side < -MAXPLMOVE) 
	side = -MAXPLMOVE; 
 

So, MAXPLMOVE is the limit. What is MAXPLMOVE defined to? It must be a constant, right? Wrong!

#define MAXPLMOVE		(forwardmove[1]) 

It's a variable!

Now, what is -turbo doing?

    // turbo option
    if ( (p=M_CheckParm ("-turbo")) )
    {
	int     scale = 200;
	extern int forwardmove[2];
	extern int sidemove[2];
	
	if (p<myargc-1)
	    scale = atoi (myargv[p+1]);
	if (scale < 10)
	    scale = 10;
	if (scale > 400)
	    scale = 400;
	printf ("turbo scale: %i%%\n",scale);
	forwardmove[0] = forwardmove[0]*scale/100;
	forwardmove[1] = forwardmove[1]*scale/100;
	sidemove[0] = sidemove[0]*scale/100;
	sidemove[1] = sidemove[1]*scale/100;
    }

It changes that variable. Oh.

[Maes]

That part of the code only allows the range of legal inputs to exceed some arbitrary limit, by replacing it with another arbitrary limit. However, effective movement (and therefore speed) is still limited by the P_XYMovement:

//
// P_XYMovement  
//
#define STOPSPEED		0x1000
#define FRICTION		0xe800

void P_XYMovement (mobj_t* mo) 
{ 	

    /* snip */
	
    player = mo->player;
		
    if (mo->momx > MAXMOVE)
	mo->momx = MAXMOVE;
    else if (mo->momx < -MAXMOVE)
	mo->momx = -MAXMOVE;

    if (mo->momy > MAXMOVE)
	mo->momy = MAXMOVE;
    else if (mo->momy < -MAXMOVE)
	mo->momy = -MAXMOVE;
		
    xmove = mo->momx;
    ymove = mo->momy;

    /* snip */
}

and MAXMOVE remains hardcoded as 30 mu/tic in p_local.h:

#define GRAVITY		FRACUNIT
#define MAXMOVE		(30*FRACUNIT)

So again, I don't think that the effective speed can go above 30 mu/tic per axis, no matter how hard Doomguy is pushed. Even a rocket fired against a wall at point blank, or catching a BFG ball plus all of its tracers, does not seem to break this limit. I'm not sure if an uncapped speed can be sustained for just one tic, though.

[scifista42]

Maes said:

That part of the code only allows the range of legal inputs to exceed some arbitrary limit, by replacing it with another arbitrary limit. However, effective movement (and therefore speed) is still limited by the P_XYMovement:

So again, I don't think that the effective speed can go above 30 mu/tic per axis, no matter how hard Doomguy is pushed. Even a rocket fired against a wall at point blank, or catching a BFG ball plus all of its tracers, does not seem to break this limit.

Yeah, but as you said, "the demo only records the intensity or "strength" of the inputs, but does not store effective position or achieved speed." So the effective speed doesn't really matter as opposed to the input speed, which is stored in the demo and which isn't capped at MAXMOVE.

[Quasar]

One fast and easy way to weed out Doom vs Heretic vs Hexen is to look at the special buttons. If the player is spamming savegame every tic, for instance, it's PROBABLY not the right format.

[printz]

Linguica said:

I was hoping this thread would be about IDing players by their movement signatures or something :(

Or maybe identifying authors based on their maps. That would help weed out authors who make their maps too similar.

[schwerpunk]

Continuing slightly off topic...

This is the first time I've heard of a turbo player flag, and maybe I'm looking in the wrong place, but according g_game.c, it seems like individual players in a network game can be turboed or no.

copypast:

	    // check for turbo cheats
	    if (cmd->forwardmove > TURBOTHRESHOLD 
		&& !(gametic&31) && ((gametic>>5)&3) == i )
	    {
		static char turbomessage[80];
		extern char *player_names[4];
		sprintf (turbomessage, "%s is turbo!",player_names[i]);
		players[consoleplayer].message = turbomessage;
	    }

I never actually played vanilla Doom online back in the day. I would've thought it would be a server/host flag and not a client flag!

[Maes]

Edit: NM. I thought that you could try and be a smartass by inputting negative or zero turbo values, but there's a lower cap of 10, as well as a max one of 400.

[scifista42]

[Gez]

schwerpunk said:

I never actually played vanilla Doom online back in the day. I would've thought it would be a server/host flag and not a client flag!

The story I heard was that it was added by one of the Id guys (Dave Taylor maybe) to surprise and beat another (probably Romero). After the trick was discovered by the rest of the team, a message warning that a cheat is used was added. Yes if it had been a normal feature it'd have been the same value for everyone in a netgame.

[kb1]

Quasar said:

One fast and easy way to weed out Doom vs Heretic vs Hexen is to look at the special buttons. If the player is spamming savegame every tic, for instance, it's PROBABLY not the right format.

This is probably the most solid way to accomplish Gez's goal.

Gez said:

Yes.

Yes, though a button press will generally last more than a single tic. (1/35th of a second is a very short time to move back and forth, as far as our fingers are concerned!)

It goes quite a bit beyond my ambitions. :)

I thought that might be the case. Try Quasar's method - that's got to be the most painless way to detect D vs. H, at least, and probably the rest of it, with some care.

dew said:

Colour me a skeptic. First of all, TAS is a very broad term and I'm pretty sure whatever you have in mind will only work on a small subset of it...

Quite understandable, and no argument here. What I propase, specifically, is the creation of a database of "tic signatures", whereas the tic signature is a fixed-size group of consecutive tics. This database would link these signatures to mGame engine and version, demo name, and demo author. I theorize that, for a given player, a given subset of the player's tic signatures will be present in any demo that player plays, give or take. It's just a theory. But, to take it further, I think the same could be said for the game engine and version, to some degree. And, finally, the same may hold true for TAS vs. non-TAS demos.

Maes said:

Don't underestimate what a statistical analysis can reveal about a player. E.g. is the "accelerator" released before turns, and how soon? How soon is it "hit again"? Does the player have a particular wobbling pattern or a preferred turning speed? Does the player slow down/backpedal after being ambushed, even so slightly, or does he act as if he expected them or knows that he can easily dodge them? All those things are tiring to observe by a human, simply because they are too common/numerous, but not by an algorithm.

Precisely. Surely certain players repeat certain patterns. I have no idea what the results might be, but I am fairly confident that they will be interesting!

scifista42 said:

I think these "probable patterns" should be selected by a human rather than discovered by an automatic analysis tool. Such tool might come to not-entirely-right conclusions when observing the more unstable values such as running/turning speed, and it doesn't help that some demos are recorded with keyboard-only while others with a mouse, which show different characteristics that may influence the automatic tool's judgement while "learning".

The tool would not decide one answer over the other, it would simply sort by a confidence level, based on the number of tic signature matches.

[scifista42]

kb1 said:

The tool would not decide one answer over the other, it would simply sort by a confidence level, based on the number of tic signature matches.

Sure, I proposed the same idea earlier in the thread (as the best thing to do after all 100%-verifiable checks fail), only that the "rules" for computing this confidence level should be created by a human rather than by feeding an entire demo archive to a learning algorithm and let it induce its own rules for evaluating new demos later.

[Maes]

Deciding what those rules will be, means creating a numerical "descriptor" in signal/pattern recognition parlance. While computing/implementing it once it's written black-on-white on a textbook or research paper is fairly trivial, designing/studying it is not.

[jmickle66666666]

Hm, if this is to show demo information in Slade 3, seems the easiest solution for implementation is just to perform basic checks to find definite matches first, then default to a "generic" demo file and let the user choose the demo target if they want to inspect it.

[Quasar]

jmickle66666666 said:

Hm, if this is to show demo information in Slade 3, seems the easiest solution for implementation is just to perform basic checks to find definite matches first, then default to a "generic" demo file and let the user choose the demo target if they want to inspect it.

The game the WAD "seems" to be for could be used as a weighting factor as well. For example, I wouldn't expect to find Doom format demos in a WAD that has SORC* sprites, a Strife-format TEXTURE1 lump, or BEHAVIOR and Hexen-format maps, just as some quick examples.

[kb1]

Quasar said:

The game the WAD "seems" to be for could be used as a weighting factor as well. For example, I wouldn't expect to find Doom format demos in a WAD that has SORC* sprites, a Strife-format TEXTURE1 lump, or BEHAVIOR and Hexen-format maps, just as some quick examples.

Yep, another good point. When the demo is in a multi-lump WAD, it's unrealistic to expect a demo for a different game within the WAD. I could provide much better suggestions if I were to build a test rig of sorts, to make the tic data more visible. That will reveal the low-hanging fruit quickly (like Quasar's savegame spamming insight.)

Unfortunately, there's a good chance that you cannot determine demo source with 100% accuracy.

scifista42 said:

Sure, I proposed the same idea earlier in the thread (as the best thing to do after all 100%-verifiable checks fail), only that the "rules" for computing this confidence level should be created by a human rather than by feeding an entire demo archive to a learning algorithm and let it induce its own rules for evaluating new demos later.

Do you want credit? Yes, your post inspired me and got me thinking. Good job! (seriously). I am proposing something bigger, which is, admittedly, slightly out of scope of the original request. Not that it's out of scope, but rather that it does a lot more (and less :). Basically, the system tells you what the rules are. My system discovers moves that, for example, could never happen in a Doom 1.2 demo, or only happens rarely in a Doom 1.2 demo.

The power of this approach is realized when you consider the fact that many hundreds of these occur in each demo, which can drastically steer the probabilities one way or the other. The human does contribute - the human tells the computer which game made each demo in a large archive, which, over time, becomes more and more fine-tuned.

Then again

[Opulent]

http://demospecs.half-empty.de/ is all you need to know.

As previously stated, the evidence of which game the lmp is for is to look at the header and then the "action" bit in the use tics.
This wouldn't be infallible though; but in longer demos it would be.

There are other bits of evidence -- eg. Hexen classes move at different speeds(and don't have a "run" ability).

btw, boom-lmpc can detect most of these things.

[Gez]

Thanks, this is useful (and let me notice I forgot a few important things, like Hexen storing the player class in the header, and Strife having two different headers depending on how many players are supported).
http://demospecs.half-empty.de/lmp/lmp.html