Skip to content

Instantly share code, notes, and snippets.

@tomaszbartoszewski
Last active July 9, 2017 11:51
Show Gist options
  • Save tomaszbartoszewski/79bf151dd69872cf6111780beb0bac05 to your computer and use it in GitHub Desktop.
Save tomaszbartoszewski/79bf151dd69872cf6111780beb0bac05 to your computer and use it in GitHub Desktop.
Console version of game Connect Four with AI
using Microsoft.VisualStudio.TestTools.UnitTesting;
using ConnectFour;
namespace ConnectFourTests
{
[TestClass]
public class BoardChecks
{
[TestMethod]
public void FourInARow_AtTheBeginning()
{
var board = Board.Empty
.With(0, 0, FieldValue.Blue)
.With(1, 0, FieldValue.Blue)
.With(2, 0, FieldValue.Blue)
.With(3, 0, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInARow_WithTheGap_ReturnInProgress()
{
var board = Board.Empty
.With(0, 0, FieldValue.Blue)
.With(1, 0, FieldValue.Empty)
.With(2, 0, FieldValue.Blue)
.With(3, 0, FieldValue.Blue)
.With(3, 0, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.InProgress, state);
}
[TestMethod]
public void FourInARow_InTheMiddle()
{
var board = Board.Empty
.With(1, 0, FieldValue.Blue)
.With(2, 0, FieldValue.Blue)
.With(3, 0, FieldValue.Blue)
.With(4, 0, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInARow_InTheMiddle_OtherPlayer()
{
var board = Board.Empty
.With(1, 0, FieldValue.Red)
.With(2, 0, FieldValue.Red)
.With(3, 0, FieldValue.Red)
.With(4, 0, FieldValue.Red);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Lose, state);
}
[TestMethod]
public void FourInARow_AtTheEnd()
{
var board = Board.Empty
.With(3, 0, FieldValue.Blue)
.With(4, 0, FieldValue.Blue)
.With(5, 0, FieldValue.Blue)
.With(6, 0, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInARow_InTheEnd_MiddleRow()
{
var board = Board.Empty
.With(2, 3, FieldValue.Blue)
.With(3, 3, FieldValue.Blue)
.With(4, 3, FieldValue.Blue)
.With(5, 3, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void InProgress()
{
var board = Board.Empty
.With(2, 3, FieldValue.Blue)
.With(3, 3, FieldValue.Blue)
.With(5, 3, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.InProgress, state);
}
[TestMethod]
public void FourInAColumn_AtTheBeginning()
{
var board = Board.Empty
.With(0, 0, FieldValue.Blue)
.With(0, 1, FieldValue.Blue)
.With(0, 2, FieldValue.Blue)
.With(0, 3, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInAColumn_WithTheGap_ReturnInProgress()
{
var board = Board.Empty
.With(0, 0, FieldValue.Blue)
.With(0, 1, FieldValue.Empty)
.With(0, 2, FieldValue.Blue)
.With(0, 3, FieldValue.Blue)
.With(0, 4, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.InProgress, state);
}
[TestMethod]
public void FourInAColumn_InTheMiddle()
{
var board = Board.Empty
.With(0, 1, FieldValue.Blue)
.With(0, 2, FieldValue.Blue)
.With(0, 3, FieldValue.Blue)
.With(0, 4, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInAColumn_AtTheEnd()
{
var board = Board.Empty
.With(0, 2, FieldValue.Blue)
.With(0, 3, FieldValue.Blue)
.With(0, 4, FieldValue.Blue)
.With(0, 5, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInAColumn_InTheEnd_MiddleColumn()
{
var board = Board.Empty
.With(4, 2, FieldValue.Blue)
.With(4, 3, FieldValue.Blue)
.With(4, 4, FieldValue.Blue)
.With(4, 5, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalDown_AtTheBeginning()
{
var board = Board.Empty
.With(0, 0, FieldValue.Blue)
.With(1, 1, FieldValue.Blue)
.With(2, 2, FieldValue.Blue)
.With(3, 3, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalDown_WithTheGap_ReturnInProgress()
{
var board = Board.Empty
.With(0, 0, FieldValue.Blue)
.With(1, 1, FieldValue.Empty)
.With(2, 2, FieldValue.Blue)
.With(3, 3, FieldValue.Blue)
.With(4, 4, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.InProgress, state);
}
[TestMethod]
public void FourInADiagonalDown_InTheMiddle()
{
var board = Board.Empty
.With(1, 1, FieldValue.Blue)
.With(2, 2, FieldValue.Blue)
.With(3, 3, FieldValue.Blue)
.With(4, 4, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalDown_AtTheEnd()
{
var board = Board.Empty
.With(3, 2, FieldValue.Blue)
.With(4, 3, FieldValue.Blue)
.With(5, 4, FieldValue.Blue)
.With(6, 5, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalDown_ColumnInTheEnd_RowMiddle()
{
var board = Board.Empty
.With(3, 1, FieldValue.Blue)
.With(4, 2, FieldValue.Blue)
.With(5, 3, FieldValue.Blue)
.With(6, 4, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalUp_AtTheBeginning()
{
var board = Board.Empty
.With(0, 3, FieldValue.Blue)
.With(1, 2, FieldValue.Blue)
.With(2, 1, FieldValue.Blue)
.With(3, 0, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalUp_WithTheGap_ReturnInProgress()
{
var board = Board.Empty
.With(0, 4, FieldValue.Blue)
.With(1, 3, FieldValue.Empty)
.With(2, 2, FieldValue.Blue)
.With(3, 1, FieldValue.Blue)
.With(4, 0, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.InProgress, state);
}
[TestMethod]
public void FourInADiagonalUp_InTheMiddle()
{
var board = Board.Empty
.With(1, 4, FieldValue.Blue)
.With(2, 3, FieldValue.Blue)
.With(3, 2, FieldValue.Blue)
.With(4, 1, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalUp_AtTheEnd()
{
var board = Board.Empty
.With(3, 5, FieldValue.Blue)
.With(4, 4, FieldValue.Blue)
.With(5, 3, FieldValue.Blue)
.With(6, 2, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
[TestMethod]
public void FourInADiagonalUp_ColumnInTheEnd_RowMiddle()
{
var board = Board.Empty
.With(3, 4, FieldValue.Blue)
.With(4, 3, FieldValue.Blue)
.With(5, 2, FieldValue.Blue)
.With(6, 1, FieldValue.Blue);
var state = board.GetCurrentState(FieldValue.Blue);
Assert.AreEqual(Result.Win, state);
}
}
}
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace ConnectFour
{
class Program
{
static void Main(string[] args)
{
var firstPlayer = new MinMaxInvadingMiddleFieldsPlayer(FieldValue.Blue, 6);
var secondPlayer = new MinMaxInvadingMiddleFieldsPlayer(FieldValue.Red, 6);
var newGame = new Game(firstPlayer, secondPlayer);
while (true)
{
newGame.StartGame();
Console.ReadLine();
}
}
}
public class Game
{
private readonly IPlayer firstPlayer;
private readonly IPlayer secondPlayer;
public Game(IPlayer firstPlayer, IPlayer secondPlayer)
{
this.firstPlayer = firstPlayer;
this.secondPlayer = secondPlayer;
}
public void StartGame()
{
var board = Board.Empty;
var currentState = Result.InProgress;
var firstPlayerMove = true;
var lastPlayer = FieldValue.Empty;
PrintBoard(board);
while (currentState == Result.InProgress)
{
var move = firstPlayerMove
? firstPlayer.GetMove(board)
: secondPlayer.GetMove(board);
lastPlayer = move.FieldValue;
if (board.TryDropButton(move, out Board newBoard))
{
board = newBoard;
PrintBoard(board);
currentState = board.GetCurrentState(move.FieldValue);
firstPlayerMove = !firstPlayerMove;
}
else // it should never happen with available columns
{
Console.WriteLine("Invalid move {0}, try again", move.Column);
}
}
switch (currentState) // you can't lose directly after your move, so only check for draw and win
{
case Result.Draw:
Console.ForegroundColor = ConsoleColor.Yellow;
Console.WriteLine("Draw");
break;
case Result.Win:
Console.ForegroundColor = ConsoleColor.Yellow;
Console.WriteLine("{0} player won!", lastPlayer);
break;
}
Console.ResetColor();
}
private void PrintBoard(Board board)
{
Console.Write(" ");
for (var column = 0; column <= 6; column++)
Console.Write(column);
Console.WriteLine();
Console.WriteLine(" -------");
for (var row = 0; row <= 5; row++)
{
Console.Write("{0}|", row);
for (var column = 0; column <= 6; column++)
WriteFieldValue(board[column, row]);
Console.WriteLine();
}
void WriteFieldValue(FieldValue fieldValue)
{
switch (fieldValue)
{
case FieldValue.Empty:
Console.BackgroundColor = ConsoleColor.Black;
Console.Write(' ');
break;
case FieldValue.Blue:
Console.BackgroundColor = ConsoleColor.Blue;
Console.Write(' ');
break;
case FieldValue.Red:
Console.BackgroundColor = ConsoleColor.Red;
Console.Write(' ');
break;
}
Console.ResetColor();
}
}
}
public interface IPlayer
{
Move GetMove(Board board);
}
public class HumanPlayer : IPlayer
{
private readonly FieldValue playerFieldValue;
public HumanPlayer(FieldValue fieldValue)
{
playerFieldValue = fieldValue;
}
public Move GetMove(Board board)
{
var availableMovesArray = board.AvailableColumns().ToArray();
var selectedColumn = -1;
while (!availableMovesArray.Contains(selectedColumn))
{
Console.WriteLine($"Choose one column from {string.Join(", ", availableMovesArray)}");
var userInput = Console.ReadLine();
if (int.TryParse(userInput, out int selectedColumnAsInt))
selectedColumn = selectedColumnAsInt;
}
return new Move(selectedColumn, playerFieldValue);
}
}
public class RandomPlayer : IPlayer
{
private readonly FieldValue playerFieldValue;
public RandomPlayer(FieldValue fieldValue)
{
playerFieldValue = fieldValue;
}
public Move GetMove(Board board)
{
var availableMovesArray = board.AvailableColumns().ToArray();
var rnd = new Random();
var selectedColumn = rnd.Next(availableMovesArray.Length);
return new Move(availableMovesArray[selectedColumn], playerFieldValue);
}
}
public class MinMaxPlayer : IPlayer
{
private readonly FieldValue playerFieldValue;
private readonly int maxTreeDepth;
public MinMaxPlayer(FieldValue fieldValue, int maxTreeDepth)
{
playerFieldValue = fieldValue;
this.maxTreeDepth = maxTreeDepth;
}
public Move GetMove(Board board)
{
var sw = Stopwatch.StartNew();
var move = CheckAllPossibleMoves(board, playerFieldValue, 1).Move;
sw.Stop();
Console.WriteLine("Time spent thinking: {0}ms", sw.ElapsedMilliseconds);
return move;
}
private int CalculatePointsForMove(Board board, Move move, int depth)
{
//var cutDepth = GetDepth(board);
board.TryDropButton(move, out board);
var status = board.GetCurrentState(move.FieldValue);
if (status == Result.Win && move.FieldValue == playerFieldValue)
return 43 - depth;
if (status == Result.Win && move.FieldValue != playerFieldValue)
return -43 + depth;
if (status == Result.Draw || depth == maxTreeDepth)
return 0;
if (status == Result.InProgress)
{
return CheckAllPossibleMoves(board, GetOppositePlayerSign(move.FieldValue), depth+1).Points;
}
return 0;
}
private int GetDepth(Board board)
{
switch (board.AvailableColumns().Count())
{
case 5:
case 1:
return 7;
case 4:
return 8;
case 3:
return 10;
case 2:
return 12;
default:
return 6;
}
}
private PointsForMove CheckAllPossibleMoves(Board board, FieldValue fieldValue, int depth)
{
var allResults = new List<PointsForMove>();
foreach (var column in board.AvailableColumns())
{
var move = new Move(column, fieldValue);
var points = CalculatePointsForMove(board, move, depth);
allResults.Add(new PointsForMove(points, move));
}
if (fieldValue == playerFieldValue)
return allResults.OrderByDescending(r => r.Points).First();
return allResults.OrderBy(r => r.Points).First();
}
private FieldValue GetOppositePlayerSign(FieldValue fieldValue)
=> fieldValue == FieldValue.Red ? FieldValue.Blue : FieldValue.Red;
private struct PointsForMove
{
public PointsForMove(int points, Move move)
{
Points = points;
Move = move;
}
public int Points { get; }
public Move Move { get; }
}
}
public class MinMaxInvadingMiddleFieldsPlayer : IPlayer
{
private readonly FieldValue playerFieldValue;
private readonly int maxTreeDepth;
public MinMaxInvadingMiddleFieldsPlayer(FieldValue fieldValue, int maxTreeDepth)
{
playerFieldValue = fieldValue;
this.maxTreeDepth = maxTreeDepth;
}
public Move GetMove(Board board)
{
var sw = Stopwatch.StartNew();
var move = CheckAllPossibleMoves(board, playerFieldValue, 1).Move;
sw.Stop();
Console.WriteLine("Time spent thinking: {0}ms", sw.ElapsedMilliseconds);
return move;
}
private int CalculatePointsForMove(Board board, Move move, int depth)
{
//var cutDepth = GetDepth(board);
board.TryDropButton(move, out board);
var status = board.GetCurrentState(move.FieldValue);
if (status == Result.Win && move.FieldValue == playerFieldValue)
return 43 - depth;
if (status == Result.Win && move.FieldValue != playerFieldValue)
return -43 + depth;
if (status == Result.Draw || depth == maxTreeDepth)
return 0;
if (status == Result.InProgress)
{
return CheckAllPossibleMoves(board, GetOppositePlayerSign(move.FieldValue), depth + 1).Points;
}
return 0;
}
private int GetDepth(Board board)
{
switch (board.AvailableColumns().Count())
{
case 5:
case 1:
return 7;
case 4:
return 8;
case 3:
return 10;
case 2:
return 12;
default:
return 6;
}
}
private PointsForMove CheckAllPossibleMoves(Board board, FieldValue fieldValue, int depth)
{
var allResults = new List<PointsForMove>();
foreach (var column in board.AvailableColumns())
{
var move = new Move(column, fieldValue);
var points = CalculatePointsForMove(board, move, depth);
allResults.Add(new PointsForMove(points, move));
}
if (fieldValue == playerFieldValue)
return allResults.OrderByDescending(r => r.Points).ThenBy(r => Math.Abs(3-r.Move.Column)).First();
return allResults.OrderBy(r => r.Points).ThenBy(r => Math.Abs(3 - r.Move.Column)).First();
}
private FieldValue GetOppositePlayerSign(FieldValue fieldValue)
=> fieldValue == FieldValue.Red ? FieldValue.Blue : FieldValue.Red;
private struct PointsForMove
{
public PointsForMove(int points, Move move)
{
Points = points;
Move = move;
}
public int Points { get; }
public Move Move { get; }
}
}
public class Board
{
public static readonly Board Empty = new Board(new FieldValue[42]);
private Board(FieldValue[] arr) => _arr = arr;
private readonly FieldValue[] _arr;
public FieldValue this[int c, int r] => _arr[c + r * 7];
public Board With(int c, int r, FieldValue fv)
{
var arr = new FieldValue[_arr.Length];
_arr.CopyTo(arr, 0);
arr[c + r * 7] = fv;
return new Board(arr);
}
public Result GetCurrentState(FieldValue playerSign)
{
foreach (var semiState in FourInARow(playerSign)
.Concat(FourInAColumn(playerSign))
.Concat(FourInADiagonalDown(playerSign))
.Concat(FourInADiagonalUp(playerSign)))
{
if (semiState == Result.Win)
return Result.Win;
if (semiState == Result.Lose)
return Result.Lose;
}
if (_arr.Any(f => f == FieldValue.Empty))
return Result.InProgress;
return Result.Draw;
}
public bool TryDropButton(Move move, out Board newBoard)
{
for (var row = 5; row >= 0; row--)
{
if (this[move.Column, row] == FieldValue.Empty)
{
newBoard = With(move.Column, row, move.FieldValue);
return true;
}
}
newBoard = null;
return false;
}
public IEnumerable<int> AvailableColumns()
{
for (var column = 0; column <= 6; column++)
if (this[column, 0] == FieldValue.Empty)
yield return column;
}
private IEnumerable<Result> FourInARow(FieldValue playerSign)
{
for (var column = 0; column <= 3; column++)
{
for (var row = 0; row <= 5; row++)
{
yield return ResultStartingAt(column, row, CheckType.Horizontal, playerSign);
}
}
}
private IEnumerable<Result> FourInAColumn(FieldValue playerSign)
{
for (var column = 0; column <= 6; column++)
{
for (var row = 0; row <= 2; row++)
{
yield return ResultStartingAt(column, row, CheckType.Vertical, playerSign);
}
}
}
private IEnumerable<Result> FourInADiagonalDown(FieldValue playerSign)
{
for (var column = 0; column <= 3; column++)
{
for (var row = 0; row <= 2; row++)
{
yield return ResultStartingAt(column, row, CheckType.DiagonalDown, playerSign);
}
}
}
private IEnumerable<Result> FourInADiagonalUp(FieldValue playerSign)
{
for (var column = 0; column <= 3; column++)
{
for (var row = 3; row <= 5; row++)
{
yield return ResultStartingAt(column, row, CheckType.DiagonalUp, playerSign);
}
}
}
private Result ResultStartingAt(int column, int row, CheckType checkType, FieldValue playerSign)
{
var firstValue = this[column, row];
if (firstValue == FieldValue.Empty)
{
return Result.InProgress;
}
for (var move = 1; move <= 3; move++)
{
var columnToCompare =
checkType == CheckType.Vertical
? column
: column + move;
var rowToCompare =
checkType == CheckType.Horizontal
? row
: checkType == CheckType.DiagonalUp
? row - move
: row + move;
if (firstValue != this[columnToCompare, rowToCompare])
{
return Result.InProgress;
}
}
if (firstValue == playerSign)
return Result.Win;
else
return Result.Lose;
}
private enum CheckType : byte
{
Vertical,
Horizontal,
DiagonalDown,
DiagonalUp
}
}
public struct Move
{
public FieldValue FieldValue;
public int Column;
public Move(int column, FieldValue fieldValue)
{
FieldValue = fieldValue;
Column = column;
}
}
public enum FieldValue : byte
{
Empty,
Blue,
Red
}
public enum Result : byte
{
Win,
Draw,
Lose,
InProgress
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment