Creating an Unbeatable Tic Tac Toe Game Using Minimax Algorithm with Alpha-Beta Pruning in Flutter
Tic Tac Toe is one of the old-school pen-and-paper games that most of us have played as a child. I remember playing with friends by drawing all over our benches and textbooks while our teacher was still teaching. The benches used to be full of tictactoe boxes and all of us used to have tricks of our own to beat one another. In this tutorial, we’re gonna have a closer look at that game and also build it using Flutter Casual Games Toolkit.
Tic-Tac-Toe is the 2 player turn based game where each player chooses one of the marks (X or O) and puts their marks alternatively on the given board and the first player to place 3(for 3X3 tictactoe board) of their marks consecutively in a horizontal, vertical, or diagonal row is the winner.
Here’s the summary of what we are going to cover in this tutorial.
- Design the
mxntic-tac-toe board and derive the winning logic - Multiplayer mode: 2 players can play with each other
- Single Player Mode: Players can play with AI. We’ll have 3 levels of difficulty. The initial levels will be easier where AI will choose the random moves. The mid-levels will be slightly difficult when AI starts to make the move logically. The final levels will be very difficult and unbeatable(for 3X3 tictactoe) for which we will use the minimax algorithm with alpha-beta pruning.
- AI vs AI Simulation: In this mode, we’ll create a gameplay simulation where 2 AIs are selected randomly, and a match is played between them.
I will be using Flutter Casual Games Toolkit as the starting point of this tutorial. You can get it from this link and also check out its official website. You can also get the starting repository by forking from this link. In this written tutorial, I’m only going to cover the key steps. If you want the step-by-step tutorial then you can check out the video tutorial above.
The games template consists of five screens as shown in the figure above. It starts with the main menu screen from which we can go to the level selection screen to choose the level of the game to play in the game session screen. The game session screen consists of the slider and to win the game we just have the slide the slider by the amount as defined by the level after which the winning screen is displayed. It also has a setting screen from which the configuration of the game can be changed. It uses the GOROUTER packages to route to different screens.
Update the text in the main menu screen from “Flutter Game Template!” to “Tic Tac Toe” and also add another button with the text “Versus Mode” that will take the user to the versus mode.
Update the game session screen with three sections, the top header will contain the action buttons, the midsection will have the tictactoe game board, and the bottom section will have the restart button.
Update the route to the level selection screen to support the URL for the multiplayer and the single-player mode.
...
GoRoute(
path: 'play/:mode',
redirect: (BuildContext context, GoRouterState state) =>
state.params["mode"] == "single" ||
state.params["mode"] == "vs"
? null
: "/play/single",
pageBuilder: (context, state) => buildTransition<void>(
child: LevelSelectionScreen(
isVsMode: state.params['mode'] == "vs",
key: Key('level selection')),
color: context.watch<Palette>().text,
),
routes: [
GoRoute(
path: 'session/:level',
pageBuilder: (context, state) {
final levelNumber = int.parse(state.params['level']!);
final isVsMode = state.params["mode"] == "vs";
return buildTransition<void>(
child: PlaySessionScreen(
levelNumber,
key: const Key('play session'),
),
color: context.watch<Palette>().backgroundMain,
);
},
),
...
])
...
Now use a GridBuilder widget to build the 3X3 game board.
GridView.builder(
shrinkWrap: true,
physics: ClampingScrollPhysics(),
padding: EdgeInsets.zero,
gridDelegate: SliverGridDelegateWithFixedCrossAxisCount(
crossAxisCount: 3, crossAxisSpacing: 4, mainAxisSpacing: 4),
itemCount: 9,
itemBuilder: (context, index) => Container(
color: Colors.blueGrey,
child: Text("$index")
)),The above will represent each of the tiles with an index position. Instead of that, we’ll represent them in an XY-plane so that the calculation becomes easier later. Make the following changes:
Text("(${index%3}, ${index%3})")
Now let's try to represent the board in the m*n form, where m and n are greater than 3. Create a modal class Tile and widget BoardTile.
class Tile{
final int x;
final int y;
Tile(this.x, this.y);
@override
String toString() => 'Tile<$x:$y>';
@override
bool operator ==(Object other) {
return other is Tile && other.x == x && other.y == y;
}
@override
int get hashCode => Object.hash(x, y);
}
class BoardTile extends StatelessWidget {
final Tile tile;
const BoardTile({Key? key, required this.tile}) : super(key: key);
@override
Widget build(BuildContext context) {
return InkWell(onTap: () {}, child: Center(child: Text(tile.toString())));
}
}Read 2 parameters m and n from the parameters and update the grid builder in the main_board_session.dart file as:
GridView.builder(
shrinkWrap: true,
physics: ClampingScrollPhysics(),
padding: EdgeInsets.zero,
gridDelegate: SliverGridDelegateWithFixedCrossAxisCount(
crossAxisCount: m,
crossAxisSpacing: 4,
mainAxisSpacing: 4),
itemCount: m * n,
itemBuilder: (context, index) => BoardTile(
tile: Tile(index % m, index ~/ n),
))
The separating lines are gone since we removed the container which had the background color. We’ll use a custom painter to draw the separating lines.
Let's do some calculations and compute the horizontal and vertical lines of the Tic Tac toe board.
Now using the Custom Painter class and Custom Paint widget, create a BoardLines widget with the following contents.
class BoardLines extends StatelessWidget {
final int m;
final int n;
const BoardLines({Key? key, required this.m, required this.n})
: super(key: key);
@override
Widget build(BuildContext context) {
final palette = context.watch<Palette>();
return RepaintBoundary(
child: CustomPaint(
painter: GamesLinesPainter(m, n, lineColor: palette.ink),
));
}
}
class GamesLinesPainter extends CustomPainter {
final int m;
final int n;
final Color lineColor;
late final pathPaint = Paint()
..colorFilter = ColorFilter.mode(lineColor, BlendMode.srcIn);
GamesLinesPainter(this.m, this.n, {this.lineColor = Colors.black});
@override
void paint(Canvas canvas, Size size) {
const padding = 10.0;
pathPaint.strokeWidth = 8;
//draw horizontal lines
final heightStep = size.height / n;
for (int i = 1; i < n; i++) {
canvas.drawLine(Offset(padding, i * heightStep),
Offset(size.width - padding, i * heightStep), pathPaint);
}
//draw vertical lines
final widthStep = size.width / m;
for (int i = 1; i < m; i++) {
canvas.drawLine(Offset(i * widthStep, padding),
Offset(i * widthStep, size.height - padding), pathPaint);
}
}
@override
bool shouldRepaint(covariant GamesLinesPainter oldDelegate) {
return oldDelegate.m != m ||
oldDelegate.n != n ||
oldDelegate.lineColor != lineColor;
}
}
Following a similar approach, create a widget to draw the winning line also. Creating the winning line is a bit trickier, as we have to compute the starting point of the first tile and the ending point of the last tile to draw the line.
class WinningLines extends StatelessWidget {
final int m;
final int n;
final Tile tile1;
final Tile tile2;
const WinningLines(
{Key? key,
required this.m,
required this.n,
required this.tile1,
required this.tile2})
: super(key: key);
@override
Widget build(BuildContext context) {
final palette = context.watch<Palette>();
return RepaintBoundary(
child: CustomPaint(
painter: WinningLinesPainter(m, n, lineColor: palette.redPen, tile1, tile2),
));
}
}
class WinningLinesPainter extends CustomPainter {
final int m;
final int n;
final Color lineColor;
final Tile tile1;
final Tile tile2;
late final pathPaint = Paint()
..colorFilter = ColorFilter.mode(lineColor, BlendMode.srcIn);
WinningLinesPainter(this.m, this.n, this.tile1, this.tile2,
{this.lineColor = Colors.black});
@override
void paint(Canvas canvas, Size size) {
const padding = 10.0;
pathPaint.strokeWidth = 8;
final heightStep = size.height / n;
final widthStep = size.width / m;
final adjustX = widthStep - padding;
final adjustY = heightStep - padding;
final p1 = Offset(
(tile1.x * widthStep) +
(tile1.x == tile2.x
? widthStep / 2
: tile1.x > tile2.x
? adjustX
: padding),
(tile1.y * heightStep) +
(tile1.y == tile2.y
? heightStep / 2
: tile1.y >= tile2.y
? adjustY
: padding));
final p2 = Offset(
(tile2.x * widthStep) +
(tile1.x == tile2.x
? widthStep / 2
: tile2.x >= tile1.x
? adjustX
: padding),
(tile2.y * heightStep) +
(tile1.y == tile2.y
? heightStep / 2
: tile2.y >= tile1.y
? adjustY
: padding));
canvas.drawLine(p1, p2, pathPaint);
}
@override
bool shouldRepaint(covariant WinningLinesPainter oldDelegate) {
return oldDelegate.m != m ||
oldDelegate.n != n ||
oldDelegate.tile1 != tile1 ||
oldDelegate.tile2 != tile2 ||
oldDelegate.lineColor != lineColor;
}
}Finally, use the above widgets in the main_board_session.dart widget to draw the board and winning lines.
@override
Widget build(BuildContext context) {
return AspectRatio(
aspectRatio: m / n,
child: Stack(
fit: StackFit.expand,
children: [
BoardLines(m: m, n: n),
WinningLines(m: m, n: n, tile1: Tile(0,0), tile2: Tile(2,2)),
WinningLines(m: m, n: n, tile1: Tile(0,0), tile2: Tile(0,2)),
WinningLines(m: m, n: n, tile1: Tile(0,0), tile2: Tile(2,0)),
GridView.builder(
shrinkWrap: true,
physics: ClampingScrollPhysics(),
padding: EdgeInsets.zero,
gridDelegate: SliverGridDelegateWithFixedCrossAxisCount(
crossAxisCount: m, crossAxisSpacing: 4, mainAxisSpacing: 4),
itemCount: m * n,
itemBuilder: (context, index) => BoardTile(
tile: Tile(index % m, index ~/ n),
)),
],
),
);
}
We now have the tic tac toe board of mxn form in which each tile can be clicked from where the event is triggered. And based on the click events we can start the game.
We’ll be using ChangeNotifier as the state management technique with the provider package which is already there in this game template repository.
Create the following enum and setting class that contains the options needed in the tic tac toe game and the board setting configuration respectively.
enum Side { X, O, NONE }
// import 'package:tictactoe/src/ai/ai_opponent.dart';
import 'package:tictactoe/src/game_internals/enums.dart';
class BoardSetting {
final int m; // size of the board
final int n; // size of the board
final int k; // number of combinations needed to win the game
final int? gameId; // id to link the game
final Side playerSide; // Side the first player is using
final bool opponentStarts; // boolean to indicate who starts the game
// final AiOpponent? aiOpponent; // store the AI that the player is competing against // we'll uncomment this later when building vs AI mode
// we'll get to this when adding ai opponent
bool get isAiPlaying => false;
// bool get isAiPlaying => aiOpponent != null;
const BoardSetting(this.m, this.n, this.k,
{bool playerIsX = true,
this.opponentStarts = false,
this.gameId,
// this.aiOpponent
})
: this.playerSide = playerIsX ? Side.X : Side.O;
const BoardSetting.defaultBoard() : this(3, 3, 3);
Side get opponentSide => playerSide == Side.X ? Side.O : Side.X;
@override
bool operator ==(Object other) {
return other is BoardSetting &&
other.m == m &&
other.n == n &&
other.opponentStarts == opponentStarts &&
other.playerSide == playerSide &&
other.gameId == gameId;
}
@override
int get hashCode => Object.hash(m, n, k, opponentStarts, playerSide, gameId);
}Next, create the board state class and extend it with the change notifier class. Most of the game logic will revolve around this class.
We’ll store the moves made by the players as the key-value pair of the Tile and Side enum class.
Map<Tile, Side> _moves = {};{Tile<0, 0>: SIDE.X, Tile<0, 2>: SIDE.O} indicates that option X is placed at the tile position <0,0> and option O is placed at <0,2>.
Then we can get the value at the given tile position by using the function.
String getValueAt(Tile tile) => moves[tile]?.name ?? "";Since it's a turn-based game we can know the current turn by checking the total number of moves made is even is odd. If it's even, then it's the turn of the player that started first.
Side get currentTurn => _moves.length % 2 == 0
? (setting.opponentStarts ? setting.opponentSide : setting.playerSide)
: (setting.opponentStarts ? setting.playerSide : setting.opponentSide);The current turn also depends on who started the game and the option the players are using which are stored in the board setting class. So add it to the state as well and create a new function to instantiate the state class with setting as the parameter.
final BoardSetting setting;
BoardState._(this.setting);
BoardState.new(BoardSetting setting) : this._(setting);Add some more variables as follows to this class for various purposes mentioned below.
// to lock and unlock the board. Sometimes the calculations may take a long
// time. So we might want to lock the board to avoid unexpected errors
bool _isLocked = true;
bool get isLocked => _isLocked;
// store the start and end tile to display the winning line
List winnerLines = [];
// store all the tiles in the winning combinations
List winCombos = [];
// boolean to know if the game has started
bool get hasGameStarted => _moves.length > 0;
bool get isAiPlaying => setting.isAiPlaying;
// value notifier to indicate the end of the game(either win or draw)
final ValueNotifier<Side?> gameResult = ValueNotifier<Side?>(null);
// know if the given tile can be occupied or taken
bool canOccupyTile(Tile tile) =>
_moves[tile] == Side.NONE || _moves[tile] == null;
// function to initialize the board
void initializeBoard() {
_isLocked = false;
notifyListeners();
}
// function to clear the board
void clearBoard() {
_moves.clear();
winnerLines.clear();
winCombos.clear();
initializeBoard();
}
@override
void dispose() {
gameResult.dispose();
super.dispose();
}
// know if there is the draw
bool get isGameDraw => _moves.length == setting.m * setting.n;
// function to check if player 1 is the winner
bool get isPlayer1Winner => setting.playerSide == gameResult.value;
bool hasSomeoneWon(Tile tile, Side currentSide, {checkOnly = false}) {
//todo implement winning logic
return false;
}We can then occupy the tile by using the following function.
void occupyTile(Tile tile) {
final _turn = currentTurn;
// claim the tile
_moves = {...moves, tile: _turn};
_isLocked = true;
notifyListeners();
bool hasWinner = hasSomeoneWon(tile, _turn);
// after claiming the tile, check if the game ends
// or can be played next by another player
if (hasWinner) {
//someone wins
gameResult.value = _turn;
gameResult.notifyListeners();
} else if (isGameDraw) {
//game is draw
gameResult.value = Side.NONE;
gameResult.notifyListeners();
} else if (isAiPlaying && !isAiMove) {
//make the move for ai if playing against Ai
} else {
//continue the game
_isLocked = false;
notifyListeners();
}
}Instead of looping through all the tiles of the board to check for the win, we’ll only check the win from where the user placed their move. From that position, we have to check in all possible directions from where the win is possible. We’ll loop to k-1 only because one match is the currently placed tile which must also be considered for the correct logic.
For the vertical case, run a loop up to k-1 and check both upwards and downwards using the two-pointer method unless there is a mismatch. If it matches up to the count needed for the win then, we have a win and then we’ll move to check if there is a match in another direction. We can stop here if there is a win, but we also might want to show the user the winning combinations in another direction. There is the parameter checkOnly that is used to check the win only, which we’ll use when being called from the Ai, and in that case, we do not want the state variables to change. If checkOnly is set to true, we can also skip the remaining direction if we found the win in one direction.
int _winningCount = 0;
bool _hasWinner = false;
List _tempWinCombos = [];
Tile _startTile = tile;
Tile _endTile = tile;
bool _mismatchTop = false;
bool _mismatchBottom = false;
//check for vertical lines
for (int i = 1; i < setting.k; i++) {
//check downwards
final downwardTile = Tile(tile.x, tile.y - i);
if (_moves[downwardTile] == currentSide && !_mismatchTop) {
_winningCount++;
_startTile = downwardTile;
_tempWinCombos.add(downwardTile);
}else{
_mismatchTop = true;
}
//check upwards
final upwardTile = Tile(tile.x, tile.y + i);
if (_moves[upwardTile] == currentSide && !_mismatchBottom) {
_winningCount++;
_endTile = upwardTile;
_tempWinCombos.add(_endTile);
}else{
_mismatchBottom = true;
}
if(_mismatchTop && _mismatchBottom){
break;
}
if (_winningCount >= setting.k - 1) {
if(checkOnly){
return true;
}
_hasWinner = true;
winnerLines = [
...winnerLines,
[_startTile, _endTile]
];
winCombos.addAll(_tempWinCombos);
winCombos.add(tile);
break;
}
}
Include the case for the horizontal and diagonal directions in the above winning logic.
bool hasSomeoneWon(Tile tile, Side currentSide, {checkOnly = false}) {
int _winningCount = 0;
bool _hasWinner = false;
List _tempWinCombos = [];
Tile _startTile = tile;
Tile _endTile = tile;
bool _mismatchTop = false;
bool _mismatchBottom = false;
//check for vertical lines
for (int i = 1; i < setting.k; i++) {
//check downwards
final downwardTile = Tile(tile.x, tile.y - i);
if (_moves[downwardTile] == currentSide && !_mismatchTop) {
_winningCount++;
_startTile = downwardTile;
_tempWinCombos.add(downwardTile);
}else{
_mismatchTop = true;
}
//check upwards
final upwardTile = Tile(tile.x, tile.y + i);
if (_moves[upwardTile] == currentSide && !_mismatchBottom) {
_winningCount++;
_endTile = upwardTile;
_tempWinCombos.add(_endTile);
}else{
_mismatchBottom = true;
}
if(_mismatchTop && _mismatchBottom){
break;
}
if (_winningCount >= setting.k - 1) {
if(checkOnly){
return true;
}
_hasWinner = true;
winnerLines = [
...winnerLines,
[_startTile, _endTile]
];
winCombos.addAll(_tempWinCombos);
winCombos.add(tile);
break;
}
}
_startTile = tile;
_endTile = tile;
_winningCount = 0;
_tempWinCombos.clear();
_mismatchTop = false;
_mismatchBottom = false;
//check for horizontal lines
for (int i = 1; i < setting.k; i++) {
//check left
final downwardTile = Tile(tile.x - i, tile.y);
if (_moves[downwardTile] == currentSide && !_mismatchTop) {
_winningCount++;
_startTile = downwardTile;
_tempWinCombos.add(downwardTile);
}else{
_mismatchTop = true;
}
//check right
final upwardTile = Tile(tile.x + i, tile.y);
if (_moves[upwardTile] == currentSide && !_mismatchBottom) {
_winningCount++;
_endTile = upwardTile;
_tempWinCombos.add(_endTile);
}else{
_mismatchBottom = true;
}
if(_mismatchTop && _mismatchBottom){
break;
}
if (_winningCount >= setting.k - 1) {
if(checkOnly){
return true;
}
_hasWinner = true;
winnerLines = [
...winnerLines,
[_startTile, _endTile]
];
winCombos.addAll(_tempWinCombos);
winCombos.add(tile);
break;
}
}
_startTile = tile;
_endTile = tile;
_winningCount = 0;
_tempWinCombos.clear();
_mismatchTop = false;
_mismatchBottom = false;
//check for diagonal lines: type1
for (int i = 1; i < setting.k; i++) {
//check upper left
final downwardTile = Tile(tile.x - i, tile.y + i);
if (_moves[downwardTile] == currentSide && !_mismatchTop) {
_winningCount++;
_startTile = downwardTile;
_tempWinCombos.add(downwardTile);
}else{
_mismatchTop = true;
}
//check downward right
final upwardTile = Tile(tile.x + i, tile.y - i);
if (_moves[upwardTile] == currentSide && !_mismatchBottom) {
_winningCount++;
_endTile = upwardTile;
_tempWinCombos.add(_endTile);
}else{
_mismatchBottom = true;
}
if(_mismatchTop && _mismatchBottom){
break;
}
if (_winningCount >= setting.k - 1) {
if(checkOnly){
return true;
}
_hasWinner = true;
winnerLines = [
...winnerLines,
[_startTile, _endTile]
];
winCombos.addAll(_tempWinCombos);
winCombos.add(tile);
break;
}
}
_startTile = tile;
_endTile = tile;
_winningCount = 0;
_tempWinCombos.clear();
_mismatchTop = false;
_mismatchBottom = false;
//check for diagonal lines: Type2
for (int i = 1; i < setting.k; i++) {
//check bottom left
final downwardTile = Tile(tile.x - i, tile.y - i);
if (_moves[downwardTile] == currentSide && !_mismatchTop) {
_winningCount++;
_startTile = downwardTile;
_tempWinCombos.add(downwardTile);
}else{
_mismatchTop = true;
}
//check top right
final upwardTile = Tile(tile.x + i, tile.y + i);
if (_moves[upwardTile] == currentSide && !_mismatchBottom) {
_winningCount++;
_endTile = upwardTile;
_tempWinCombos.add(_endTile);
}else{
_mismatchBottom = true;
}
if(_mismatchTop && _mismatchBottom){
break;
}
if (_winningCount >= setting.k - 1) {
if(checkOnly){
return true;
}
_hasWinner = true;
winnerLines = [
...winnerLines,
[_startTile, _endTile]
];
winCombos.addAll(_tempWinCombos);
winCombos.add(tile);
break;
}
}
return _hasWinner;
}The above code is in unoptimized form, it has repetitive portions that can be removed. I’ll not go on to optimize this portion, you can try yourself to optimize it. With this winning logic done, let's proceed to create the versus mode where two players can compete with each other.
Update the board tile widget to add the click events and display the options properly.
import 'package:flutter/material.dart';
import 'package:provider/provider.dart';
import 'package:tictactoe/src/game_internals/board_state.dart';
import 'package:tictactoe/src/game_internals/tile.dart';
import 'package:tictactoe/src/style/palette.dart';
class BoardTile extends StatelessWidget {
final Tile tile;
const BoardTile({Key? key, required this.tile}) : super(key: key);
@override
Widget build(BuildContext context) {
final tileValue =
context.select((BoardState state) => state.getValueAt(tile));
final List winningCombos =
context.select((BoardState state) => state.winCombos);
final _isInWinningCombo = winningCombos.contains(tile);
final _palette = context.read<Palette>();
return InkWell(
onTap: () {
final _state = context.read<BoardState>();
if (!_state.isLocked && _state.canOccupyTile(tile)) {
_state.occupyTile(tile);
}
},
child: Center(
child: AnimatedScale(
scale: _isInWinningCombo ? 1.5 : 1,
duration: const Duration(milliseconds: 300),
child: Text(
tileValue,
style: _isInWinningCombo
? TextStyle(
fontSize: 40,
color: _palette.redPen,
fontWeight: FontWeight.bold)
: TextStyle(fontSize: 40),
),
)));
}
}When choosing the versus option in the main menu screen, the player will be redirected to the level selection screen. On this screen, we have to write some logic to distinguish between the versus mode and the single-play mode and display the UI accordingly. For versus mode, we’ll display some game configurations which the player can select to play with that configuration.
Create game_map.dart modal class with the following contents.
import 'package:tictactoe/src/game_internals/board_setting.dart';
class GameMap{
final int id;
final BoardSetting setting;
const GameMap(this.id, this.setting);
}
const gameMaps = [
GameMap(1, BoardSetting(3, 3, 3, gameId: 1)),
GameMap(2, BoardSetting(4, 4, 3, gameId: 2)),
GameMap(3, BoardSetting(4, 4, 4, gameId: 3)),
GameMap(4, BoardSetting(5, 5, 4, gameId: 4)),
];Also modify the game levels class as:
class GameLevel {
final int id;
final int difficulty;
final BoardSetting setting;
const GameLevel({
required this.id,
required this.setting,
required this.difficulty,
});
}
const gameLevels = [];Update the route configuration for the level selection, game session, and win game screen.
GoRoute(
path: 'play/:mode',
redirect: (BuildContext context, GoRouterState state) =>
state.params["mode"] == "single" ||
state.params["mode"] == "vs"
? null
: "/play/single",
pageBuilder: (context, state) => buildMyTransition<void>(
child: LevelSelectionScreen(
isVsMode: state.params['mode'] == "vs",
key: Key('level selection')),
color: context.watch<Palette>().backgroundLevelSelection,
),
routes: [
GoRoute(
path: 'session/:level',
pageBuilder: (context, state) {
final levelNumber = int.parse(state.params['level']!);
final isVsMode = state.params["mode"] == "vs";
late final BoardSetting setting;
if (isVsMode) {
setting = gameMaps
.firstWhereOrNull(
(element) => element.id == levelNumber)
?.setting ??
BoardSetting.defaultBoard();
} else {
//todo fix this:: handle properly for the cases when the level doesnot exist and cannot play the level yet
setting = gameLevels
.firstWhereOrNull(
(element) => element.id == levelNumber)
?.setting ??
BoardSetting.defaultBoard();
}
return buildMyTransition<void>(
child: PlaySessionScreen(
setting,
key: const Key('play session'),
),
color: context.watch<Palette>().backgroundPlaySession,
);
},
),
GoRoute(
path: 'won',
pageBuilder: (context, state) {
final map = state.extra! as Map<String, dynamic>;
final BoardSetting setting =
map["setting"] is BoardSetting
? map["setting"] as BoardSetting
: BoardSetting.defaultBoard();
final resultMessage = map["message"] is String
? map["message"]
: "Game is interrupted";
return buildMyTransition<void>(
child: WinGameScreen(
message: resultMessage,
setting: setting,
key: const Key('win game'),
),
color: context.watch<Palette>().backgroundPlaySession,
);
},
)
]),In the level selection screen widget, add a parameter isVsMode and use it to display the UI accordingly.
...
final bool isVsMode;
const LevelSelectionScreen({super.key, this.isVsMode = false});
...
Text(
isVsMode ? "Vs Mode" : "Vs AI",
style:
TextStyle(fontFamily: 'Permanent Marker', fontSize: 30),
)
...Also, use the grid builder to display the list of maps or the levels as per the game mode.
Expanded(
child: isVsMode
? GridView.builder(
gridDelegate: SliverGridDelegateWithFixedCrossAxisCount(
crossAxisCount: 2,
mainAxisSpacing: 2,
crossAxisSpacing: 2),
itemCount: gameMaps.length,
itemBuilder: (context, index) =>
MapSelectionCard(gameMaps[index]))
: GridView.builder(
gridDelegate: SliverGridDelegateWithFixedCrossAxisCount(
crossAxisCount: 3,
mainAxisSpacing: 10,
crossAxisSpacing: 10),
itemCount: gameLevels.length,
itemBuilder: (context, index) =>
LevelSelectionCard(gameLevels[index])))MMapSelectionCard is a simple widget that displays the game map with the win configurations with the following contents.
import 'package:flutter/material.dart';
import 'package:go_router/go_router.dart';
import 'package:provider/provider.dart';
import 'package:tictactoe/src/level_selection/game_map.dart';
import 'package:tictactoe/src/play_session/board_lines.dart';
import 'package:tictactoe/src/style/palette.dart';
class MapSelectionCard extends StatelessWidget {
final GameMap map;
const MapSelectionCard(this.map, {Key? key}) : super(key: key);
onClick(BuildContext context) {
GoRouter.of(context).go("/play/vs/session/${map.id}");
}
@override
Widget build(BuildContext context) {
final palette = context.watch<Palette>();
return InkWell(
onTap: ()=>onClick(context),
child: Stack(
children: [
Padding(
padding: const EdgeInsets.all(20.0),
child: AspectRatio(
aspectRatio: 1,
child: BoardLines(m: map.setting.m, n: map.setting.n)),
),
Align(
alignment: Alignment.center,
child: Container(
padding: EdgeInsets.all(3),
decoration: BoxDecoration(color: palette.trueWhite, borderRadius: BorderRadius.circular(6)),
child: Text(
"${map.setting.m} X ${map.setting.n}",
style:
TextStyle(color: palette.redPen, fontWeight: FontWeight.bold),
),
),
),
Align(
alignment: Alignment.bottomCenter,
child: Text(
"match ${map.setting.k} tiles",
style:
TextStyle(color: palette.ink, fontWeight: FontWeight.bold),
),
)
],
),
);
}
}Similarly, LevelSelectionCard consists of a simple card design with a level number on it, and clicking it will allow the players to play at that particular level.
import 'package:flutter/material.dart';
import 'package:go_router/go_router.dart';
import 'package:provider/provider.dart';
import 'package:tictactoe/src/level_selection/levels.dart';
import 'package:tictactoe/src/style/palette.dart';
class LevelSelectionCard extends StatelessWidget {
final GameLevel level;
const LevelSelectionCard(this.level, {Key? key}) : super(key: key);
onClick(BuildContext context) {
GoRouter.of(context).go("/play/single/session/${level.id}");
}
@override
Widget build(BuildContext context) {
final palette = context.watch<Palette>();
return InkWell(
onTap: () => onClick(context),
child: Container(
decoration: BoxDecoration(color: palette.trueWhite, borderRadius: BorderRadius.circular(6)),
padding: const EdgeInsets.all(20.0),
child: Center(
child: Text(
"${level.id}",
style: TextStyle(
fontWeight: FontWeight.bold, fontSize: 60, color: palette.redPen, ),
),
),
),
);
}
}In the play session screen widget, add a parameter for BoardSetting class and also initialize the instance of the board state using the change notifier provider class.
...
final BoardSetting setting;
const PlaySessionScreen(this.setting, {super.key});
...Instantiate the state class as:
...
ChangeNotifierProvider(create: (context) {
final state = BoardState.new(widget.setting)..initializeBoard();
state.gameResult.addListener(() => _onGameComplete(state));
return state;
}),
...
Future<void> _onGameComplete(BoardState state) async {
await Future<void>.delayed(_preCelebrationDuration);
final isGameDraw = state.gameResult.value == Side.NONE;
if (isGameDraw) {
GoRouter.of(context).go("/play/vs/won", extra: {
"message": "Game Finished. It's a draw",
"setting": widget.setting
});
} else {
if (!mounted) return;
setState(() {
_duringCelebration = true;
});
final audioController = context.read<AudioController>();
audioController.playSfx(SfxType.congrats);
/// Give the player some time to see the celebration animation.
await Future<void>.delayed(_celebrationDuration);
if (!mounted) return;
final _settings = context.read<SettingsController>();
GoRouter.of(context).go('/play/${widget.setting.isAiPlaying ? 'single':'vs'}/won', extra: {
"message":
"${state.isPlayer1Winner ? _settings.playerName.value : widget.setting.isAiPlaying ? "Ai":"player2"} wins",
"setting": widget.setting
});
}
}
_onGameComplete is the function that will get executed when the match is won or drawn meaning the game has been completed in which case the winning screen is displayed with the suitable message.
The versus mode is now completed and the players can select this mode and choose from the available map to initiate the match between 2 players.
Modify the win game screen widget to display the message and restart button.
class WinGameScreen extends StatelessWidget {
final String message;
final BoardSetting setting;
const WinGameScreen({
super.key,
required this.message,
required this.setting,
});
@override
Widget build(BuildContext context) {
final palette = context.watch<Palette>();
const gap = SizedBox(height: 10);
return Scaffold(
backgroundColor: palette.backgroundPlaySession,
body: ResponsiveScreen(
squarishMainArea: Column(
mainAxisAlignment: MainAxisAlignment.center,
children: <Widget>[
gap,
Center(
child: Text(
message,
style: TextStyle(fontFamily: 'Permanent Marker', fontSize: 50),
),
),
],
),
rectangularMenuArea: InkResponse(
onTap: () {
GoRouter.of(context).go(
'/play/${setting.isAiPlaying ? 'single' : 'vs'}/session/${setting.gameId}',
extra: setting);
},
child: Image.asset(
'assets/images/restart.png',
),
),
),
);
}
}Next on our list is the vs AI mode and to begin with let's create an abstract class AIOpponent to represent the AI with one function that will be used to decide its next move.
abstract class AiOpponent{
const AiOpponent();
Tile chooseNextMove(BoardState state);
}Then create the random opponent class which is the 1st level opponent and is very easy to beat. All it does is use the random function to select from the list of available moves.
class RandomOpponent extends AiOpponent {
const RandomOpponent();
static final Random _random = Random();
@override
Tile chooseNextMove(BoardState state) {
final options = <Tile>[];
for (int x = 0; x < state.setting.m; x++) {
for (int y = 0; y < state.setting.n; y++) {
final tile = Tile(x, y);
if (state.canOccupyTile(tile)) {
options.add(tile);
}
}
}
return options[_random.nextInt(options.length)];
}
}Next, create another opponent Thinking Opponent which uses some logic to decide its next move. First of all, it checks if there is a move that can win the game. If so it makes that move to win the game. And if not it checks if there is a move through which the opponent can win in its next turn. If it finds that move then it will select that particular move to restrict the opponent from winning the game. And if it does not find the move with both above-mentioned cases then it will choose randomly from the available move.
import 'dart:math';
import 'package:tictactoe/src/ai/ai_opponent.dart';
import 'package:tictactoe/src/game_internals/board_state.dart';
import 'package:tictactoe/src/game_internals/enums.dart';
import 'package:tictactoe/src/game_internals/tile.dart';
class ThinkingOpponent extends AiOpponent {
const ThinkingOpponent();
static final Random _random = Random();
@override
Tile chooseNextMove(BoardState state) {
final options = <Tile>[];
for (int x = 0; x < state.setting.m; x++) {
for (int y = 0; y < state.setting.n; y++) {
final tile = Tile(x, y);
if (state.canOccupyTile(tile)) {
options.add(tile);
}
}
}
//check for the AI win
Side _aiSide = state.currentTurn;
for(int i=0;i<options.length;i++){
if(state.hasSomeoneWon(options[i], _aiSide, checkOnly: true)){
return options[i];
}
}
//check for the player win to block the win if found
Side _playerSide = _aiSide == Side.X ? Side.O:Side.X;
for(int i=0;i<options.length;i++){
if(state.hasSomeoneWon(options[i], _playerSide, checkOnly: true)){
return options[i];
}
}
//choose random move
return options[_random.nextInt(options.length)];
}
}Now add an entry of AIOpponent class to the board setting the modal class to introduce AI opponents to the game configuration.
class BoardSetting {
...
final AiOpponent? aiOpponent; // store the AI that the player is competing against // we'll uncomment this later when building vs AI mode
bool get isAiPlaying => aiOpponent != null;
...
}Modify the board state class to include the case where the AI makes its first move and also makes its move after the player is done making their move.
class BoardState extends ChangeNotifier {
....
void initializeBoard() {
_isLocked = false;
//make the first move for Ai when playing against Ai and it starts first
if(setting.isAiPlaying && setting.opponentStarts){
_moves.addAll({Tile(setting.m~/2, setting.n~/2): currentTurn});
// OR use the chooseNextMove to decide the AIs next move
// occupyTile(setting.aiOpponent!.chooseNextMove(this), isAiMove: true);
}
notifyListeners();
}
void occupyTile(Tile tile, {bool isAiMove = false}) {
...
else if (isAiPlaying && !isAiMove) {
//make the move for ai if playing against Ai
occupyTile(setting.aiOpponent!.chooseNextMove(this), isAiMove: true);
}
...
}
....
}For the AI's first move, it selects the middle tile. Instead of the middle tile, we can also utilize the AIs chooseNextMove to compute the move as occupyTile(setting.aiOpponent!.chooseNextMove(this), isAiMove: true);.
In levels.dart file add the following entries to the list of game levels.
const gameLevels = [
GameLevel(
id: 1,
difficulty: 5,
setting: BoardSetting(3, 3, 3, gameId: 1, aiOpponent: RandomOpponent()),
),
GameLevel(
id: 2,
difficulty: 42,
setting: BoardSetting(3, 3, 3,
gameId: 2, aiOpponent: RandomOpponent(), opponentStarts: true)),
GameLevel(
id: 3,
setting: BoardSetting(4, 4, 3,
gameId: 3, aiOpponent: RandomOpponent(), opponentStarts: true),
difficulty: 100,
),
GameLevel(
id: 4,
setting: BoardSetting(3, 3, 3, gameId: 4, aiOpponent: ThinkingOpponent()),
difficulty: 200,
),
GameLevel(
id: 5,
setting: BoardSetting(3, 3, 3,
gameId: 5, aiOpponent: ThinkingOpponent(), opponentStarts: true),
difficulty: 300,
),
GameLevel(
id: 6,
setting: BoardSetting(4, 4, 3,
gameId: 6, aiOpponent: ThinkingOpponent(), opponentStarts: true),
difficulty: 400,
)
];If we run the game, then we’ll have the option to play against AI. The first three levels are very easier with AI choosing random moves. The last three levels are slightly competitive as it chooses the move logically. The question here is, can you beat this AI? The answer is YES. If you had played the game, you might as well have beaten the second AI, but how? Let’s break down 3X3 tictactoe so that we can answer the above question logically.
If 2 players play the 3X3 version of this game, then no one can win. The game will always end up in a draw. But there are certain states on the board through which a win is guaranteed.
Consider the above case where it’s the turn of O to place the move. But there are two positions that it should place the move so that it can restrict X from winning. But it can only take 1 place at a time meaning X can win the game. In order to win, the players can bring the situations like above in their favor. Consider the following example:
In the above example, if X places the move at the center tile then the best move for O to make would be at the corners through which the game can be drawn. And if it places at the mid tiles, then X can lead up to the double win condition through which a win is guaranteed for X. There are many scenarios like these that can lead up to the double win condition. The ThinkingOpponent Ai cannot avoid this situation, which the players can exploit to win against it.
We’ll now proceed to develop the next AI which is smart enough to avoid all those cases that can lead up to the players winning. In a 3x3 tictactoe, the players cannot beat this AI, the best bet for them is to draw the game. And for that, we’ll be using the Minimax algorithm with alpha-beta pruning for the optimization.
Minimax algorithm
It’s a back-tracking algorithm that uses the recursive approach to find the optimal move which can be used in a turn-based game like tic-tac-toe, chess, etc. By using this algorithm, the AI will play every possible move from the given match state and choose the optimal move. By following this approach, AI can always win if that is possible of course.
Let's consider the following state where X is trying to make its move. There are 3 places where X can make the move.
It's clear from the above picture that if X chose the third option, it can win the game. So the optimal move for X to make is the third option, but X needs to decide that programmatically. For that X plays every possible move for both itself and the opponent. By doing so, X can know which move is best for it to win.
The above figure shows every result that can take place from the X’s turn. The first option yields a draw or a win, the second option yields a draw or loss which is definitely a bad choice than before and the final option guarantees the win for X, so the optimal move to make is the third option.
In the minimax algorithm, one player is termed a maximizer while another player is a minimizer. The maximum player chooses the maximum value and the minimum player chooses the minimum value and they play alternatively each trying to get the win.
In Tic Tac Toe, we only need 3 values.
- One player is Maximizer, who represents +1 for the win
- One player is Maximizer, who represents -1 for the win
- 0 represents Draw/No Result.
Now, let’s represent the previous game state in the form of a minimax tree.
We loop through each available option and calculate the score using the minimax function. Let’s suppose AI is the maximizing player, so it will choose the higher value among all the scores. We can also assume AI as a minimizing player in which case, it will choose the lower value.
Create another AI opponent Smart Opponent with the following content.
class SmartOpponent extends AiOpponent {
const SmartOpponent();
@override
Tile chooseNextMove(BoardState state) {
final options = <Tile>[];
final startTime = DateTime.now();
for (int x = 0; x < state.setting.m; x++) {
for (int y = 0; y < state.setting.n; y++) {
final tile = Tile(x, y);
if (state.canOccupyTile(tile)) {
options.add(tile);
}
}
}
late Tile bestMove;
var bestScore = -1;
for(int i=0;i<options.length;i++){
// state.moves[options[i]] = state.currentTurn;
//calculate the score for the move
var score = minimax(state, options[i], false, options.where((Tile tile) => tile!=options[i]).toList(), -1, 1);
//undo the move
state.moves.remove(options[i]);
//compare the scores and choose the best one
//ai is maximizing player, so the best score should be the higher values
if(score > bestScore){
bestScore = score;
bestMove = options[i];
}
}
//prints total time taken to compute the move
print("Total time: ${DateTime.now().difference(startTime).inMilliseconds}");
return bestMove;
}Here, we loop through each move and store the best move and score among others.
int minimax(BoardState state, Tile tile, isMaximizing, List<Tile> remainingOptions){
Side _turn = state.currentTurn;
//make the move
state.moves[tile] = _turn;
if(state.hasSomeoneWon(tile, _turn, checkOnly: true)){
return isMaximizing ? -1:1;
}else if(state.isGameDraw){
return 0;
}
if(isMaximizing){
var bestScore = -1;
for(int i=0;i<remainingOptions.length;i++){
//calculate score
var score = minimax(state, remainingOptions[i], false, remainingOptions.where((Tile tile) => tile!=remainingOptions[i]).toList());
state.moves.remove(remainingOptions[i]);
//here we are calculating the best move for the ai which is the maximizing player
//so the bestScore will be the higher values
if(score>bestScore) bestScore = score;
}
return bestScore;
}else{
var bestScore = 1;
for(int i=0;i<remainingOptions.length;i++){
//calculate score
var score = minimax(state, remainingOptions[i], true, remainingOptions.where((Tile tile) => tile!=remainingOptions[i]).toList());
state.moves.remove(remainingOptions[i]);
//here we are calculating the best move for the player which is the minimizing player
//so the bestScore will be the lower values
if(score<bestScore) bestScore = score;
}
return bestScore;
}
}The minimax function is a recursive function, which gets called until all the values are calculated at the leaf and the intermediate nodes. The minimum and maximum cases will run alternatively unless they encounter a win or a draw.
Add the entry of the SmartOpponent to the list of levels in levels.dart file.
const gameLevels = [
....,
GameLevel(
id: 7,
setting: BoardSetting(3, 3, 3,
gameId: 7, aiOpponent: SmartOpponent()),
difficulty: 500,
),
GameLevel(
id: 8,
setting: BoardSetting(3, 3, 3,
gameId: 8, aiOpponent: SmartOpponent(), opponentStarts: true),
difficulty: 600,
),
];We just added opponents with 3X3 boards, since the higher boards will take a comparatively longer time to compute the first move, and more optimization is needed to make them unbeatable.
If we play against these levels with 3X3X3 boards and a smart opponent, the best result that we can get is a draw. Winning is not possible, the result will either be a draw or a defeat for the players.
We’ve also added some code to calculate the total time taken by AI to compute its moves, we observe the following.
The time taken by AI to compute its first move is very large as compared to the 2nd and 3rd moves. We can bring it down a bit by using alpha-beta pruning. In this approach, it will try to find the nodes that have no effect on the calculation, so such nodes are pruned so that the number of iterations needed becomes less.
Make some changes to the SmartOpponent to include alpha-beta pruning optimization. The final code for the smart opponent is as:
import 'dart:math';
import 'package:tictactoe/src/ai/ai_opponent.dart';
import 'package:tictactoe/src/game_internals/board_state.dart';
import 'package:tictactoe/src/game_internals/enums.dart';
import 'package:tictactoe/src/game_internals/tile.dart';
class SmartOpponent extends AiOpponent {
const SmartOpponent();
@override
Tile chooseNextMove(BoardState state) {
final options = <Tile>[];
final startTime = DateTime.now();
for (int x = 0; x < state.setting.m; x++) {
for (int y = 0; y < state.setting.n; y++) {
final tile = Tile(x, y);
if (state.canOccupyTile(tile)) {
options.add(tile);
}
}
}
late Tile bestMove;
var bestScore = -1;
for (int i = 0; i < options.length; i++) {
// state.moves[options[i]] = state.currentTurn;
//calculate the score for the move
var score = minimax(state, options[i], false,
options.where((Tile tile) => tile != options[i]).toList(), -1, 1);
//undo the move
state.moves.remove(options[i]);
//compare the scores and choose the best one
//ai is maximizing player, so the best score should be the higher values
if (score > bestScore) {
bestScore = score;
bestMove = options[i];
}
}
print("Total time: ${DateTime.now().difference(startTime).inMilliseconds}");
return bestMove;
}
int minimax(BoardState state, Tile tile, isMaximizing,
List<Tile> remainingOptions, alpha, beta) {
Side _turn = state.currentTurn;
//make the move
state.moves[tile] = _turn;
if (state.hasSomeoneWon(tile, _turn, checkOnly: true)) {
return isMaximizing ? -1 : 1;
} else if (state.isGameDraw) {
return 0;
}
if (isMaximizing) {
var bestScore = -1;
for (int i = 0; i < remainingOptions.length; i++) {
//calculate score
var score = minimax(
state,
remainingOptions[i],
false,
remainingOptions
.where((Tile tile) => tile != remainingOptions[i])
.toList(),
alpha,
beta);
state.moves.remove(remainingOptions[i]);
//here we are calculating the best move for the ai which is the maximizing player
//so the bestScore will be the higher values
if (score > bestScore) bestScore = score;
alpha = max<int>(alpha, bestScore);
if (beta <= alpha) break;
}
return bestScore;
} else {
var bestScore = 1;
for (int i = 0; i < remainingOptions.length; i++) {
//calculate score
var score = minimax(
state,
remainingOptions[i],
true,
remainingOptions
.where((Tile tile) => tile != remainingOptions[i])
.toList(),
alpha,
beta);
state.moves.remove(remainingOptions[i]);
//here we are calculating the best move for the player which is the minimizing player
//so the bestScore will be the lower values
if (score < bestScore) bestScore = score;
beta = min<int>(beta, bestScore);
if (beta <= alpha) break;
}
return bestScore;
}
}
}If we compare the time taken by the old and the new implementation with alpha-beta pruning, it should be definitely less than that of before.
As expected, the time taken has definitely come down than before.
With this, We have completed this tutorial. If you have reached here from the beginning and also code along then give yourself a pat on the back, we have come a long way to complete this game. We now have a fully functional Tic-Tac-Toe game with 2 modes of play.
Here is the link to the completed repository that we’ve done so far. You can make further changes to make the UI better, optimize the logic, introduce a new mode of play with your own rules, etc.
I have played around with the code to make a few changes such as:
- added an AI vs AI simulation when 2 players are picked randomly and a match is played between them.
- Modified UI, changes in the main menu screen to showcase the AI vs AI simulation, and changed the button style.
- Modified UI, changes in the level selection screen with an option to select sides.
- Modified UI, changes in the play session screen, and added animation while selecting X and O options.
- Modified UI, changes in the win game screen to display a proper message, and also added different buttons.
- Changes in the setting screen to include an option to add a second player's name.
Here is the link to all the repositories:
This is the end of the article and please do leave suggestions or questions if any in the comment section below. Also, feel free to clap 👏 as much as you can and share with other people to show support. Thank you!
#flutter #minimax_algorithm #alpha_beta_pruning #game_development #flutter_games_template #tic_tac_toe #flutter_games
