NP hardness is not about every instance being hard. It's a worst case notion. The paper provides an infinite family of instances which are hard assuming P is not NP. Any poly time algorithm solving for all instances has to solve those hard instances too, hence the game is hard in general.