Computer vs. Human: Exploring AI in the Game Blokus

Overview

Objectives/Goals AI researchers have always been interested in abstract strategy games because they involve complex human thought process and a clean environment with clear criteria for success. My objective is to explore AI in a new strategy game Blokus. I hypothesize that, by using my newly created and optimized strategies based on last year's research, my Blokus AI program could defeat human players, represented in my project by doctors and professors. Methods/Materials (1) With my own C# program, I simulated and analyzed a total of 5 million Blokus games in 500 strategy tests (with 100 trials in each test) in Experiments 1, 2, 3, and 4. I created 4 new versions of increasingly effective strategies by developing a new Form (F) Strategy, enhancing the Piece (P) and Location (L) strategies, and adding a deep search algorithm. I tested 30 parameter values for P, L, and F, and investigated hundreds of different combinations in order to achieve the best winning chance. (2) In Experiment 5, Computer vs. Human, I developed new functions to allow my best strategy to play against 5 PhDs and 4 professors in a total of 72 games for human-level AI testing. (3) In a Side Experiment, I had my program play against both commercial Blokus AI products I was able to find. Results (1) This year's best strategy achieved a 99.8% winning chance against random and an 89.5% against P/L, last year's best strategy. The optimal parameter values were determined as P12, L9, and F0.8587 by using polynomial regression analyses and calculus techniques of finding the extrema. (2) In Exp. 5, my AI program defeated all 9 human players. (3) In the Side Exp., my program won against both commercial Blokus AI products. Conclusions/Discussion (1) The results support my hypothesis that my Blokus AI could defeat human players, represented here by doctors and professors. (2) I created my AI program by not only copying the way the human brain thinks, but also taking advantage of the computer's calculation power in order to handle the search tree's large branching factors and to run 5 million games for parameter optimization. (3) My project is very significant because it shows AI's great potential to win humans in Blokus and provides a good test-bed for studying Blokus and other similar games. More importantly, with a newly studied game Blokus, my project contributes to the challenging field of game-related AI research.

Awards (1)

• First Place

Competition history

• CSEF 2012 Mathematics & Software · Entry J1415

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2012 project
• CSEF First Place winners