Packing Problem: 2D and 3D Packing 📦

September 2021 - January 2022

Packing problems are critical in operations research. Companies can significantly reduce costs by using packing strategies generated by our algorithms as starting points.

We developed 2D packing algorithms in the form of Pentris. Initially, we used brute-force methods but later advanced to genetic algorithms where fitness was determined by both the pentomino to pack and the existing shape of the arrangement.

We implemented genetic algorithms, greedy algorithms, and dancing links to efficiently pack 3D containers. The GUI for this project was built using JavaFX.

Developed algorithms from scratch to efficiently pack 2D and 3D packages into containers. Initially built a Tetris-style solver, which was later expanded to include more complex 3D packing solutions. This project served as an excellent exploration of greedy and genetic algorithms, as well as Donald Knuth’s "Dancing Links," which can also be used for solving problems like the exact cover problem and Sudoku. The GUI was implemented in both Swing and JavaFX.

Technologies Utilized:

Java

JavaFX

Project Demonstrations

Dice Chess 🎲

September 2022 - June 2023

Dice Chess is a variant of traditional chess that incorporates a six-sided die, introducing an element of randomness to the game.

Due to the stochastic nature of Dice Chess, the search tree depth cannot be fully anticipated beyond the immediate move, unlike in traditional chess.

We leveraged a MySQL database containing encoded game states (FEN) to train a neural network that predicts win probabilities for specific game positions.

In this project, I developed a learning agent for Dice Chess, where the introduction of a die determines available moves and introduces an element of unpredictability. The self-play data from the best agent was stored in a MySQL database using JDBC. While grandmaster-level games are ideal for training, they were difficult to find for this variant of chess.

The neural network was employed in two distinct contexts: as a Q-function approximation in a Q-learning agent to evaluate which moves offer the highest win probability, and as a value network in Monte Carlo Tree Search (MCTS) to compute the expected cumulative score for a given game state.

Technologies Utilized:

Java

MySQL

Gradle

Deep4J

Project Demonstrations

3D Golf Simulator ⛳️

Feb 2022 - Jun 2022

In this game, we developed agents that allowed 'putting' the golf ball into a hole, on a diverse terrain, including trees, hills, and potential walls.

We developed a physics engine from scratch, based on Euler and Runge Kutta, with RK4 showing the best performance.

Different optimization algorithms were implemented to find the best 'parameters' like force and angle to hit the ball. These included PSO and Simulated Annealing.

In this project, I developed the physics engine from scratch, initially relying on Euler's method but later advancing to Runge-Kutta 4 (RK4). The "putting" algorithms implemented were Simulated Annealing (SA) and Particle Swarm Optimization (PSO). The GUI was programmed in LibGDX, where the terrain was generated using a height function \( f(x, y) \), and additional objects like sandpits, trees, and walls were added to increase difficulty for the agents.

Technologies Utilized:

Java

Gradle

LibGDX

Project Demonstrations