Flutter: Tic-tac-toe e l'algoritmo del Minimax

Nella prima parte dell'articolo abbiamo descritto l'algoritmo Minimax, un algoritmo ricorsivo per la ricerca della mossa migliore in un gioco a somma zero, ovvero quelli in cui i giocatori hanno obiettivi opposti e utilizzato nella teoria delle decisioni quando i giocatori si trovano in interazione strategica come ad esempio nel gioco Tic-tac-toe. In questa seconda parte completeremo l'implementazione in Flutter.

Il progetto in Flutter

Partiamo da un nuovo progetto e sostituiamo il codice standard nel file main.dart con questo:

import 'package:flutter/material.dart';
import 'views/board_view.dart';

void main() {
runApp(const MyApp());
}

class MyApp extends StatelessWidget {
const MyApp({Key? key}) : super(key: key);

@override
Widget build(BuildContext context) {
return MaterialApp(
title: 'Flutter Demo',
theme: ThemeData(
useMaterial3: true,
),
home: const GameBoard('Tic-tac-toe'),
);
}
}

La griglia di gioco

Nella cartella lib, creiamo una sottocartella views e dentro questa un file board_view.dart con questo codice che si occupa di costruire la griglia di gioco:

import 'package:flutter/material.dart';
import '../models/game.dart';
import '../models/minimax.dart';
import '../widgets/cell_widget.dart';

class GameBoard extends StatefulWidget {
  final String title;

  const GameBoard(this.title, {super.key});

  @override
  GameBoardState createState() => GameBoardState();
}

class GameBoardState extends State<GameBoard> {
  Game game = Game();

  late int _currentPlayer;

  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        title: Text(widget.title),
      ),
      body: Column(
        children: <Widget>[
          const Padding(
            padding: EdgeInsets.all(60),
            child: Text(
              "Tu giochi con la X",
              style: TextStyle(fontSize: 25),
            ),
          ),
          Expanded(
            child: Padding(
              padding: const EdgeInsets.all(8.0),
              child: GridView.count(
                crossAxisCount: 3,
                // genera la griglia di gioco
                children: List.generate(9, (idx) {
                  return Cell(
                      idx: idx,
                      onTap: _movePlayed,
                      playerSymbol: game.getPlayerSymbol(idx));
                }),
              ),
            ),
          ),
        ],
      ),
    );
  }

  @override
  void initState() {
    super.initState();
    reinitialize();
  }

  void reinitialize() {
    _currentPlayer = Game.PlayerX;
    game.resetBoard();
  }

  void _movePlayed(int idx) {
    setState(() {
      game.board[idx] = _currentPlayer;
    });
    if (_currentPlayer == Game.PlayerX) AIMove();
  }

  void AIMove() {
    // valuta lo stato del gioco
    if (isGameOver(game.board)) return;

    // aspetta un po' prima di rispondere
    // altrimneti la risposta è davvero troppo veloce
    Future.delayed(const Duration(milliseconds: 300)).then((val) async {
      // calcola la mossa successiva
      int aiMove = await Future(() => Minimax.play(game.board, Game.PlayerO));

      setState(() {
        game.board[aiMove] = Game.PlayerO;
      });

      // valuta lo stato del gioco
      isGameOver(game.board);
    });
  }

...
}

Nonostante l'algoritmo Minimax debba valutare un po' di alternative, la risposta è davvero molto veloce, quindi è stato necessario aggiungere un po' di ritardo per migliorare la giocabilità.

La funzione isGameOver() controlla se il gioco è finito con un vincitore o con un pareggio, mostrando un messaggio sullo schermo:

  // valuta lo stato del gioco
  bool isGameOver(List<int> board) {
    int winner = Game.checkIfWinnerFound(game.board);
    if (winner != Game.NO_WINNER_YET) {
      _showWinner(winner);
      return true;
    }
    return false;
  }

  void _showWinner(int winner) {
    var title = "Pareggio!";
    var content = "Nessun vincitore";
    if (winner == Game.PlayerX) {
      title = "Bravo!";
      content = "Hai battuto Minimax!";
    } else if (winner == Game.PlayerO) {
      title = "Game Over!";
      content = "Hai perso";
    }

    showDialog(
        context: context,
        builder: (BuildContext context) {
          return AlertDialog(
            title: Text(title),
            content: Text(content),
            actions: <Widget>[
              ElevatedButton(
                  onPressed: () {
                    setState(() {
                      reinitialize();
                      Navigator.of(context).pop();
                    });
                  },
                  child: const Text("Gioca di nuovo"))
            ],
          );
        });
  }

La griglia di gioco è costruita con 9 celle definite con questo widget (file cell_widget.dart nella cartella widgets). Ogni cella ha il bordo che dipende dalla posizione e un evento da generare al tap, solo se la cella è vuota:

import 'package:flutter/material.dart';

class Cell extends StatelessWidget {
  final int idx;
  final Function(int idx) onTap;
  final String playerSymbol;

  Cell(
      {super.key,
      required this.idx,
      required this.onTap,
      required this.playerSymbol});

  final BorderSide _borderSide = const BorderSide(
      color: Colors.blueAccent, width: 2.0, style: BorderStyle.solid);

  void _handleTap() {
    // only send tap events if the field is empty
    if (playerSymbol == "") onTap(idx);
  }

  @override
  Widget build(BuildContext context) {
    return GestureDetector(
      onTap: _handleTap,
      child: Container(
        margin: const EdgeInsets.all(0.0),
        decoration: BoxDecoration(border: _cellBorder()),
        child: Center(
            child: Text(playerSymbol,
                style: TextStyle(
                    fontSize: 100,
                    fontWeight: FontWeight.bold,
                    color: (playerSymbol == "X")
                        ? Colors.greenAccent
                        : Colors.black))),
      ),
    );
  }

  /// Returns a border to draw depending on this field index.
  Border _cellBorder() {
    Border determinedBorder = Border.all();

    switch (idx) {
      case 0:
        determinedBorder = Border(bottom: _borderSide, right: _borderSide);
        break;
      case 1:
        determinedBorder =
            Border(left: _borderSide, bottom: _borderSide, right: _borderSide);
        break;
      case 2:
        determinedBorder = Border(left: _borderSide, bottom: _borderSide);
        break;
      case 3:
        determinedBorder =
            Border(bottom: _borderSide, right: _borderSide, top: _borderSide);
        break;
      case 4:
        determinedBorder = Border(
            left: _borderSide,
            bottom: _borderSide,
            right: _borderSide,
            top: _borderSide);
        break;
      case 5:
        determinedBorder =
            Border(left: _borderSide, bottom: _borderSide, top: _borderSide);
        break;
      case 6:
        determinedBorder = Border(right: _borderSide, top: _borderSide);
        break;
      case 7:
        determinedBorder =
            Border(left: _borderSide, top: _borderSide, right: _borderSide);
        break;
      case 8:
        determinedBorder = Border(left: _borderSide, top: _borderSide);
        break;
    }

    return determinedBorder;
  }
}

Utilizzando la logica dell'algoritmo descritta nella prima parte, se avviamo l'applicazione, otteniamo un risultato come questo:

Conclusioni

L'algoritmo Minimax è davvero "bravo" a giocare. In tutte le prove che ho fatto non sono mai riuscito a batterlo, raggiungendo al massimo un pareggio. Magari si potrebbe ragionare nel limitarne l'efficacia riducendo la profondità di scansione, ma questo potrebbe essere un argomento per un prossimo articolo.

Come per gli articoli precedenti potete trovare il codice completo tra le mie repo GitHub: https://github.com/luigimicco/flutter_minimax_ttt.

Il blog di Luigi Micco

Cerca nel blog