¿Existe un lenguaje formal para describir juegos?

Creo que lo que estás buscando es GDL (también conocido como Lenguaje de descripción del juego). Le recomiendo que eche un vistazo a la clase General Game Playing en Coursera. El curso se centra en la creación de programas que se pueden alimentar a cualquier descripción del juego (en GDL, por supuesto) y jugar de manera competente.

Aquí hay un GDL de tic-tac-toe: Página en githubusercontent.com

  init (celda (1,1, b))
 init (celda (1,2, b))
 init (celda (1,3, b))
 init (celda (2,1, b))
 init (celda (2,2, b))
 init (celda (2,3, b))
 init (celda (3,1, b))
 init (celda (3,2, b))
 init (celda (3,3, b))
 init (control (blanco))

 legal (P, marca (X, Y))) <=
     verdadero (celda (X, Y, b)) ∧
     verdadero (control (P))
 legal (blanco, noop) <=
     verdadero (celda (X, Y, b)) ∧
     verdadero (control (negro))
 legal (negro, noop) <=
     verdadero (celda (X, Y, b)) ∧
     verdadero (control (blanco))

 siguiente (celda (M, N, x)) <=
     hace (blanco, marca (M, N))
 siguiente (celda (M, N, o)) <=
     hace (negro, marca (M, N))
 siguiente (celda (M, N, W)) <=
     verdadero (celda (M, N, W)) ∧
     distinto (W, b)
 siguiente (celda (M, N, b)) <=
     verdadero (celda (M, N, b)) ∧
     hace (P, marca (J, K)) ∧
     (distinto (M, J) | distinto (N, K))
 siguiente (control (blanco)) <=
     verdadero (control (negro))
 siguiente (control (negro)) <=
     verdadero (control (blanco))

 fila (M, W) <=
     verdadero (celda (M, 1, W)) ∧
     verdadero (celda (M, 2, W)) ∧
     verdadero (celda (M, 3, W))
 columna (N, W) <=
     verdadero (celda (1, N, W)) ∧
     verdadero (celda (2, N, W)) ∧
     verdadero (celda (3, N, W))
 diagonal (W) <=
     verdadero (celda (1,1, W)) ∧
     verdadero (celda (2,2, W)) ∧
     verdadero (celda (3,3, W))
 diagonal (W) <=
     verdadero (celda (1,3, W)) ∧
     verdadero (celda (2,2, W)) ∧
     verdadero (celda (3,1, W))

 terminal <= línea (W)
 terminal <= ~ abierto
 línea (W) <= fila (M, W)
 línea (W) <= columna (N, W)
 línea (W) <= diagonal (W)
 abierto <= verdadero (celda (M, N, b))

 objetivo (blanco, 100) <= línea (x)
 objetivo (blanco, 50) <= ~ línea (x) y ~ línea (o) y ~ abierto
 objetivo (blanco, 0) <= línea (o)
 gol (negro, 100) <= línea (o)
 objetivo (negro, 50) <= ~ línea (x) y ~ línea (o) y ~ abierto
 objetivo (negro, 0) <= línea (x)

Con solo esto (y un Game State Manager), un programa GGP puede jugar tic-tac-toe.