Searching the history to enforce the threefold repetition rule[1] wouldn't be efficient, but the fifty-move rule[2] could be pretty cheaply implemented (one cell of state for a counter, an increment-and-check per move, and resetting the counter to 0 on the relevant moves).