🏠

ai dev

beep boop

academic projects

@ Simon Fraser University

tic tac toe (CMPT 310)

the goal of this project was to construct a tic-tac-toe bot that could never lose against a smart player. the catch, however, was that this bot could not have any knowledge of the game beyond the basic rules. in order to fulfill these requirements, the bot was coded to play according to the Monte Carlo Tree Search algorithm. this algorithm takes in a game state, simulates random playouts based on that state, and chooses the next move based on the playout that resulted in the most wins.

pizza problem (CMPT 417)

the purpose of this research project was to obtain methods of improving solver performance when applied to instances of a challenging application problem. the problem i chose was the Pizza Problem, which goes something like this:

we have a list of pizzas we want to buy, each with a price. we also have a collection of “buy x, get y free” coupons, each of which can be used to get a specified number of pizzas free, provided we have paid for some other specified number of pizzas. each pizza that we get free by applying a coupon c must have a price no more than that of the cheapest paid-for pizza used to justify using coupon c.

an added constraint to this version of the problem was that i also enforced a cost limit, that is, a cap on the amount of money spent on pizzas. It is worth noting that this is an optimization problem rather than a decision problem, meaning that we are looking for the best possible answer to some input, rather than the only possible answer.