diff options
| -rw-r--r-- | csci4511w/writing3.bib | 29 | ||||
| -rw-r--r-- | csci4511w/writing3.tex | 44 |
2 files changed, 73 insertions, 0 deletions
diff --git a/csci4511w/writing3.bib b/csci4511w/writing3.bib new file mode 100644 index 0000000..bea7fcd --- /dev/null +++ b/csci4511w/writing3.bib @@ -0,0 +1,29 @@ +@inproceedings{10.5555/2900728.2900788, + author = {Barker, Joseph K. and Korf, Richard E.}, + title = {Solving Dots-and-Boxes}, + year = {2012}, + publisher = {AAAI Press}, + abstract = {Dots-And-Boxes is a well-known and widely-played combinatorial game. While the rules of play are very simple, the state space for even very small games is extremely large, and finding the outcome under optimal play is correspondingly hard. In this paper we introduce a Dots-And-Boxes solver which is significantly faster than the current state-of-the-art: over an order-of-magnitude faster on several large problems. Our approach uses Alpha-Beta search and applies a number of techniques--both problem-specific and general--that reduce the search space to a manageable size. Using these techniques, we have determined for the first time that Dots-And-Boxes on a board of 4 \texttimes{} 5 boxes is a tie given optimal play; this is the largest game solved to date.}, + booktitle = {Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence}, + pages = {414–419}, + numpages = {6}, + location = {Toronto, Ontario, Canada}, + series = {AAAI'12} +} +@inproceedings{7317912, + author = {Y. {Zhuang} and S. {Li} and T. V. {Peters} and C. {Zhang}}, + booktitle = {2015 IEEE Conference on Computational Intelligence and Games (CIG)}, + title = {Improving Monte-Carlo tree search for dots-and-boxes with a novel board representation and artificial neural networks}, + year = {2015}, + volume = {}, + number = {}, + pages = {314-321}, + doi = {10.1109/CIG.2015.7317912} +} +@misc{article, + author = {Simon, Eliott and Giepmans, Cas}, + year = {2020}, + location = {Maastricht University, Maastricht, Netherlands}, + pages = {}, + title = {INTELLIGENT AGENTS FOR SOLVING THE GAME DOTS AND BOXES} +}
\ No newline at end of file diff --git a/csci4511w/writing3.tex b/csci4511w/writing3.tex new file mode 100644 index 0000000..214df16 --- /dev/null +++ b/csci4511w/writing3.tex @@ -0,0 +1,44 @@ +\documentclass{article} +\usepackage[utf8]{inputenc} +\usepackage{indentfirst} + +\title{Writing 3} +\author{Jack Vehmeier, Andrea Smith, Matt Strapp} +\date{2021-03-16} +\begin{document} + \maketitle + \section*{Project Proposal} +La Pipopipette, or Dots \& Boxes, is a simple paper and pen game designed by Édouard Lucas in the nineteenth century. +The game is similar to tic tac toe in that it is quick, easy to learn, and popular amongst children or bored people with access to paper and writing utensils. +We are all familiar with this game from our own childhoods and were curious if we could design an AI opponent that can compete and potentially outperform humans. + + +We hope the AI will be unbeatable or at least a reasonable challenge for a human player. +We approach the problem by first building a program which allows the game to be played. +After this we will implement Minimax with Alpha-Beta pruning as the main algorithm used to navigate the game tree the AI will see. +The tree will see what will have the highest possibility of victory and take it, because most games usually end with one side having significantly more points than the other if play is not perfect. +This should allow the AI to simulate many different possible moves it could make and then it will pick the best move based on criteria that is yet to be determined. +We need to make sure that the AI understands the rules and is able to discern the best approach to win. +We plan to implement our program in Python, and have no preliminary results at the moment of writing. +If possible, we would also like to make our implementation open source and post it on GitHub. + + +Our solution will be validated by first making sure it follows all rules of the game and when successful comparing our implementation to other possible implementations with different search algorithms and ranks them based on win percentage. +Possible other implementations include using a Minimax Search, Monte Carlo Tree Search, and a random search that only looks for empty spaces. +We can compare all of these search methods and have them play dots and boxes against each other as well as humans. + + + +Given that we currently have approximately seven weeks to complete this project, our tentative timeline will span all of them. +Within the first three to four weeks, the game should be playable such that the board renders properly, and a random-search based AI is implemented that can play against a human opponent. +By weeks four through six, we plan to accomplish the bulk of the work (implementing the “best” AI, as well as the other variations previously mentioned). +In the final two weeks a GUI will be added and experiments run with various matchups (AI against AI, AI against human, human against human). +The main data collected will be comparing the different implementations against each other to see which one is the best by the highest ratio of victories to defeats. +In the final weeks, we will write the final report and finish the analysis of our experimental data. +We plan on using all of the weeks available as a failsafe for something than takes longer than expected and to balance our workload with other classes. + + \medskip + \nocite{*} + \bibliographystyle{unsrt} + \bibliography{writing3} +\end{document} |