diff options
| author | Navan Chauhan <navanchauhan@gmail.com> | 2024-04-18 00:47:42 -0600 |
|---|---|---|
| committer | Navan Chauhan <navanchauhan@gmail.com> | 2024-04-18 00:47:42 -0600 |
| commit | 6844c234cde69ee356168bb3dcb7d69fa4e8a74d (patch) | |
| tree | 1d9c07bca693ae4c41afad065f03b03feb001774 | |
| parent | 0a01d79c96626d293da71b2319f1bfc0c56511dc (diff) | |
simple chess AI
| -rw-r--r-- | Content/posts/2024-03-26-Derivation-of-the-Quadratic-Equation.md | 2 | ||||
| -rw-r--r-- | Content/posts/2024-04-17-implementing-minimax-for-chess-in-swift.md | 295 | ||||
| -rw-r--r-- | Resources/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png | bin | 0 -> 38531 bytes | |||
| -rw-r--r-- | docs/feed.rss | 314 | ||||
| -rw-r--r-- | docs/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png | bin | 0 -> 38531 bytes | |||
| -rw-r--r-- | docs/index.html | 34 | ||||
| -rw-r--r-- | docs/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html | 387 | ||||
| -rw-r--r-- | docs/posts/index.html | 19 | ||||
| -rw-r--r-- | docs/tags/Chess.html | 108 | ||||
| -rw-r--r-- | docs/tags/Game Theory.html | 108 | ||||
| -rw-r--r-- | docs/tags/Swift.html | 17 | ||||
| -rw-r--r-- | docs/tags/mathematics.html | 11 |
12 files changed, 1266 insertions, 29 deletions
diff --git a/Content/posts/2024-03-26-Derivation-of-the-Quadratic-Equation.md b/Content/posts/2024-03-26-Derivation-of-the-Quadratic-Equation.md index 0435a6c..a618419 100644 --- a/Content/posts/2024-03-26-Derivation-of-the-Quadratic-Equation.md +++ b/Content/posts/2024-03-26-Derivation-of-the-Quadratic-Equation.md @@ -1,7 +1,7 @@ --- date: 2024-03-26 15:36 description: Quick derivation of the quadratic equation by completing the square -tags: mathematics +tags: Mathematics --- # Quadratic Formula Derivation diff --git a/Content/posts/2024-04-17-implementing-minimax-for-chess-in-swift.md b/Content/posts/2024-04-17-implementing-minimax-for-chess-in-swift.md new file mode 100644 index 0000000..aeb0840 --- /dev/null +++ b/Content/posts/2024-04-17-implementing-minimax-for-chess-in-swift.md @@ -0,0 +1,295 @@ +--- +date: 2024-04-17 23:20 +description: Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax +tags: Swift, Chess, Game Theory, Mathematics +--- + +# Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift + +Ever since Chess24 shut down, I have been looking to find a better way to follow Chess tournaments. A few weeks ago I decided to start working on a cross-platform (macOS/iOS) app using Lichess's API. +I heavily underestimated the amount of work it would take me to build something like this in SwiftUI. You not only need a library that can parse PGNs, but also a way to display those moves! + + +I ended up forking [Sage](https://github.com/nvzqz/Sage) to [swift-chess-neo](https://git.navan.dev/swift-chess-neo). I did have to patch the library to make it compatible with Swift 5 and create my own UI components using SwiftUI. + + +Now that I had a working Chess library that could give me all legal moves in a position, I wondered if I could write a minimax implementation. + +## Theory + +Imagine you could look far ahead into the future and predict the perfect moves in a game for both sides. This is similar to Dr. Strange seeing all 14,000,605 alternate futures. +Knowing what works and what doesn't can help you decide what you should actually play. + + +Using the example of Dr. Strange looking into the alternate futures, think of the Avengers winning being scored as +1, and Thanos winning being scored as -1. +The Avengers would try to maximize this score, whereas Thanos would try to minimize this. + + +This is the idea of "minimax". + + +Say we are playing a game of Tic-Tac-Toe, where us winning is scored positively and our opponent winning is scored negatively. We are going to try and maximize our score. A fresh game of Tic-Tac-Toe can be represented as a 3x3 grid. Which means, if we have the first turn we have 9 possible moves. + +Say we place an X in the top left corner: + +``` +------------- +| x | | | +------------- +| | | | +------------- +| | | | +------------- +``` + +Now, our oponent has 8 different moves they can play. Say they play their move in the bottom right corner + +``` +------------- +| x | | | +------------- +| | | | +------------- +| | | o | +------------- +``` + +We have 6 different moves we can play. + +It would take us ages to brute force each and every combination/permutation of moves by hand. A depth-first minimax algorithm for Tick-Tac-Toe would have a max-depth of 9 (since after 9 moves from the start, we would have exhausted the search space as there would be no more available moves). + +Since we cannot score an individual Tic-Tac-Toe position (technically we can), we can iterate through all moves (till we reach our max-depth) and then use these three terminal states: + +* +1 (You Win) +* -1 (You Lose) +* 0 (Draw) + +### Pseudocode + +``` +function minimax(board, depth, isMaximizingPlayer): + score = evaluate(board) + + # +1 Win, -1 Lose, 0 Draw + if score == 1: return score + if score == -1: return score + + if boardFull(board): + return 0 + + if isMaximizingPlayer: + best = -infinity + + for each cell in board: + if cell is empty: + place X in cell + best = maximum of (best, minimax(board, depth + 1, false)) + remove X from cell + return best + + else: + best = infinity + + for each cell in board: + if cell is empyu: + place O in cell + best = minimum of (best, minimax(board, depth + 1, true)) + return best + +function evaluate(board): + if three consecutive Xs: return 1 + if three consecutive 0s: return -1 + + return 0 + +function boardFull(board): + if all cells are filled: return true + + else: + return false +``` + +Think of each move as a node, and each node having multiple continuations (each continuing move can be represented as a node). + +### Alpha-Beta Pruning + +This is quiet inefficient, as this will comb through all $9!$ or $362,880$ moves! Imagine iterating through the entire search space for a complex game like Chess. It would be impossible. Therefore we use a technique called Alpha-beta pruning wherein we reduce the number of nodes that we are evaluating. + +``` +function minimax(board, depth, isMaximizingPlayer, alpha, beta): + score = evaluate(board) + + # +1 Win, -1 Lose, 0 Draw + if score == 1: return score + if score == -1: return score + + if boardFull(board): + return 0 + + if isMaximizingPlayer: + best = -infinity + + for each cell in board: + if cell is empty: + place X in cell + best = maximum of (best, minimax(board, depth + 1, false, alpha, beta)) + remove X from cell + alpha = max(alpha, best) + if beta <= alpha: + break + return best + + else: + best = infinity + + for each cell in board: + if cell is empyu: + place O in cell + best = minimum of (best, minimax(board, depth + 1, true, alpha, beta)) + beta = min(beta, best) + if beta <= alpha: + break + return best +``` + +Alpha and beta are initialized as $-\infty$ and $+\infty$ respectively, with Alpha representing the best already explored option along the path to the root for the maximizer, and beta representing the best already explored option along the path to the root for the minimizer. If at any point beta is less than or equal to alpha, it means that the current branch does not need to be explored further because the parent node already has a better move elsewhere, thus "pruning" this node. + +Thus, to implement a model you can use minimax (or similar algorithms), you need to be able to describe the following: + +* Players + * Player Count - How many players are there in this game? (Just 2) + * Active Player - Whose turn is it? +* Game + * Game State - How do you represent the current game state + * Save/Load Game State - If you are trying out different moves, you need to be able to go to the original state before you move on to the next node + * Score - Who is winning? Is the game over? Who lost? +* Moves + * Valid Moves - What are all the legal moves in this game state? + +## Show me the code! + +The chess library does a little bit of the heavy lifting by already providing methods to take care of the above requirements. Since we already have a way to find all possible moves in a position, we only need to figure out a few more functions/methods: + +* Evaluation/Score - We need to be able to numerically quantify the effect of a move. For a basic implementation we can just sum over the piece values. +* Game state management - Since we explore different possible moves in our search space up to a certain depth, we need to be able to copy/save the state and reset it back to this state after we are done exploring all of our moves. Even though I did add a `setGame` method to the `Game` class, I use the `undoMove()` method + +### Evaluate + +Each piece has a different relative value. Since "capturing" the king finishes the game, the king is given a really high value. + +```swift +public struct Piece: Hashable, CustomStringConvertible { + public enum Kind: Int { + ... + public var relativeValue: Double { + switch self { + case .pawn: return 1 + case .knight: return 3 + case .bishop: return 3.25 + case .rook: return 5 + case .queen: return 9 + case .king: return 900 + } + } + ... + } + ... +} +``` + +We extend the `Game` class by adding an evaluate function that adds up the value of all the pieces left on the board. + +```swift +extension Game { + func evaluate() -> Double { + var score: Double = 0 + for square in Square.all { + if let piece = board[square] { + score += piece.kind.relativeValue * (piece.color == .white ? 1.0 : -1.0) + } + } + return score +} +``` + +Since the values for black pieces are multiplied by -1 and white pieces by +1, material advantage on the board translates to a higher/lower evaluation. + +### Recursive Minimax + +Taking inspiration from the pseudocode above, we can define a minimax function in Swift as: + +```swift +func minimax(depth: Int, isMaximizingPlayer: Bool, alpha: Double, beta: Double) -> Double { + if depth == 0 || isFinished { + return evaluate() + } + + var alpha = alpha + var beta = beta + + if isMaximizingPlayer { + var maxEval: Double = -.infinity + + for move in availableMoves() { + try! execute(uncheckedMove: move) + let eval = minimax(depth: depth - 1, isMaximizingPlayer: false, alpha: alpha, beta: beta) + maxEval = max(maxEval, eval) + undoMove() + alpha = max(alpha, eval) + if beta <= alpha { + break + } + } + return maxEval + } else { + var minEval: Double = .infinity + for move in availableMoves() { + try! execute(uncheckedMove: move) + let eval = minimax(depth: depth - 1, isMaximizingPlayer: true, alpha: alpha, beta: beta) + minEval = min(minEval, eval) + if beta <= alpha { + break + } + } + return minEval + } +} +``` + +### Best Move + +We can now get a score for a move for a given depth, we wrap this up as a public method + +```swift +extension Game { + public func bestMove(depth: Int) -> Move? { + var bestMove: Move? + var bestValue: Double = (playerTurn == .white) ? -.infinity : .infinity + let alpha: Double = -.infinity + let beta: Double = .infinity + + for move in availableMoves() { + try! execute(uncheckedMove: move) + let moveValue = minimax(depth: depth - 1, isMaximizingPlayer: playerTurn.isBlack ? false : true, alpha: alpha, beta: beta) + undoMove() + if (playerTurn == .white && moveValue > bestValue) || (playerTurn == .black && moveValue < bestValue) { + bestValue = moveValue + bestMove = move + } + } + return bestMove + } +} +``` + + +## Usage + +```swift +import SwiftChessNeo + +let game = try! Game(position: Game.Position(fen: "8/5B2/k5p1/4rp2/8/8/PP6/1K3R2 w - - 0 1")!) +let move = game.bestMove(depth: 5) +``` + +Of course there are tons of improvements you can make to this naive algorithm. A better scoring function that understands the importance of piece positioning would make this even better. The [Chess Programming Wiki](https://www.chessprogramming.org/Main_Page) is an amazing resource if you want to learn more about this. diff --git a/Resources/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png b/Resources/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png Binary files differnew file mode 100644 index 0000000..4197443 --- /dev/null +++ b/Resources/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png diff --git a/docs/feed.rss b/docs/feed.rss index 81b5acb..dec39fa 100644 --- a/docs/feed.rss +++ b/docs/feed.rss @@ -4,7 +4,7 @@ <link rel="alternate" type="text/html" href="https://web.navan.dev/"/> <link rel="self" type="application/atom+xml" href="https://web.navan.dev/feed.rss"/> <subtitle>Rare Tips, Tricks and Posts</subtitle> - <updated>2024-04-13T22:30:15.472249</updated> + <updated>2024-04-18T00:47:15.150903</updated> <author> <name>Navan Chauhan</name> </author> @@ -6339,6 +6339,318 @@ DescriptionThe bag-of-words model is a simplifying representation used in NLP, i </entry> <entry> + <title>Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</title> + <link type="text/html" href="https://web.navan.dev/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html" /> + <id>https://web.navan.dev/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html</id> + <published>2024-04-17T23:20:00</published> + <updated>2024-04-17T23:20:00</updated> + <summary>Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax</summary> + <content type="html"> + <![CDATA[<h1 id="implementing-minimax-with-alpha-beta-pruning-for-a-simple-chess-ai-in-swift">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</h1> + +<p>Ever since Chess24 shut down, I have been looking to find a better way to follow Chess tournaments. A few weeks ago I decided to start working on a cross-platform (macOS/iOS) app using Lichess's API. +I heavily underestimated the amount of work it would take me to build something like this in SwiftUI. You not only need a library that can parse PGNs, but also a way to display those moves! </p> + +<p>I ended up forking <a rel="noopener" target="_blank" href="https://github.com/nvzqz/Sage">Sage</a> to <a rel="noopener" target="_blank" href="https://git.navan.dev/swift-chess-neo">swift-chess-neo</a>. I did have to patch the library to make it compatible with Swift 5 and create my own UI components using SwiftUI.</p> + +<p>Now that I had a working Chess library that could give me all legal moves in a position, I wondered if I could write a minimax implementation.</p> + +<h2 id="theory">Theory</h2> + +<p>Imagine you could look far ahead into the future and predict the perfect moves in a game for both sides. This is similar to Dr. Strange seeing all 14,000,605 alternate futures. +Knowing what works and what doesn't can help you decide what you should actually play.</p> + +<p>Using the example of Dr. Strange looking into the alternate futures, think of the Avengers winning being scored as +1, and Thanos winning being scored as -1. +The Avengers would try to maximize this score, whereas Thanos would try to minimize this. </p> + +<p>This is the idea of "minimax".</p> + +<p>Say we are playing a game of Tic-Tac-Toe, where us winning is scored positively and our opponent winning is scored negatively. We are going to try and maximize our score. A fresh game of Tic-Tac-Toe can be represented as a 3x3 grid. Which means, if we have the first turn we have 9 possible moves.</p> + +<p>Say we place an X in the top left corner:</p> + +<pre><code>------------- +| x | | | +------------- +| | | | +------------- +| | | | +------------- +</code></pre> + +<p>Now, our oponent has 8 different moves they can play. Say they play their move in the bottom right corner</p> + +<pre><code>------------- +| x | | | +------------- +| | | | +------------- +| | | o | +------------- +</code></pre> + +<p>We have 6 different moves we can play.</p> + +<p>It would take us ages to brute force each and every combination/permutation of moves by hand. A depth-first minimax algorithm for Tick-Tac-Toe would have a max-depth of 9 (since after 9 moves from the start, we would have exhausted the search space as there would be no more available moves).</p> + +<p>Since we cannot score an individual Tic-Tac-Toe position (technically we can), we can iterate through all moves (till we reach our max-depth) and then use these three terminal states:</p> + +<ul> +<li>+1 (You Win)</li> +<li>-1 (You Lose)</li> +<li>0 (Draw)</li> +</ul> + +<h3 id="pseudocode">Pseudocode</h3> + +<pre><code>function minimax(board, depth, isMaximizingPlayer): + score = evaluate(board) + + # +1 Win, -1 Lose, 0 Draw + if score == 1: return score + if score == -1: return score + + if boardFull(board): + return 0 + + if isMaximizingPlayer: + best = -infinity + + for each cell in board: + if cell is empty: + place X in cell + best = maximum of (best, minimax(board, depth + 1, false)) + remove X from cell + return best + + else: + best = infinity + + for each cell in board: + if cell is empyu: + place O in cell + best = minimum of (best, minimax(board, depth + 1, true)) + return best + +function evaluate(board): + if three consecutive Xs: return 1 + if three consecutive 0s: return -1 + + return 0 + +function boardFull(board): + if all cells are filled: return true + + else: + return false +</code></pre> + +<p>Think of each move as a node, and each node having multiple continuations (each continuing move can be represented as a node).</p> + +<h3 id="alpha-beta-pruning">Alpha-Beta Pruning</h3> + +<p>This is quiet inefficient, as this will comb through all <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mn>9</mn><mo>!</mo></mrow></math> or <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mn>362</mn><mo>,</mo><mn>880</mn></mrow></math> moves! Imagine iterating through the entire search space for a complex game like Chess. It would be impossible. Therefore we use a technique called Alpha-beta pruning wherein we reduce the number of nodes that we are evaluating. </p> + +<pre><code>function minimax(board, depth, isMaximizingPlayer, alpha, beta): + score = evaluate(board) + + # +1 Win, -1 Lose, 0 Draw + if score == 1: return score + if score == -1: return score + + if boardFull(board): + return 0 + + if isMaximizingPlayer: + best = -infinity + + for each cell in board: + if cell is empty: + place X in cell + best = maximum of (best, minimax(board, depth + 1, false, alpha, beta)) + remove X from cell + alpha = max(alpha, best) + if beta <= alpha: + break + return best + + else: + best = infinity + + for each cell in board: + if cell is empyu: + place O in cell + best = minimum of (best, minimax(board, depth + 1, true, alpha, beta)) + beta = min(beta, best) + if beta <= alpha: + break + return best +</code></pre> + +<p>Alpha and beta are initialized as <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mo>−</mo><mo>∞</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mo>+</mo><mo>∞</mo></mrow></math> respectively, with Alpha representing the best already explored option along the path to the root for the maximizer, and beta representing the best already explored option along the path to the root for the minimizer. If at any point beta is less than or equal to alpha, it means that the current branch does not need to be explored further because the parent node already has a better move elsewhere, thus "pruning" this node.</p> + +<p>Thus, to implement a model you can use minimax (or similar algorithms), you need to be able to describe the following:</p> + +<ul> +<li>Players +<ul> +<li>Player Count - How many players are there in this game? (Just 2)</li> +<li>Active Player - Whose turn is it?</li> +</ul></li> +<li>Game +<ul> +<li>Game State - How do you represent the current game state</li> +<li>Save/Load Game State - If you are trying out different moves, you need to be able to go to the original state before you move on to the next node</li> +<li>Score - Who is winning? Is the game over? Who lost?</li> +</ul></li> +<li>Moves +<ul> +<li>Valid Moves - What are all the legal moves in this game state? </li> +</ul></li> +</ul> + +<h2 id="show-me-the-code">Show me the code!</h2> + +<p>The chess library does a little bit of the heavy lifting by already providing methods to take care of the above requirements. Since we already have a way to find all possible moves in a position, we only need to figure out a few more functions/methods:</p> + +<ul> +<li>Evaluation/Score - We need to be able to numerically quantify the effect of a move. For a basic implementation we can just sum over the piece values.</li> +<li>Game state management - Since we explore different possible moves in our search space up to a certain depth, we need to be able to copy/save the state and reset it back to this state after we are done exploring all of our moves. Even though I did add a <code>setGame</code> method to the <code>Game</code> class, I use the <code>undoMove()</code> method</li> +</ul> + +<h3 id="evaluate">Evaluate</h3> + +<p>Each piece has a different relative value. Since "capturing" the king finishes the game, the king is given a really high value.</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">public</span> <span class="kd">struct</span> <span class="nc">Piece</span><span class="p">:</span> <span class="nb">Hashable</span><span class="p">,</span> <span class="n">CustomStringConvertible</span> <span class="p">{</span> + <span class="kd">public</span> <span class="kd">enum</span> <span class="nc">Kind</span><span class="p">:</span> <span class="nb">Int</span> <span class="p">{</span> + <span class="p">...</span> + <span class="kd">public</span> <span class="kd">var</span> <span class="nv">relativeValue</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">{</span> + <span class="k">switch</span> <span class="kc">self</span> <span class="p">{</span> + <span class="k">case</span> <span class="p">.</span><span class="n">pawn</span><span class="p">:</span> <span class="k">return</span> <span class="mi">1</span> + <span class="k">case</span> <span class="p">.</span><span class="n">knight</span><span class="p">:</span> <span class="k">return</span> <span class="mi">3</span> + <span class="k">case</span> <span class="p">.</span><span class="n">bishop</span><span class="p">:</span> <span class="k">return</span> <span class="mf">3.25</span> + <span class="k">case</span> <span class="p">.</span><span class="n">rook</span><span class="p">:</span> <span class="k">return</span> <span class="mi">5</span> + <span class="k">case</span> <span class="p">.</span><span class="n">queen</span><span class="p">:</span> <span class="k">return</span> <span class="mi">9</span> + <span class="k">case</span> <span class="p">.</span><span class="n">king</span><span class="p">:</span> <span class="k">return</span> <span class="mi">900</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="p">...</span> + <span class="p">}</span> + <span class="p">...</span> +<span class="p">}</span> +</code></pre> +</div> + +<p>We extend the <code>Game</code> class by adding an evaluate function that adds up the value of all the pieces left on the board.</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">extension</span> <span class="nc">Game</span> <span class="p">{</span> + <span class="kd">func</span> <span class="nf">evaluate</span><span class="p">()</span> <span class="p">-></span> <span class="nb">Double</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">score</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="mi">0</span> + <span class="k">for</span> <span class="n">square</span> <span class="k">in</span> <span class="n">Square</span><span class="p">.</span><span class="n">all</span> <span class="p">{</span> + <span class="k">if</span> <span class="kd">let</span> <span class="nv">piece</span> <span class="p">=</span> <span class="n">board</span><span class="p">[</span><span class="n">square</span><span class="p">]</span> <span class="p">{</span> + <span class="n">score</span> <span class="o">+=</span> <span class="n">piece</span><span class="p">.</span><span class="n">kind</span><span class="p">.</span><span class="n">relativeValue</span> <span class="o">*</span> <span class="p">(</span><span class="n">piece</span><span class="p">.</span><span class="n">color</span> <span class="p">==</span> <span class="p">.</span><span class="n">white</span> <span class="p">?</span> <span class="mf">1.0</span> <span class="p">:</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">)</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">score</span> +<span class="p">}</span> +</code></pre> +</div> + +<p>Since the values for black pieces are multiplied by -1 and white pieces by +1, material advantage on the board translates to a higher/lower evaluation.</p> + +<h3 id="recursive-minimax">Recursive Minimax</h3> + +<p>Taking inspiration from the pseudocode above, we can define a minimax function in Swift as:</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">func</span> <span class="nf">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="nb">Int</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="nb">Bool</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="nb">Double</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="nb">Double</span><span class="p">)</span> <span class="p">-></span> <span class="nb">Double</span> <span class="p">{</span> + <span class="k">if</span> <span class="n">depth</span> <span class="p">==</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">isFinished</span> <span class="p">{</span> + <span class="k">return</span> <span class="n">evaluate</span><span class="p">()</span> + <span class="p">}</span> + + <span class="kd">var</span> <span class="nv">alpha</span> <span class="p">=</span> <span class="n">alpha</span> + <span class="kd">var</span> <span class="nv">beta</span> <span class="p">=</span> <span class="n">beta</span> + + <span class="k">if</span> <span class="n">isMaximizingPlayer</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">maxEval</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="o">-</span><span class="p">.</span><span class="n">infinity</span> + + <span class="k">for</span> <span class="n">move</span> <span class="k">in</span> <span class="n">availableMoves</span><span class="p">()</span> <span class="p">{</span> + <span class="k">try</span><span class="p">!</span> <span class="n">execute</span><span class="p">(</span><span class="n">uncheckedMove</span><span class="p">:</span> <span class="n">move</span><span class="p">)</span> + <span class="kd">let</span> <span class="nv">eval</span> <span class="p">=</span> <span class="n">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="n">depth</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="kc">false</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="n">beta</span><span class="p">)</span> + <span class="n">maxEval</span> <span class="p">=</span> <span class="bp">max</span><span class="p">(</span><span class="n">maxEval</span><span class="p">,</span> <span class="n">eval</span><span class="p">)</span> + <span class="n">undoMove</span><span class="p">()</span> + <span class="n">alpha</span> <span class="p">=</span> <span class="bp">max</span><span class="p">(</span><span class="n">alpha</span><span class="p">,</span> <span class="n">eval</span><span class="p">)</span> + <span class="k">if</span> <span class="n">beta</span> <span class="o"><=</span> <span class="n">alpha</span> <span class="p">{</span> + <span class="k">break</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">maxEval</span> + <span class="p">}</span> <span class="k">else</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">minEval</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="p">.</span><span class="n">infinity</span> + <span class="k">for</span> <span class="n">move</span> <span class="k">in</span> <span class="n">availableMoves</span><span class="p">()</span> <span class="p">{</span> + <span class="k">try</span><span class="p">!</span> <span class="n">execute</span><span class="p">(</span><span class="n">uncheckedMove</span><span class="p">:</span> <span class="n">move</span><span class="p">)</span> + <span class="kd">let</span> <span class="nv">eval</span> <span class="p">=</span> <span class="n">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="n">depth</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="kc">true</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="n">beta</span><span class="p">)</span> + <span class="n">minEval</span> <span class="p">=</span> <span class="bp">min</span><span class="p">(</span><span class="n">minEval</span><span class="p">,</span> <span class="n">eval</span><span class="p">)</span> + <span class="k">if</span> <span class="n">beta</span> <span class="o"><=</span> <span class="n">alpha</span> <span class="p">{</span> + <span class="k">break</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">minEval</span> + <span class="p">}</span> +<span class="p">}</span> +</code></pre> +</div> + +<h3 id="best-move">Best Move</h3> + +<p>We can now get a score for a move for a given depth, we wrap this up as a public method</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">extension</span> <span class="nc">Game</span> <span class="p">{</span> + <span class="kd">public</span> <span class="kd">func</span> <span class="nf">bestMove</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="nb">Int</span><span class="p">)</span> <span class="p">-></span> <span class="n">Move</span><span class="p">?</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">bestMove</span><span class="p">:</span> <span class="n">Move</span><span class="p">?</span> + <span class="kd">var</span> <span class="nv">bestValue</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="p">(</span><span class="n">playerTurn</span> <span class="p">==</span> <span class="p">.</span><span class="n">white</span><span class="p">)</span> <span class="p">?</span> <span class="o">-</span><span class="p">.</span><span class="n">infinity</span> <span class="p">:</span> <span class="p">.</span><span class="n">infinity</span> + <span class="kd">let</span> <span class="nv">alpha</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="o">-</span><span class="p">.</span><span class="n">infinity</span> + <span class="kd">let</span> <span class="nv">beta</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="p">.</span><span class="n">infinity</span> + + <span class="k">for</span> <span class="n">move</span> <span class="k">in</span> <span class="n">availableMoves</span><span class="p">()</span> <span class="p">{</span> + <span class="k">try</span><span class="p">!</span> <span class="n">execute</span><span class="p">(</span><span class="n">uncheckedMove</span><span class="p">:</span> <span class="n">move</span><span class="p">)</span> + <span class="kd">let</span> <span class="nv">moveValue</span> <span class="p">=</span> <span class="n">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="n">depth</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="n">playerTurn</span><span class="p">.</span><span class="n">isBlack</span> <span class="p">?</span> <span class="kc">false</span> <span class="p">:</span> <span class="kc">true</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="n">beta</span><span class="p">)</span> + <span class="n">undoMove</span><span class="p">()</span> + <span class="k">if</span> <span class="p">(</span><span class="n">playerTurn</span> <span class="p">==</span> <span class="p">.</span><span class="n">white</span> <span class="o">&&</span> <span class="n">moveValue</span> <span class="o">></span> <span class="n">bestValue</span><span class="p">)</span> <span class="o">||</span> <span class="p">(</span><span class="n">playerTurn</span> <span class="p">==</span> <span class="p">.</span><span class="n">black</span> <span class="o">&&</span> <span class="n">moveValue</span> <span class="o"><</span> <span class="n">bestValue</span><span class="p">)</span> <span class="p">{</span> + <span class="n">bestValue</span> <span class="p">=</span> <span class="n">moveValue</span> + <span class="n">bestMove</span> <span class="p">=</span> <span class="n">move</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">bestMove</span> + <span class="p">}</span> +<span class="p">}</span> +</code></pre> +</div> + +<h2 id="usage">Usage</h2> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">import</span> <span class="nc">SwiftChessNeo</span> + +<span class="kd">let</span> <span class="nv">game</span> <span class="p">=</span> <span class="k">try</span><span class="p">!</span> <span class="n">Game</span><span class="p">(</span><span class="n">position</span><span class="p">:</span> <span class="n">Game</span><span class="p">.</span><span class="n">Position</span><span class="p">(</span><span class="n">fen</span><span class="p">:</span> <span class="s">"8/5B2/k5p1/4rp2/8/8/PP6/1K3R2 w - - 0 1"</span><span class="p">)</span><span class="o">!</span><span class="p">)</span> +<span class="kd">let</span> <span class="nv">move</span> <span class="p">=</span> <span class="n">game</span><span class="p">.</span><span class="n">bestMove</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="mi">5</span><span class="p">)</span> +</code></pre> +</div> + +<p>Of course there are tons of improvements you can make to this naive algorithm. A better scoring function that understands the importance of piece positioning would make this even better. The <a rel="noopener" target="_blank" href="https://www.chessprogramming.org/Main_Page">Chess Programming Wiki</a> is an amazing resource if you want to learn more about this.</p> +]]> + </content> + <author> + <name>Navan Chauhan</name> + <email>blog@navan.email</email> + </author> + </entry> + + <entry> <title>RSS Feed written in HTML + JavaScript</title> <link type="text/html" href="https://web.navan.dev/posts/2020-12-1-HTML-JS-RSS-Feed.html" /> <id>https://web.navan.dev/posts/2020-12-1-HTML-JS-RSS-Feed.html</id> diff --git a/docs/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png b/docs/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png Binary files differnew file mode 100644 index 0000000..4197443 --- /dev/null +++ b/docs/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png diff --git a/docs/index.html b/docs/index.html index 1f22460..d54cfb3 100644 --- a/docs/index.html +++ b/docs/index.html @@ -88,6 +88,24 @@ lead.innerText = new_phrase; <h1>Recent Posts</h1> <ul> + <li><a href="/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</a> + <ul> + <li>Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax</li> + <li>Published On: 2024-04-17 23:20</li> + <li>Tags: + + <a href='/tags/Swift.html'>Swift</a>, + + <a href='/tags/Chess.html'>Chess</a>, + + <a href='/tags/Game Theory.html'>Game Theory</a>, + + <a href='/tags/Mathematics.html'>Mathematics</a> + + </ul> + </li> + + <li><a href="/posts/2024-03-28-Running-ADFRSuite-on-arm64-Macs.html">Fixing ADFRSuite for Apple Silicon</a> <ul> <li>Fixing ADFRsuite on M1/MX chip Macs - CLI Tools</li> @@ -108,7 +126,7 @@ lead.innerText = new_phrase; <li>Published On: 2024-03-26 15:36</li> <li>Tags: - <a href='/tags/mathematics.html'>mathematics</a> + <a href='/tags/Mathematics.html'>Mathematics</a> </ul> </li> @@ -146,20 +164,6 @@ lead.innerText = new_phrase; </li> - <li><a href="/posts/2024-02-26-control-element-under-another-element-html-css.html">Interacting with underlying element in HTML</a> - <ul> - <li>With CSS you can disable any interactions with an element and directly control the underlying element</li> - <li>Published On: 2024-02-26 11:57</li> - <li>Tags: - - <a href='/tags/HTML.html'>HTML</a>, - - <a href='/tags/CSS.html'>CSS</a> - - </ul> - </li> - - </ul> <b>For all posts go to <a href="/posts">Posts</a></b> diff --git a/docs/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html b/docs/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html new file mode 100644 index 0000000..5683da6 --- /dev/null +++ b/docs/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html @@ -0,0 +1,387 @@ +<!DOCTYPE html> +<html lang="en"> +<head> + + <meta http-equiv="X-UA-Compatible" content="IE=edge"> + <meta http-equiv="content-type" content="text/html; charset=utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="theme-color" content="#6a9fb5"> + + <title>Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</title> + + <!-- + <link rel="stylesheet" href="https://unpkg.com/latex.css/style.min.css" /> + --> + + <link rel="stylesheet" href="/assets/c-hyde.css" /> + + <link rel="stylesheet" href="http://fonts.googleapis.com/css?family=PT+Sans:400,400italic,700|Abril+Fatface"> + + <link rel="stylesheet" href="/assets/main.css" /> + <meta charset="utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="og:site_name" content="Navan Chauhan" /> + <link rel="canonical" href="https://web.navan.dev/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html" /> + <meta name="twitter:url" content="https://web.navan.dev/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html" /> + <meta name="og:url" content="https://web.navan.dev/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html" /> + <meta name="twitter:title" content="Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift" /> + <meta name="og:title" content="Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift" /> + <meta name="description" content="Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax" /> + <meta name="twitter:description" content="Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax" /> + <meta name="og:description" content="Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax" /> + <meta name="twitter:card" content="summary_large_image" /> + <meta name="viewport" content="width=device-width, initial-scale=1.0" /> + <link rel="shortcut icon" href="/images/favicon.png" type="image/png" /> + <link href="/feed.rss" type="application/atom+xml" rel="alternate" title="Sitewide Atom feed" /> + <meta name="twitter:image" content="https://web.navan.dev/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png" /> + <meta name="og:image" content="https://web.navan.dev/images/opengraph/posts/2024-04-17-implementing-minimax-for-chess-in-swift.png" /> + <meta name="google-site-verification" content="LVeSZxz-QskhbEjHxOi7-BM5dDxTg53x2TwrjFxfL0k" /> + <script data-goatcounter="https://navanchauhan.goatcounter.com/count" + async src="//gc.zgo.at/count.js"></script> + <script defer data-domain="web.navan.dev" src="https://plausible.io/js/plausible.js"></script> + <link rel="manifest" href="/manifest.json" /> + +</head> +<body class="theme-base-0d"> + <div class="sidebar"> + <div class="container sidebar-sticky"> + <div class="sidebar-about"> + <h1><a href="/">Navan</a></h1> + <p class="lead" id="random-lead">Alea iacta est.</p> + </div> + + <ul class="sidebar-nav"> + <li><a class="sidebar-nav-item" href="/about/">about/links</a></li> + <li><a class="sidebar-nav-item" href="/posts/">posts</a></li> + <li><a class="sidebar-nav-item" href="/3D-Designs/">3D designs</a></li> + <li><a class="sidebar-nav-item" href="/feed.rss">RSS Feed</a></li> + <li><a class="sidebar-nav-item" href="/colophon/">colophon</a></li> + </ul> + <div class="copyright"><p>© 2019-2024. Navan Chauhan <br> <a href="/feed.rss">RSS</a></p></div> + </div> +</div> + +<script> +let phrases = [ + "Something Funny", "Veni, vidi, vici", "Alea iacta est", "In vino veritas", "Acta, non verba", "Castigat ridendo mores", + "Cui bono?", "Memento vivere", "अहम् ब्रह्मास्मि", "अनुगच्छतु प्रवाहं", "चरन्मार्गान्विजानाति", "coq de cheval", "我愛啤酒" + ]; + +let new_phrase = phrases[Math.floor(Math.random()*phrases.length)]; + +let lead = document.getElementById("random-lead"); +lead.innerText = new_phrase; +</script> + <div class="content container"> + + <div class="post"> + <h1 id="implementing-minimax-with-alpha-beta-pruning-for-a-simple-chess-ai-in-swift">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</h1> + +<p>Ever since Chess24 shut down, I have been looking to find a better way to follow Chess tournaments. A few weeks ago I decided to start working on a cross-platform (macOS/iOS) app using Lichess's API. +I heavily underestimated the amount of work it would take me to build something like this in SwiftUI. You not only need a library that can parse PGNs, but also a way to display those moves! </p> + +<p>I ended up forking <a rel="noopener" target="_blank" href="https://github.com/nvzqz/Sage">Sage</a> to <a rel="noopener" target="_blank" href="https://git.navan.dev/swift-chess-neo">swift-chess-neo</a>. I did have to patch the library to make it compatible with Swift 5 and create my own UI components using SwiftUI.</p> + +<p>Now that I had a working Chess library that could give me all legal moves in a position, I wondered if I could write a minimax implementation.</p> + +<h2 id="theory">Theory</h2> + +<p>Imagine you could look far ahead into the future and predict the perfect moves in a game for both sides. This is similar to Dr. Strange seeing all 14,000,605 alternate futures. +Knowing what works and what doesn't can help you decide what you should actually play.</p> + +<p>Using the example of Dr. Strange looking into the alternate futures, think of the Avengers winning being scored as +1, and Thanos winning being scored as -1. +The Avengers would try to maximize this score, whereas Thanos would try to minimize this. </p> + +<p>This is the idea of "minimax".</p> + +<p>Say we are playing a game of Tic-Tac-Toe, where us winning is scored positively and our opponent winning is scored negatively. We are going to try and maximize our score. A fresh game of Tic-Tac-Toe can be represented as a 3x3 grid. Which means, if we have the first turn we have 9 possible moves.</p> + +<p>Say we place an X in the top left corner:</p> + +<pre><code>------------- +| x | | | +------------- +| | | | +------------- +| | | | +------------- +</code></pre> + +<p>Now, our oponent has 8 different moves they can play. Say they play their move in the bottom right corner</p> + +<pre><code>------------- +| x | | | +------------- +| | | | +------------- +| | | o | +------------- +</code></pre> + +<p>We have 6 different moves we can play.</p> + +<p>It would take us ages to brute force each and every combination/permutation of moves by hand. A depth-first minimax algorithm for Tick-Tac-Toe would have a max-depth of 9 (since after 9 moves from the start, we would have exhausted the search space as there would be no more available moves).</p> + +<p>Since we cannot score an individual Tic-Tac-Toe position (technically we can), we can iterate through all moves (till we reach our max-depth) and then use these three terminal states:</p> + +<ul> +<li>+1 (You Win)</li> +<li>-1 (You Lose)</li> +<li>0 (Draw)</li> +</ul> + +<h3 id="pseudocode">Pseudocode</h3> + +<pre><code>function minimax(board, depth, isMaximizingPlayer): + score = evaluate(board) + + # +1 Win, -1 Lose, 0 Draw + if score == 1: return score + if score == -1: return score + + if boardFull(board): + return 0 + + if isMaximizingPlayer: + best = -infinity + + for each cell in board: + if cell is empty: + place X in cell + best = maximum of (best, minimax(board, depth + 1, false)) + remove X from cell + return best + + else: + best = infinity + + for each cell in board: + if cell is empyu: + place O in cell + best = minimum of (best, minimax(board, depth + 1, true)) + return best + +function evaluate(board): + if three consecutive Xs: return 1 + if three consecutive 0s: return -1 + + return 0 + +function boardFull(board): + if all cells are filled: return true + + else: + return false +</code></pre> + +<p>Think of each move as a node, and each node having multiple continuations (each continuing move can be represented as a node).</p> + +<h3 id="alpha-beta-pruning">Alpha-Beta Pruning</h3> + +<p>This is quiet inefficient, as this will comb through all <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mn>9</mn><mo>!</mo></mrow></math> or <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mn>362</mn><mo>,</mo><mn>880</mn></mrow></math> moves! Imagine iterating through the entire search space for a complex game like Chess. It would be impossible. Therefore we use a technique called Alpha-beta pruning wherein we reduce the number of nodes that we are evaluating. </p> + +<pre><code>function minimax(board, depth, isMaximizingPlayer, alpha, beta): + score = evaluate(board) + + # +1 Win, -1 Lose, 0 Draw + if score == 1: return score + if score == -1: return score + + if boardFull(board): + return 0 + + if isMaximizingPlayer: + best = -infinity + + for each cell in board: + if cell is empty: + place X in cell + best = maximum of (best, minimax(board, depth + 1, false, alpha, beta)) + remove X from cell + alpha = max(alpha, best) + if beta <= alpha: + break + return best + + else: + best = infinity + + for each cell in board: + if cell is empyu: + place O in cell + best = minimum of (best, minimax(board, depth + 1, true, alpha, beta)) + beta = min(beta, best) + if beta <= alpha: + break + return best +</code></pre> + +<p>Alpha and beta are initialized as <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mo>−</mo><mo>∞</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mo>+</mo><mo>∞</mo></mrow></math> respectively, with Alpha representing the best already explored option along the path to the root for the maximizer, and beta representing the best already explored option along the path to the root for the minimizer. If at any point beta is less than or equal to alpha, it means that the current branch does not need to be explored further because the parent node already has a better move elsewhere, thus "pruning" this node.</p> + +<p>Thus, to implement a model you can use minimax (or similar algorithms), you need to be able to describe the following:</p> + +<ul> +<li>Players +<ul> +<li>Player Count - How many players are there in this game? (Just 2)</li> +<li>Active Player - Whose turn is it?</li> +</ul></li> +<li>Game +<ul> +<li>Game State - How do you represent the current game state</li> +<li>Save/Load Game State - If you are trying out different moves, you need to be able to go to the original state before you move on to the next node</li> +<li>Score - Who is winning? Is the game over? Who lost?</li> +</ul></li> +<li>Moves +<ul> +<li>Valid Moves - What are all the legal moves in this game state? </li> +</ul></li> +</ul> + +<h2 id="show-me-the-code">Show me the code!</h2> + +<p>The chess library does a little bit of the heavy lifting by already providing methods to take care of the above requirements. Since we already have a way to find all possible moves in a position, we only need to figure out a few more functions/methods:</p> + +<ul> +<li>Evaluation/Score - We need to be able to numerically quantify the effect of a move. For a basic implementation we can just sum over the piece values.</li> +<li>Game state management - Since we explore different possible moves in our search space up to a certain depth, we need to be able to copy/save the state and reset it back to this state after we are done exploring all of our moves. Even though I did add a <code>setGame</code> method to the <code>Game</code> class, I use the <code>undoMove()</code> method</li> +</ul> + +<h3 id="evaluate">Evaluate</h3> + +<p>Each piece has a different relative value. Since "capturing" the king finishes the game, the king is given a really high value.</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">public</span> <span class="kd">struct</span> <span class="nc">Piece</span><span class="p">:</span> <span class="nb">Hashable</span><span class="p">,</span> <span class="n">CustomStringConvertible</span> <span class="p">{</span> + <span class="kd">public</span> <span class="kd">enum</span> <span class="nc">Kind</span><span class="p">:</span> <span class="nb">Int</span> <span class="p">{</span> + <span class="p">...</span> + <span class="kd">public</span> <span class="kd">var</span> <span class="nv">relativeValue</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">{</span> + <span class="k">switch</span> <span class="kc">self</span> <span class="p">{</span> + <span class="k">case</span> <span class="p">.</span><span class="n">pawn</span><span class="p">:</span> <span class="k">return</span> <span class="mi">1</span> + <span class="k">case</span> <span class="p">.</span><span class="n">knight</span><span class="p">:</span> <span class="k">return</span> <span class="mi">3</span> + <span class="k">case</span> <span class="p">.</span><span class="n">bishop</span><span class="p">:</span> <span class="k">return</span> <span class="mf">3.25</span> + <span class="k">case</span> <span class="p">.</span><span class="n">rook</span><span class="p">:</span> <span class="k">return</span> <span class="mi">5</span> + <span class="k">case</span> <span class="p">.</span><span class="n">queen</span><span class="p">:</span> <span class="k">return</span> <span class="mi">9</span> + <span class="k">case</span> <span class="p">.</span><span class="n">king</span><span class="p">:</span> <span class="k">return</span> <span class="mi">900</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="p">...</span> + <span class="p">}</span> + <span class="p">...</span> +<span class="p">}</span> +</code></pre> +</div> + +<p>We extend the <code>Game</code> class by adding an evaluate function that adds up the value of all the pieces left on the board.</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">extension</span> <span class="nc">Game</span> <span class="p">{</span> + <span class="kd">func</span> <span class="nf">evaluate</span><span class="p">()</span> <span class="p">-></span> <span class="nb">Double</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">score</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="mi">0</span> + <span class="k">for</span> <span class="n">square</span> <span class="k">in</span> <span class="n">Square</span><span class="p">.</span><span class="n">all</span> <span class="p">{</span> + <span class="k">if</span> <span class="kd">let</span> <span class="nv">piece</span> <span class="p">=</span> <span class="n">board</span><span class="p">[</span><span class="n">square</span><span class="p">]</span> <span class="p">{</span> + <span class="n">score</span> <span class="o">+=</span> <span class="n">piece</span><span class="p">.</span><span class="n">kind</span><span class="p">.</span><span class="n">relativeValue</span> <span class="o">*</span> <span class="p">(</span><span class="n">piece</span><span class="p">.</span><span class="n">color</span> <span class="p">==</span> <span class="p">.</span><span class="n">white</span> <span class="p">?</span> <span class="mf">1.0</span> <span class="p">:</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">)</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">score</span> +<span class="p">}</span> +</code></pre> +</div> + +<p>Since the values for black pieces are multiplied by -1 and white pieces by +1, material advantage on the board translates to a higher/lower evaluation.</p> + +<h3 id="recursive-minimax">Recursive Minimax</h3> + +<p>Taking inspiration from the pseudocode above, we can define a minimax function in Swift as:</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">func</span> <span class="nf">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="nb">Int</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="nb">Bool</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="nb">Double</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="nb">Double</span><span class="p">)</span> <span class="p">-></span> <span class="nb">Double</span> <span class="p">{</span> + <span class="k">if</span> <span class="n">depth</span> <span class="p">==</span> <span class="mi">0</span> <span class="o">||</span> <span class="n">isFinished</span> <span class="p">{</span> + <span class="k">return</span> <span class="n">evaluate</span><span class="p">()</span> + <span class="p">}</span> + + <span class="kd">var</span> <span class="nv">alpha</span> <span class="p">=</span> <span class="n">alpha</span> + <span class="kd">var</span> <span class="nv">beta</span> <span class="p">=</span> <span class="n">beta</span> + + <span class="k">if</span> <span class="n">isMaximizingPlayer</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">maxEval</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="o">-</span><span class="p">.</span><span class="n">infinity</span> + + <span class="k">for</span> <span class="n">move</span> <span class="k">in</span> <span class="n">availableMoves</span><span class="p">()</span> <span class="p">{</span> + <span class="k">try</span><span class="p">!</span> <span class="n">execute</span><span class="p">(</span><span class="n">uncheckedMove</span><span class="p">:</span> <span class="n">move</span><span class="p">)</span> + <span class="kd">let</span> <span class="nv">eval</span> <span class="p">=</span> <span class="n">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="n">depth</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="kc">false</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="n">beta</span><span class="p">)</span> + <span class="n">maxEval</span> <span class="p">=</span> <span class="bp">max</span><span class="p">(</span><span class="n">maxEval</span><span class="p">,</span> <span class="n">eval</span><span class="p">)</span> + <span class="n">undoMove</span><span class="p">()</span> + <span class="n">alpha</span> <span class="p">=</span> <span class="bp">max</span><span class="p">(</span><span class="n">alpha</span><span class="p">,</span> <span class="n">eval</span><span class="p">)</span> + <span class="k">if</span> <span class="n">beta</span> <span class="o"><=</span> <span class="n">alpha</span> <span class="p">{</span> + <span class="k">break</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">maxEval</span> + <span class="p">}</span> <span class="k">else</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">minEval</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="p">.</span><span class="n">infinity</span> + <span class="k">for</span> <span class="n">move</span> <span class="k">in</span> <span class="n">availableMoves</span><span class="p">()</span> <span class="p">{</span> + <span class="k">try</span><span class="p">!</span> <span class="n">execute</span><span class="p">(</span><span class="n">uncheckedMove</span><span class="p">:</span> <span class="n">move</span><span class="p">)</span> + <span class="kd">let</span> <span class="nv">eval</span> <span class="p">=</span> <span class="n">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="n">depth</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="kc">true</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="n">beta</span><span class="p">)</span> + <span class="n">minEval</span> <span class="p">=</span> <span class="bp">min</span><span class="p">(</span><span class="n">minEval</span><span class="p">,</span> <span class="n">eval</span><span class="p">)</span> + <span class="k">if</span> <span class="n">beta</span> <span class="o"><=</span> <span class="n">alpha</span> <span class="p">{</span> + <span class="k">break</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">minEval</span> + <span class="p">}</span> +<span class="p">}</span> +</code></pre> +</div> + +<h3 id="best-move">Best Move</h3> + +<p>We can now get a score for a move for a given depth, we wrap this up as a public method</p> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">extension</span> <span class="nc">Game</span> <span class="p">{</span> + <span class="kd">public</span> <span class="kd">func</span> <span class="nf">bestMove</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="nb">Int</span><span class="p">)</span> <span class="p">-></span> <span class="n">Move</span><span class="p">?</span> <span class="p">{</span> + <span class="kd">var</span> <span class="nv">bestMove</span><span class="p">:</span> <span class="n">Move</span><span class="p">?</span> + <span class="kd">var</span> <span class="nv">bestValue</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="p">(</span><span class="n">playerTurn</span> <span class="p">==</span> <span class="p">.</span><span class="n">white</span><span class="p">)</span> <span class="p">?</span> <span class="o">-</span><span class="p">.</span><span class="n">infinity</span> <span class="p">:</span> <span class="p">.</span><span class="n">infinity</span> + <span class="kd">let</span> <span class="nv">alpha</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="o">-</span><span class="p">.</span><span class="n">infinity</span> + <span class="kd">let</span> <span class="nv">beta</span><span class="p">:</span> <span class="nb">Double</span> <span class="p">=</span> <span class="p">.</span><span class="n">infinity</span> + + <span class="k">for</span> <span class="n">move</span> <span class="k">in</span> <span class="n">availableMoves</span><span class="p">()</span> <span class="p">{</span> + <span class="k">try</span><span class="p">!</span> <span class="n">execute</span><span class="p">(</span><span class="n">uncheckedMove</span><span class="p">:</span> <span class="n">move</span><span class="p">)</span> + <span class="kd">let</span> <span class="nv">moveValue</span> <span class="p">=</span> <span class="n">minimax</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="n">depth</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">isMaximizingPlayer</span><span class="p">:</span> <span class="n">playerTurn</span><span class="p">.</span><span class="n">isBlack</span> <span class="p">?</span> <span class="kc">false</span> <span class="p">:</span> <span class="kc">true</span><span class="p">,</span> <span class="n">alpha</span><span class="p">:</span> <span class="n">alpha</span><span class="p">,</span> <span class="n">beta</span><span class="p">:</span> <span class="n">beta</span><span class="p">)</span> + <span class="n">undoMove</span><span class="p">()</span> + <span class="k">if</span> <span class="p">(</span><span class="n">playerTurn</span> <span class="p">==</span> <span class="p">.</span><span class="n">white</span> <span class="o">&&</span> <span class="n">moveValue</span> <span class="o">></span> <span class="n">bestValue</span><span class="p">)</span> <span class="o">||</span> <span class="p">(</span><span class="n">playerTurn</span> <span class="p">==</span> <span class="p">.</span><span class="n">black</span> <span class="o">&&</span> <span class="n">moveValue</span> <span class="o"><</span> <span class="n">bestValue</span><span class="p">)</span> <span class="p">{</span> + <span class="n">bestValue</span> <span class="p">=</span> <span class="n">moveValue</span> + <span class="n">bestMove</span> <span class="p">=</span> <span class="n">move</span> + <span class="p">}</span> + <span class="p">}</span> + <span class="k">return</span> <span class="n">bestMove</span> + <span class="p">}</span> +<span class="p">}</span> +</code></pre> +</div> + +<h2 id="usage">Usage</h2> + +<div class="codehilite"> +<pre><span></span><code><span class="kd">import</span> <span class="nc">SwiftChessNeo</span> + +<span class="kd">let</span> <span class="nv">game</span> <span class="p">=</span> <span class="k">try</span><span class="p">!</span> <span class="n">Game</span><span class="p">(</span><span class="n">position</span><span class="p">:</span> <span class="n">Game</span><span class="p">.</span><span class="n">Position</span><span class="p">(</span><span class="n">fen</span><span class="p">:</span> <span class="s">"8/5B2/k5p1/4rp2/8/8/PP6/1K3R2 w - - 0 1"</span><span class="p">)</span><span class="o">!</span><span class="p">)</span> +<span class="kd">let</span> <span class="nv">move</span> <span class="p">=</span> <span class="n">game</span><span class="p">.</span><span class="n">bestMove</span><span class="p">(</span><span class="n">depth</span><span class="p">:</span> <span class="mi">5</span><span class="p">)</span> +</code></pre> +</div> + +<p>Of course there are tons of improvements you can make to this naive algorithm. A better scoring function that understands the importance of piece positioning would make this even better. The <a rel="noopener" target="_blank" href="https://www.chessprogramming.org/Main_Page">Chess Programming Wiki</a> is an amazing resource if you want to learn more about this.</p> + + </div> + <blockquote>If you have scrolled this far, consider subscribing to my mailing list <a href="https://listmonk.navan.dev/subscription/form">here.</a> You can subscribe to either a specific type of post you are interested in, or subscribe to everything with the "Everything" list.</blockquote> + <script data-isso="https://comments.navan.dev/" + src="https://comments.navan.dev/js/embed.min.js"></script> + <section id="isso-thread"> + <noscript>Javascript needs to be activated to view comments.</noscript> + </section> + + </div> + <script src="assets/manup.min.js"></script> + <script src="/pwabuilder-sw-register.js"></script> +</body> +</html>
\ No newline at end of file diff --git a/docs/posts/index.html b/docs/posts/index.html index 7e6f7e4..e1c1cdd 100644 --- a/docs/posts/index.html +++ b/docs/posts/index.html @@ -84,6 +84,23 @@ lead.innerText = new_phrase; <ul> + <li><a href="/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</a></li> + <ul> + <li>Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax</li> + <li>Published On: 2024-04-17 23:20</li> + <li>Tags: + + <a href='/tags/Swift.html'>Swift</a>, + + <a href='/tags/Chess.html'>Chess</a>, + + <a href='/tags/Game Theory.html'>Game Theory</a>, + + <a href='/tags/Mathematics.html'>Mathematics</a> + + </ul> + + <li><a href="/posts/2024-03-28-Running-ADFRSuite-on-arm64-Macs.html">Fixing ADFRSuite for Apple Silicon</a></li> <ul> <li>Fixing ADFRsuite on M1/MX chip Macs - CLI Tools</li> @@ -103,7 +120,7 @@ lead.innerText = new_phrase; <li>Published On: 2024-03-26 15:36</li> <li>Tags: - <a href='/tags/mathematics.html'>mathematics</a> + <a href='/tags/Mathematics.html'>Mathematics</a> </ul> diff --git a/docs/tags/Chess.html b/docs/tags/Chess.html new file mode 100644 index 0000000..1ffdc18 --- /dev/null +++ b/docs/tags/Chess.html @@ -0,0 +1,108 @@ +<!DOCTYPE html> +<html lang="en"> +<head> + + <meta http-equiv="X-UA-Compatible" content="IE=edge"> + <meta http-equiv="content-type" content="text/html; charset=utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="theme-color" content="#6a9fb5"> + + <title>"Chess"</title> + + <!-- + <link rel="stylesheet" href="https://unpkg.com/latex.css/style.min.css" /> + --> + + <link rel="stylesheet" href="/assets/c-hyde.css" /> + + <link rel="stylesheet" href="http://fonts.googleapis.com/css?family=PT+Sans:400,400italic,700|Abril+Fatface"> + + <link rel="stylesheet" href="/assets/main.css" /> + <meta charset="utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="og:site_name" content="Navan Chauhan" /> + <link rel="canonical" href="https://web.navan.dev" /> + <meta name="twitter:url" content="https://web.navan.dev" /> + <meta name="og:url" content="https://web.navan.dev" /> + <meta name="twitter:title" content="Hey - Home" /> + <meta name="og:title" content="Hey - Home" /> + <meta name="description" content="code snippets, long-form rants, and tutorials" /> + <meta name="twitter:description" content="code snippets, long-form rants, and tutorials" /> + <meta name="og:description" content="code snippets, long-form rants, and tutorials" /> + <meta name="twitter:card" content="summary_large_image" /> + <meta name="viewport" content="width=device-width, initial-scale=1.0" /> + <link rel="shortcut icon" href="/images/favicon.png" type="image/png" /> + <link href="/feed.rss" type="application/atom+xml" rel="alternate" title="Sitewide Atom feed" /> + <meta name="twitter:image" content="https://web.navan.dev/images/logo.png" /> + <meta name="og:image" content="https://web.navan.dev/images/logo.png" /> + <meta name="google-site-verification" content="LVeSZxz-QskhbEjHxOi7-BM5dDxTg53x2TwrjFxfL0k" /> + <script data-goatcounter="https://navanchauhan.goatcounter.com/count" + async src="//gc.zgo.at/count.js"></script> + <script defer data-domain="web.navan.dev" src="https://plausible.io/js/plausible.js"></script> + <link rel="manifest" href="/manifest.json" /> + +</head> +<body class="theme-base-0d"> + <div class="sidebar"> + <div class="container sidebar-sticky"> + <div class="sidebar-about"> + <h1><a href="/">Navan</a></h1> + <p class="lead" id="random-lead">Alea iacta est.</p> + </div> + + <ul class="sidebar-nav"> + <li><a class="sidebar-nav-item" href="/about/">about/links</a></li> + <li><a class="sidebar-nav-item" href="/posts/">posts</a></li> + <li><a class="sidebar-nav-item" href="/3D-Designs/">3D designs</a></li> + <li><a class="sidebar-nav-item" href="/feed.rss">RSS Feed</a></li> + <li><a class="sidebar-nav-item" href="/colophon/">colophon</a></li> + </ul> + <div class="copyright"><p>© 2019-2024. Navan Chauhan <br> <a href="/feed.rss">RSS</a></p></div> + </div> +</div> + +<script> +let phrases = [ + "Something Funny", "Veni, vidi, vici", "Alea iacta est", "In vino veritas", "Acta, non verba", "Castigat ridendo mores", + "Cui bono?", "Memento vivere", "अहम् ब्रह्मास्मि", "अनुगच्छतु प्रवाहं", "चरन्मार्गान्विजानाति", "coq de cheval", "我愛啤酒" + ]; + +let new_phrase = phrases[Math.floor(Math.random()*phrases.length)]; + +let lead = document.getElementById("random-lead"); +lead.innerText = new_phrase; +</script> + <div class="content container"> + + +<main> + <h1>Chess</h1><p>Posts tagged 'Chess'</p> +</main> + +<ul> + + <li><a href="/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</a></li> + <ul> + <li>Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax</li> + <li>Published On: 2024-04-17 23:20</li> + <li>Tags: + + <a href='/tags/Swift.html'>Swift</a>, + + <a href='/tags/Chess.html'>Chess</a>, + + <a href='/tags/Game Theory.html'>Game Theory</a>, + + <a href='/tags/Mathematics.html'>Mathematics</a> + + </ul> + + +</ul> + + + </div> + <script src="assets/manup.min.js"></script> + <script src="/pwabuilder-sw-register.js"></script> +</body> +</html>
\ No newline at end of file diff --git a/docs/tags/Game Theory.html b/docs/tags/Game Theory.html new file mode 100644 index 0000000..95aed04 --- /dev/null +++ b/docs/tags/Game Theory.html @@ -0,0 +1,108 @@ +<!DOCTYPE html> +<html lang="en"> +<head> + + <meta http-equiv="X-UA-Compatible" content="IE=edge"> + <meta http-equiv="content-type" content="text/html; charset=utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="theme-color" content="#6a9fb5"> + + <title>"Game Theory"</title> + + <!-- + <link rel="stylesheet" href="https://unpkg.com/latex.css/style.min.css" /> + --> + + <link rel="stylesheet" href="/assets/c-hyde.css" /> + + <link rel="stylesheet" href="http://fonts.googleapis.com/css?family=PT+Sans:400,400italic,700|Abril+Fatface"> + + <link rel="stylesheet" href="/assets/main.css" /> + <meta charset="utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="og:site_name" content="Navan Chauhan" /> + <link rel="canonical" href="https://web.navan.dev" /> + <meta name="twitter:url" content="https://web.navan.dev" /> + <meta name="og:url" content="https://web.navan.dev" /> + <meta name="twitter:title" content="Hey - Home" /> + <meta name="og:title" content="Hey - Home" /> + <meta name="description" content="code snippets, long-form rants, and tutorials" /> + <meta name="twitter:description" content="code snippets, long-form rants, and tutorials" /> + <meta name="og:description" content="code snippets, long-form rants, and tutorials" /> + <meta name="twitter:card" content="summary_large_image" /> + <meta name="viewport" content="width=device-width, initial-scale=1.0" /> + <link rel="shortcut icon" href="/images/favicon.png" type="image/png" /> + <link href="/feed.rss" type="application/atom+xml" rel="alternate" title="Sitewide Atom feed" /> + <meta name="twitter:image" content="https://web.navan.dev/images/logo.png" /> + <meta name="og:image" content="https://web.navan.dev/images/logo.png" /> + <meta name="google-site-verification" content="LVeSZxz-QskhbEjHxOi7-BM5dDxTg53x2TwrjFxfL0k" /> + <script data-goatcounter="https://navanchauhan.goatcounter.com/count" + async src="//gc.zgo.at/count.js"></script> + <script defer data-domain="web.navan.dev" src="https://plausible.io/js/plausible.js"></script> + <link rel="manifest" href="/manifest.json" /> + +</head> +<body class="theme-base-0d"> + <div class="sidebar"> + <div class="container sidebar-sticky"> + <div class="sidebar-about"> + <h1><a href="/">Navan</a></h1> + <p class="lead" id="random-lead">Alea iacta est.</p> + </div> + + <ul class="sidebar-nav"> + <li><a class="sidebar-nav-item" href="/about/">about/links</a></li> + <li><a class="sidebar-nav-item" href="/posts/">posts</a></li> + <li><a class="sidebar-nav-item" href="/3D-Designs/">3D designs</a></li> + <li><a class="sidebar-nav-item" href="/feed.rss">RSS Feed</a></li> + <li><a class="sidebar-nav-item" href="/colophon/">colophon</a></li> + </ul> + <div class="copyright"><p>© 2019-2024. Navan Chauhan <br> <a href="/feed.rss">RSS</a></p></div> + </div> +</div> + +<script> +let phrases = [ + "Something Funny", "Veni, vidi, vici", "Alea iacta est", "In vino veritas", "Acta, non verba", "Castigat ridendo mores", + "Cui bono?", "Memento vivere", "अहम् ब्रह्मास्मि", "अनुगच्छतु प्रवाहं", "चरन्मार्गान्विजानाति", "coq de cheval", "我愛啤酒" + ]; + +let new_phrase = phrases[Math.floor(Math.random()*phrases.length)]; + +let lead = document.getElementById("random-lead"); +lead.innerText = new_phrase; +</script> + <div class="content container"> + + +<main> + <h1>Game Theory</h1><p>Posts tagged 'Game Theory'</p> +</main> + +<ul> + + <li><a href="/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</a></li> + <ul> + <li>Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax</li> + <li>Published On: 2024-04-17 23:20</li> + <li>Tags: + + <a href='/tags/Swift.html'>Swift</a>, + + <a href='/tags/Chess.html'>Chess</a>, + + <a href='/tags/Game Theory.html'>Game Theory</a>, + + <a href='/tags/Mathematics.html'>Mathematics</a> + + </ul> + + +</ul> + + + </div> + <script src="assets/manup.min.js"></script> + <script src="/pwabuilder-sw-register.js"></script> +</body> +</html>
\ No newline at end of file diff --git a/docs/tags/Swift.html b/docs/tags/Swift.html index 8a7f446..9aa0bfb 100644 --- a/docs/tags/Swift.html +++ b/docs/tags/Swift.html @@ -81,6 +81,23 @@ lead.innerText = new_phrase; <ul> + <li><a href="/posts/2024-04-17-implementing-minimax-for-chess-in-swift.html">Implementing Minimax with Alpha-Beta pruning for a simple Chess AI in Swift</a></li> + <ul> + <li>Adding a bestMove method to swift-chess-neo by implementing alpha-beta pruning for minimax</li> + <li>Published On: 2024-04-17 23:20</li> + <li>Tags: + + <a href='/tags/Swift.html'>Swift</a>, + + <a href='/tags/Chess.html'>Chess</a>, + + <a href='/tags/Game Theory.html'>Game Theory</a>, + + <a href='/tags/Mathematics.html'>Mathematics</a> + + </ul> + + <li><a href="/posts/2021-06-27-Crude-ML-AI-Powered-Chatbot-Swift.html">Making a Crude ML Powered Chatbot in Swift using CoreML</a></li> <ul> <li>Writing a simple Machine-Learning powered Chatbot (or, daresay virtual personal assistant ) in Swift using CoreML.</li> diff --git a/docs/tags/mathematics.html b/docs/tags/mathematics.html index a81be53..21d670e 100644 --- a/docs/tags/mathematics.html +++ b/docs/tags/mathematics.html @@ -81,17 +81,6 @@ lead.innerText = new_phrase; <ul> - <li><a href="/posts/2024-03-26-Derivation-of-the-Quadratic-Equation.html">Quadratic Formula Derivation</a></li> - <ul> - <li>Quick derivation of the quadratic equation by completing the square</li> - <li>Published On: 2024-03-26 15:36</li> - <li>Tags: - - <a href='/tags/mathematics.html'>mathematics</a> - - </ul> - - <li><a href="/posts/2023-04-30-n-body-simulation.html">n-body solution generator</a></li> <ul> <li>n-body solution generator and solver</li> |
