8000 Merge pull request #26 from michalnowak061/minimax · delphi1977/Swift@e933a92 · GitHub
[go: up one dir, main page]
8000
Skip to content

Commit e933a92

Browse files
carloshmartinscarloshmartins
authored
Merge pull request TheAlgorithms#26 from michalnowak061/minimax
Add minimax algorithm
2 parents 380d72d + a82d199 commit e933a92

26 files changed

+1356
-0
lines changed

‎algorithms/AI/minimax/README.md

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
# Minimax algorithm
2+
3+
<p align="center"> <img src="Resources/image1.jpg" {:height="50%" width="50%"} /> </p>
4+
5+
## Runtime environment
6+
<img src="https://img.shields.io/badge/Swift-5.3-orange.svg?style=flat" />
7+
<img src="https://img.shields.io/badge/Xcode-12.4-blue.svg?style=flat" />
8+
<img src="https://img.shields.io/badge/MacOS-11.2.3-blue.svg?style=flat" />
9+
10+
## Table of contents
11+
* [General info](#general-info)
12+
* [Functionality](#functionality)
13+
* [Pseudocode](#pseudocode)
14+
* [Demo](#demo)
15+
* [Sources](#sources)
16+
17+
## General info
18+
It is an example of implementation and use ``minimax algorithm`` in ``Tic Tac Toe`` game. Minimax is an algorithm that searches deeply into all possible states in the game. There are two types of players in the algorithm. One that wants to maximize the state of the game and one that wants to minimaze the state of the game. There are three states in the tic-tac-toe game:
19+
- `` -1 `` - if the minimizing player wins
20+
- `` 0 `` - in case of a tie
21+
- `` 1 `` - if the maximizing player wins
22+
23+
``Alpha-beta prunning`` this is a method that interrupts the search of those branches that do not lead to win. Alpha for maximizing player and beta for minimizing player. Alpha-beta prunnings reduce the time complexity of the algorithm.
24+
25+
Parameters:
26+
- ``searching depth`` - how many moves in depth is to be calculated by the algorithm
27+
28+
Input:
29+
- ``actual board state`` - in the form of an array for players symbols (cross/circle)
30+
- ``two player symbols`` - cross / circle
31+
32+
Output:
33+
- ``the best move for autonomus(AI) player`` - Position(row: Int, column: Int)
34+
35+
## Functionality
36+
- example of use in Swift Playground with interactive UIView
37+
- unit tests in XCode
38+
39+
## Pseudocode
40+
41+
```
42+
function alphabeta(node, depth, α, β, maximizingPlayer) is
43+
if depth = 0 or node is a terminal node then
44+
return the heuristic value of node
45+
if maximizingPlayer then
46+
value := −∞
47+
for each child of node do
48+
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
49+
if value ≥ β then
50+
break (* β cutoff *)
51+
α := max(α, value)
52+
return value
53+
else
54+
value := +∞
55+
for each child of node do
56+
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
57+
if value ≤ α then
58+
break (* α cutoff *)
59+
β := min(β, value)
60+
return value
61+
```
62+
63+
## Demo
64+
65+
<p align="center"> <img src="Resources/demo.gif" {:height="100%" width="100%"} /> </p>
66+
67+
## Sources
68+
* Minimax algorithm: https://en.wikipedia.org/wiki/Minimax
69+
* Alpha-beta prunning: https://en.wikipedia.org/wiki/Alpha–beta_pruning
70+
71+
## Author
72+
Written by Michał Nowak(mnowak061)

‎algorithms/AI/minimax/Resources/demo.gif

725 KB
Loading

‎algorithms/AI/minimax/Resources/image1.jpg

57.2 KB
Loading

‎algorithms/AI/minimax/Sources/Minimax.playground/Contents.swift

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
import UIKit
2+
import PlaygroundSupport
3+
4+
let boardSize = CGSize(width: 500, height: 550)
5+
let boardView = BoardView(frame: CGRect(origin: .zero, size: boardSize))
6+
7+
PlaygroundPage.current.needsIndefiniteExecution = true
8+
PlaygroundPage.current.liveView = boardView

‎algorithms/AI/minimax/Sources/Minimax.playground/Sources/Model/Board/Board.swift

Lines changed: 154 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,154 @@
1+
public struct Board {
2+
// MARK: -- Public variable's
3+
public var size: Int
4+
5+
// MARK: -- Private variable's
6+
private var table: [ [PlayerSymbol?] ]
7+
8+
// MARK: -- Public function's
9+
public init(size: Int) {
10+
self.size = size
11+
self.table = []
12+
self.clear()
13+
}
14+
15+
public mutating func clear() {
16+
self.table = Array(repeating: Array(repeating: PlayerSymbol.empty, count: size), count: size)
17+
}
18+
19+
public func hasEmptyField() -> Bool {
20+
for i in 0 ..< self.size {
21+
for j in 0 ..< self.size {
22+
if self.table[i][j] == PlayerSymbol.empty {
23+
return true
24+
}
25+
}
26+
}
27+
return false
28+
}
29+
30+
public func symbol(forPosition position: Position) -> PlayerSymbol? {
31+
guard position.row < self.size, position.column < size else { return nil }
32+
return self.table[position.row][position.column]
33+
}
34+
35+
public mutating func makeMove(player: Player, position: Position) {
36+
guard self.symbol(forPosition: position) == PlayerSymbol.empty else { return }
37+
guard self.symbol(forPosition: position) != player.symbol else { return }
38+
39+
self.table[position.row][position.column] = player.symbol
40+
}
41+
42+
public func check(player: Player) -> BoardStatus {
43+
let playerSymbol: PlayerSymbol = player.symbol
44+
45+
if self.foundWinInRows(playerSymbol) { return BoardStatus.win }
46+
if self.foundWinInColumns(playerSymbol) { return BoardStatus.win }
47+
if self.foundWinInSlants(playerSymbol) { return BoardStatus.win }
48+
49+
if self.hasEmptyField() { return BoardStatus.continues } else { return BoardStatus.draw }
50+
}
51+
52+
// M F438 ARK: -- Private function's
53+
private func foundWinInRows(_ playerSymbol: PlayerSymbol) -> Bool {
54+
for i in 0 ..< self.size {
55+
var theSameSymbolsInRowCount = 0
56+
57+
for j in 0 ..< self.size - 1 {
58+
if self.table[i][j] == self.table[i][j+1] && (self.table[i][j] == playerSymbol) {
59+
theSameSymbolsInRowCount += 1
60+
} else {
61+
theSameSymbolsInRowCount = 0
62+
}
63+
}
64+
65+
if theSameSymbolsInRowCount == self.size - 1 {
66+
return true
67+
}
68+
}
69+
70+
return false
71+
}
72+
73+
private func foundWinInColumns(_ playerSymbol: PlayerSymbol) -> Bool {
74+
for j in 0 ..< self.size {
75+
var theSameSymbolsInColumnCount = 0
76+
77+
for i in 0 ..< self.size - 1 {
78+
if self.table[i][j] == self.table[i+1][j] && (self.table[i][j] == playerSymbol) {
79+
theSameSymbolsInColumnCount += 1
80+
} else {
81+
theSameSymbolsInColumnCount = 0
82+
}
83+
}
84+
85+
if theSameSymbolsInColumnCount == self.size - 1 {
86+
return true
87+
}
88+
}
89+
90+
return false
91+
}
92+
93+
private func foundWinInSlants(_ playerSymbol: PlayerSymbol) -> Bool {
94+
var theSameSymbolsInSlantCount = 0
95+
96+
for i in 0 ..< self.size {
97+
for j in -(self.size - 1) ... 0 {
98+
if(self.table[-j][i] == playerSymbol) {
99+
var k: Int = -j
100+
var l: Int = i
101+
theSameSymbolsInSlantCount = 0
102+
103+
while l < self.size && k >= 0 {
104+
if self.table[k][l] == playerSymbol {
105+
theSameSymbolsInSlantCount += 1
106+
} else {
107+
theSameSymbolsInSlantCount = 0
108+
}
109+
k -= 1
110+
l += 1
111+
112+
if theSameSymbolsInSlantCount == self.size {
113+
return true
114+
}
115+
}
116+
theSameSymbolsInSlantCount = 0
117+
}
118+
theSameSymbolsInSlantCount = 0
119+
}
120+
theSameSymbolsInSlantCount = 0
121+
}
122+
123+
theSameSymbolsInSlantCount = 0
124+
125+
for i in 0 ..< self.size {
126+
for j in 0 ..< self.size {
127+
if(self.table[j][i] == playerSymbol) {
128+
var k: Int = j
129+
var l: Int = i
130+
theSameSymbolsInSlantCount = 0
131+
132+
while l < self.size && k < self.size {
133+
if self.table[k][l] == playerSymbol {
134+
theSameSymbolsInSlantCount += 1
135+
} else {
136+
theSameSymbolsInSlantCount = 0
137+
}
138+
k += 1
139+
l += 1
140+
141+
if theSameSymbolsInSlantCount == self.size {
142+
return true
143+
}
144+
}
145+
theSameSymbolsInSlantCount = 0
146+
}
147+
theSameSymbolsInSlantCount = 0
148+
}
149+
theSameSymbolsInSlantCount = 0
150+
}
151+
152+
return false
153+
}
154+
}

‎algorithms/AI/minimax/Sources/Minimax.playground/Sources/Model/Board/BoardPosition.swift

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
public typealias Position = (row: Int, column: Int)

‎algorithms/AI/minimax/Sources/Minimax.playground/Sources/Model/Board/BoardStatus.swift

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
public enum BoardStatus {
2+
3+
case continues
4+
5+
case win
6+
7+
case draw
8+
}

‎algorithms/AI/minimax/Sources/Minimax.playground/Sources/Model/GameModel/DifficultLevel.swift

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
public enum DifficultLevel: Int {
2+
3+
case easy = 2
4+
5+
case medium = 3
6+
7+
case hard = 5
8+
}

‎algorithms/AI/minimax/Sources/Minimax.playground/Sources/Model/GameModel/GameModel.swift

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
import Foundation
2+
3+
public class GameModel {
4+
// MARK: -- Public variable's
5+
public var board: Board!
6+
7+
public var gameStatus: BoardStatus
8+
9+
// MARK: -- Private variable's
10+
private var playersList: [Player]!
11+
12+
private var movementsSequence: [Int]!
13+
14+
private var actualPlayerIndex: Int!
15+
16+
private var actualPlayer: Player {
17+
get {
18+
return playersList[actualPlayerIndex]
19+
}
20+
}
21+
22+
private var difficultLevel: DifficultLevel = DifficultLevel.hard
23+
24+
// MARK: -- Public function's
25+
public init(boardSize: Int, playersList: [Player], difficultLevel: DifficultLevel) {
26+
self.board = Board.init(size: boardSize)
27+
self.playersList = playersList
28+
self.difficultLevel = difficultLevel
29+
self.gameStatus = BoardStatus.continues
30+
31+
self.generateMovementsSequence()
32+
self.changeActualPlayer()
33+
}
34+
35+
public func update() {
36+
self.gameStatus = board.check(player: actualPlayer)
37+
38+
switch self.gameStatus {
39+
case BoardStatus.continues:
40+
changeActualPlayer()
41+
case BoardStatus.draw:
42+
changeActualPlayer()
43+
default: break
44+
}
45+
}
46+
47+
public func playerMakeMove(selectedPosition: (row: Int, column: Int)) {
48+
guard board.symbol(forPosition: selectedPosition) == PlayerSymbol.empty else { return }
49+
guard board.hasEmptyField() == true else { return }
50+
51+
board.makeMove(player: actualPlayer, position: selectedPosition)
52+
update()
53+
}
54+
55+
public func makeMinimaxMove() {
56+
guard actualPlayer.type == PlayerType.computer else { return }
57+
guard board.hasEmptyField() == true else { return }
58+
59+
sleep(1)
60+
61+
let selectedPosition: Position = minimaxMove(board: board, player: playersList[0], opponent: playersList[1], depth: self.difficultLevel.rawValue)
62+
board.makeMove(player: actualPlayer, position: selectedPosition)
63+
update()
64+
}
65+
66+
public func newRound() {
67+
board.clear()
68+
gameStatus = BoardStatus.continues
69+
generateMovementsSequence()
70+
changeActualPlayer()
71+
}
72+
73+
// MARK: -- Private function's
74+
private func generateMovementsSequence() {
75+
self.movementsSequence = []
76+
77+
let playersCount = playersList.count
78+
let movesCount = (board.size * board.size)
79+
80+
var move = Int.random(in: 0 ..< playersCount)
81+
movementsSequence.append(move)
82+
83+
for _ in 0 ..< movesCount - 1 {
84+
move += 1
85+
movementsSequence.append(move % playersCount)
86+
}
87+
}
88+
89+
private func changeActualPlayer() {
90+
if !movementsSequence.isEmpty {
91+
actualPlayerIndex = movementsSequence.first!
92+
movementsSequence.removeFirst()
93+
}
94+
}
95+
}

‎algorithms/AI/minimax/Sources/Minimax.playground/Sources/Model/Minimax/GameStateValue.swift

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
public enum GameStateValue: Int {
2+
3+
case min = -1
4+
5+
case null = 0
6+
7+
case max = 1
8+
}

0 commit comments

Comments
 (0)
0