Alphabear Solver

Author: Ryan E. Dougherty (ryan.dougherty@westpoint.edu)

Image credit: https://patricktay.files.wordpress.com/2015/09/alphabear1.jpg

Description:

The Alphabear game contains a grid of both visible and invisible (to the player) letters; the visible ones contain an integer timer that decreases by 1 each round, and invisible ones become visible with a timer when an orthogonally adjacent letter is used. In each turn, the player chooses some visible letters to make a valid English word. If any letter's timer becomes 0, then it can never be picked (and the player earns fewer points at the end). This assignment is about finding the "best" single choice of word to pick for a given board by assigning an "importance" to each letter based on its timer (and correspondingly the whole word). The score for a word is the sum of the importances for each of its letters multiplied by a factor that increases with longer words, because Alphabear heavily prefers longer words. Note the chosen scoring function was just to make a reasonable approximation of what Alphabear does based on gameplay, not necessarily what its actual scoring function, which is much more complicated. Students are provided a text file of all English words.

The specific tasks required of the students in the assignment were:

Reading in a text file of all English words and storing them in a data structure
Reading user inputs for letters and storing in an ordered data structure (C++ vectors here)
Writing a function to calculate the "importance" of a letter
Reading parallel arrays/vectors
Finding the maximum of a collection

The assignment was created for a C++ course, but is not limited to that language. The views expressed in this article are those of the author and do not reflect the official policy or position of the Department of the Army, Department of Defense, or the U.S. Government.

Metadata

Summary	This assignment asks students to create a program which determines what English word to choose with the given board letters and timers so that the score is maximized.
Audience	The primary audience involves CS1 students, and is not restricted to any particular programming language; the assignment here originally was given in a C++ course (but this is not a requirement).
Difficulty	The expected difficulty is several hours, and CS1 students should be able to complete it within 2 or 3 weeks. Students found it to be moderately difficult.
Topics	The assignment focuses on arrays, file I/O, searching across parallel arrays, and creating functions. This implies that students should also know and be comfortable with some form of iteration and conditionals.
Strengths	There is an ability for studnets to see applications of game solvers. The assignment has a large coverage of CS1 topics, and thus is useful for reinforcing course concepts. Related to the last point, but this assignment is a sufficiently complex project that involves critically thinking about how to layout their code. Additionally, it is very "modular" in that one can complete parts independently of others simply by putting "dummy" data (say for the text file of English words). Students have an ability to have hands-on experience with the game.
Weaknesses	There are many moving parts, which may be prohibitive for lower-performing students about where to start.
Dependencies	Students need to know how to manipulate some kind of ordered collections (like arrays), and read files. No particular programming language is required, although ours was in C++. A list of English words stored as a text file is required (but can be applied to any other spoken language).
Variants	One possibility is to involve students testing different algorithms to guess "good" words across multiple turns instead of just one: are greedy methods best? Another variant concerns what scoring functions give better outcomes over the course of several games.
Teaching Notes	It would be helpful for instructors to go over the assignment directions in class, as there are many moving parts. Additionally, we would recommend adding a specific format to the output so that autograding the assignment is possible. This might be difficult since the scoring function deals with floating-point numbers, so we advocate always rounding the result to avoid this issue.

Assignment Files

Assignment Directions
Assignment Solutions
words.txt (all English words)