Convex optimization has been active in my GitHub long before the existence of this repository. From smart farmers in quant trading, portfolio optimization in graph theory, multiple choice knapsack problem in dynamic programming to support vector machine in machine learning, I am always fascinated by the elegance of Lagrangian functions. As optimization problems accumulate in other repositories, it came to my mind that optimization problems deserve their own Guoco Tower as opposed to couch surfing in Tanjong Pagar. Since the more I learn, the more I realize how much I don’t know. Convex optimization is merely a little fish in a big pond. The big pond, operations research, covers other cools topics such as decision analysis, game theory, inventory theory, metaheuristics and queuing theory. Hence, the birth of this repository marks the beginning of my journey to the uncharted water. And I hope it motivates you to explore the unknown territory in mathematics as well.
- Binary Integer Linear Programming
- Minimax/Negamax
- Depth Limited Search
Sudoku is a logic-based, combinatorial number-placement puzzle. Despite its Japanese name, the game was actually invented by an American and later gained popularity in Japan. There are many ways (e.g. vertex coloring) for computer algorithms to solve Sudoku. Here we use Binary Integer Linear Programming to solve the puzzle via convex optimization. In this particular optimization problem, we have no objective function to maximize or minimize. We merely need to satisfy the constraints below.
- Only one element in each column
- Only one element in each row
- Only one element in each sub matrix
- Each cell in the matrix should be filled
- Given elements in the cells are set on
Click here to be redirected to the script.
Tic-Tac-Toe is a very simple game for children. In a conventional setting, two players play on a three by three grid. Whoever manages to have three marks on a column, row or diagonal wins the game. The objective here is to create a gaming AI which is sophisticated enough to beat the human player. Minimax algorithm is perfect for the job. Minimax, inspired by DFS in graph theory, is a recursive traversal algorithm on game tree to minimize the maximum game loss. The brute force computation of every possible game scenario is computationally expensive. Other techniques including alpha-beta pruning, depth limited search, iterative deepening search, memoization, Monte Carlo evaluation function can improve the time complexity.
Click here to be redirected to the script.