N-gramas são populares aqui. A idéia básica é manter uma lista de movimentos que o jogador fez. Você pode então, dados os últimos N movimentos do jogador, descobrir a probabilidade percentual de qual será o próximo movimento dele.
Seu jogo deve ter um banco de dados de contadores e blocos efetivos para cada jogada.
Para modos ofensivos na IA, você ainda pode modelar o jogador básico para determinar quais ataques o jogador teve mais problemas para bloquear ou combater e reutilizá-los.
Para dificuldade de IA, reduza a IA em níveis mais fáceis. O pior modo AI pode inverter as escolhas (ou seja, se ele sabe que o jogador geralmente bloqueia socos, ele tem um chane mais alto do que baixo para dar um soco). O modo de maior dificuldade usaria o algoritmo não deficiente, e provavelmente vai acabar com o jogo.
Se você deseja tornar o jogo mais divertido, também recomendo adicionar personalidade à IA. Alguns personagens podem provocar mais, outros podem ser mais defensivos do que ofensivos etc. Os jogadores gostam de poder atribuir inteligência humana aos personagens de IA.