That is with some bounds applied to it - if we allow unbounded games (ko, superko, etc) then it is EXPTIME-complete.