Ehrenfeucht-Fraïssé games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P = NP or NP = coNP no progress has been achieved using the games. We show that for these problems it is already hard to get the board for the corresponding Ehrenfeucht-Fraïssé game. We obtain similar results for the so-called Ajtai-Fagin games and for a variant where the structures are obtained randomly.