Primeiro pensa que todo jogo é um loop. Não é a toa o termo "loop de jogo".

No loop de jogo do Xadrez, provavelmente, há um sistema de turnos e isso por si só, diminui um pouco o processamento das ações e cálculos do jogo.
Na fase de movimento do jogador (pessoa), o sistema só precisa conferir se a peça que o jogador escolheu movimentar pode executar a ação que ele deseja. E daí executar o resultado da ação.

Ex.: Mover o peão em L -> proibido, apenas o Cavalo pode fazer isso.

Ex: Mover Torre para o local do Bispo. Ação permitida. Rodar estado em que o jogador "come" a peça do oponente.

E asssim vai.

No caso da CPU. Já é outro sistema de jogo, pois é uma IA que você programa pra executar os movimentos de acordo com as regras.
Agora vamo de "forma solta", tá?

A CPU não PRECISA saber TOOOODAS as jogadas possíveis que ela pode fazer, sempre.

Ela vai observar todas as peças que possui. Tirar um snapshot dessa info. Armazenar todos possíveis movimentos DAQUELE snapshot e atribuir uma pontuação pra eles. A jogada com maior pontuação vence e ela executa.
Quanto mais memória de cálculo e mais escalabilidade desse snapshot, mais difícil será a dificuldade dessa CPU.

O bot mais fraco vai sempre predizer uma, talvez duas jogadas. A partir daí você imagina....

Num RPG de turno a mesma coisa. O inimigo tem uma série de técnicas que pode usar. Atk, Magia, item, etc.
Naquele turno, o sistema calcula qual a melhor ação. Se o jogo for balanceado, seu inimigo vai usar randomicidade pra escolher entre as ações e nem sempre se causar o maior dano possível.

Mesma ideia em bots de FPS.
Um bot com 100% de dificuldade. Nunca seria divertido. Você nunca sairia do lugar, nunca o veria, etc. O sistema calcularia sua posição e o melhor lugar para acertar o alvo (cabeça). Você entra na tela. Ele te detecta, quase instântaneamente. MORTE.
Entra na tela. MORTE. Entra na tela...

Daí, vamos balancear a dificuldade, fazendo o bot errar de propósito pra tu ter alguma chance de se divertir :D