|
> The most naive implementation would replay the entire previous match every time a new action happens. A better implementation realizes that you don't need to - because once you have one repeat, everything after should be a repeat as well, so you really can just keep running and merely check for repeats at strategic points (such as between turns or on any human input). Store the serialized state at those points in some appropriate Set implementation to make checking easy and fast. Increase the spacing between those checkpoints, deleting old ones, if space becomes an issue - though if you get to this point, the game has run for so long that the humans playing it probably need medical attention. Any test of this type only works if there is a repeat, which you can only know about if you have a finite machine, and even with finite steps it takes 2^n steps[0] to be sure you've hit an infinite loop. Even in a computer, even with a fairly small deck to build the state, you'll time out on things like the stars going out before you can rule out any loop. And there isn't necessarily any repeat at all in the unbounded case. The state is recorded by 18 types of card, where "moving" left or right along the tape modifies the number of hitpoints on each card. At that point, I think you can still kinda decide if it halts or is infinite with the Busy Beaver number, except only "kinda" because now you run into the problem that the Busy Beaver number itself isn't generally computable because of the halting problem. Also the lower bound S-number for a mere 2-state 6-symbol machine, let alone the 2-state 18-symbol one in the paper, is already 10⇈10⇈(10^(10^115)), which is so much larger than the Poincaré recurrence time of the universe (even when measured in Planck times) as to make those periods themselves to be infinitesimal rounding errors. > All of this is possible because of the human element: Human just aren't physically capable of producing enough input to make a computer sweat about recording it. In practice, it's the opposite problem: for both humans and computers, even if you already know what it's going to compute and it's only doing something simple, it takes ages to get through enough states to say either way. It's a very slow Turing machine. [0] well actually[1] it's something more like min(2^n, BB(2, 18)), but BB numbers grow so much faster that in practice they only matter for infinite tapes [1] I've probably got this wrong, like getting the m and n switched around because the terminology doesn't seem to be entirely consistent, hence me starting that footnote with the traditional catchphrase for someone about to say something stupid :P |