Total: 19
Birds of a Feather is a single-player card game in which cards are arranged in a grid. The player attempts to combine stacks of cards under certain rules, with the goal being to combine all cards into a single stack. This paper highlights several approaches for efficiently classifying whether a randomlychosen state has a single-stack solution. These approaches use graph theory and machine learning concepts to prune a state’s search space, resulting in significant reductions in runtime relative to a baseline search.
As research and development (R&D) in autonomous systems progresses further, more interdisciplinary knowledge is needed from domains as diverse as artificial intelligence (AI), bi-ology, psychology, modeling and simulation (M&S), and robotics. Such R&D efforts are necessarily interdisciplinary in nature and require technical as well as further soft skills of teamwork, communication and integration. In this paper, we introduce a 14 week, summer long internship for developing these skills in undergraduate science and engineering interns through R&D. The internship was designed to be modular and divided into three parts: training, innovation, and application/integration. The end result of the internship was 1) the development of an M&S ecosystem for autonomy concepts, 2) development and robotics testing of reasoning methods through both Bayesian methods and cognitive models of the basal ganglia, and 3) a process for future internships within the modular construct. Through collaboration with full-time professional staff, who actively learned with the interns, this internship incorporates a feedback loop to educate and per-form fundamental R&D. Future iterations of this internship can leverage the M&S ecosystem and adapt the modular internship framework to focus on different innovations, learning paradigms, and/or applications.
After years of taking a trial-and-error approach to managing a moderate-size academic research group, I settled on using a set of online tools and protocols that seem effective, require relatively little effort to use and maintain, and are inexpensive. This paper discusses this approach to communication, project management, document and code management, and logistics. It is my hope that other researchers, especially new faculty and research scientists, might find this set of tools and protocols useful when determining how to manage their own research group. This paper is targeted toward research groups based in mathematics and engineering, although faculty in other disciplines may find inspiration in some of these ideas.
In this paper, we analyze Birds of a Feather (BoaF), a perfectinformation one-player card game that is the subject of the 2019 EAAI Undergraduate Research Challenge. We prove that the generalized N × N BoaF game is NP-complete, and then explore the one million deals in the 4×4 BoaF testbed. We present several graph-theoretic algorithms to prove that 1880 of these million deals are unsolvable, and conclude the paper with two search algorithms that efficiently show that all of the remaining 998,120 deals are in fact solvable.
This research was conducted by an interdisciplinary team of two undergraduate students and a faculty to explore solutions to the Birds of a Feather (BoF) Research Challenge. BoF is a newly-designed perfect-information solitaire-type game. The focus of the study was to design and implement different algorithms and evaluate their effectiveness. The team compared the provided depth-first search (DFS) to heuristic algorithms such as Monte Carlo tree search (MCTS), as well as a novel heuristic search algorithm guided by machine learning. Since all of the studied algorithms converge to a solution from a solvable deal, effectiveness of each approach was measured by how quickly a solution was reached, and how many nodes were traversed until a solution was reached. The employed methods have a potential to provide artificial intelligence enthusiasts with a better understanding of BoF and novel ways to solve perfect-information games and puzzles in general. The results indicate that the proposed heuristic search algorithms guided by machine learning provide a significant improvement in terms of number of nodes traversed over the provided DFS algorithm.
In the era of MOOCs, online exams are taken by millions of candidates, where scoring short answers is an integral part. It becomes intractable to evaluate them by human graders. Thus, a generic automated system capable of grading these responses should be designed and deployed. In this paper, we present a fast, scalable, and accurate approach towards automated Short Answer Scoring (SAS). We propose and explain the design and development of a system for SAS, namely AutoSAS. Given a question along with its graded samples, AutoSAS can learn to grade that prompt successfully. This paper further lays down the features such as lexical diversity, Word2Vec, prompt, and content overlap that plays a pivotal role in building our proposed model. We also present a methodology for indicating the factors responsible for scoring an answer. The trained model is evaluated on an extensively used public dataset, namely Automated Student Assessment Prize Short Answer Scoring (ASAP-SAS). AutoSAS shows state-of-the-art performance and achieves better results by over 8% in some of the question prompts as measured by Quadratic Weighted Kappa (QWK), showing performance comparable to humans.
Modern introductory courses on AI do not train students to create intelligent systems or provide broad coverage of this complex field. In this paper, we identify problems with common approaches to teaching artificial intelligence and suggest alternative principles that courses should adopt instead. We illustrate these principles in a proposed course that teaches students not only about component methods, such as pattern matching and decision making, but also about their combination into higher-level abilities for reasoning, sequential control, plan generation, and integrated intelligent agents. We also present a curriculum that instantiates this organization, including sample programming exercises and a project that requires system integration. Participants also gain experience building knowledge-based agents that use their software to produce intelligent behavior.
Prerequisite relations among concepts are crucial for educational applications. However, it is difficult to automatically extract domain-specific concepts and learn the prerequisite relations among them without labeled data. In this paper, we first extract high-quality phrases from a set of educational data, and identify the domain-specific concepts by a graph based ranking method. Then, we propose an iterative prerequisite relation learning framework, called iPRL, which combines a learning based model and recovery based model to leverage both concept pair features and dependencies among learning materials. In experiments, we evaluated our approach on two real-world datasets Textbook Dataset and MOOC Dataset, and validated that our approach can achieve better performance than existing methods. Finally, we also illustrate some examples of our approach.
In this article, we describe the lessons learned in creating an efficient solver for the solitaire game Birds of a Feather. We introduce a new variant of depth-first search that we call best-n depth-first search that achieved a 99.56% reduction in search time over 100,000 puzzle seeds. We evaluate a number of potential node-ordering search features and pruning tests, perform an analysis of solvability prediction with such search features, and consider possible future research directions suggested by the most computationally expensive puzzle seeds encountered in our testing.
In this article, we describe a computer-aided design process for generating high-quality Birds of a Feather solitaire card puzzles. In each iteration, we generate puzzles via combinatorial optimization of an objective function. After solving and subjectively rating such puzzles, we compute objective puzzle features and regress our ratings onto such features to provide insight for objective function improvements. Through this iterative improvement process, we demonstrate the importance of the halfway solvability ratio in quality puzzle design. We relate our observations to recent work on tension in puzzle design, and suggest next steps for more efficient puzzle generation.
Artificial intelligence in games serves as an excellent platform for facilitating collaborative research with undergraduates. This paper explores several aspects of a research challenge proposed for a newly-developed variant of a solitaire game. We present multiple classes of game states that can be identified as solvable or unsolvable. We present a heuristic for quickly finding goal states in a game state search tree. Finally, we introduce a Monte Carlo Tree Search-based player for the solitaire variant that can win almost any solvable starting deal efficiently.
Birds of a Feather is a single player, perfect information card game. The game can have multiple board sizes with larger boards introducing larger search spaces that grow exponentially. In this paper, we investigate the solvability of the game, aiming at building a machine learning method to automatically classify whether a given board state has a solution path or not. We propose a method based on image-based features of the board state and deep neural network. Experimental results show that the proposed method can make reasonable predictions of the solvability of a game at an arbitrary stage of the game.
Images are an essential tool for communicating with children, particularly at younger ages when they are still developing their emergent literacy skills. Hence, assessments that use images to assess their conceptual knowledge and visual literacy, are an important component of their learning process. Creating assessments at scale is a challenging task, which has led to several techniques being proposed for automatic generation of textual assessments. However, none of them focuses on generating image-based assessments. To understand the manual process of creating visual assessments, we interviewed primary school teachers. Based on the findings from the preliminary study, we present a novel approach which uses image semantics to generate visual multiple choice questions (VMCQs) for young learners, wherein options are presented in the form of images. We propose a metric to measure the semantic similarity between two images, which we use to identify the four options – one answer and three distractor images – for a given question. We also use this metric for generating VMCQs at two difficulty levels – easy and hard. Through a quantitative evaluation, we show that the system-generated VMCQs are comparable to VMCQs created by experts, hence establishing the effectiveness of our approach.
Our work builds on advances in deep learning for natural language processing to automatically analyze transcribed classroom discourse and reliably generate information about teachers’ uses of specific discursive strategies called ”talk moves.” Talk moves can be used by both teachers and learners to construct conversations in which students share their thinking, actively consider the ideas of others, and engage in sustained reasoning. Currently, providing teachers with detailed feedback about the talk moves in their lessons requires highly trained observers to hand code transcripts of classroom recordings and analyze talk moves and/or one-on-one expert coaching, a time-consuming and expensive process that is unlikely to scale. We created a bidirectional long short-term memory (bi-LSTM) network that can automate the annotation process. We have demonstrated the feasibility of this deep learning approach to reliably identify a set of teacher talk moves at the sentence level with an F1 measure of 65%.
PopBots is a hands-on toolkit and curriculum designed to help young children learn about artificial intelligence (AI) by building, programming, training, and interacting with a social robot. Today’s children encounter AI in the forms of smart toys and computationally curated educational and entertainment content. However, children have not yet been empowered to understand or create with this technology. Existing computational thinking platforms have made ideas like sequencing and conditionals accessible to young learners. Going beyond this, we seek to make AI concepts accessible. We designed PopBots to address the specific learning needs of children ages four to seven by adapting constructionist ideas into an AI curriculum. This paper describes how we designed the curriculum and evaluated its effectiveness with 80 Pre-K and Kindergarten children. We found that the use of a social robot as a learning companion and programmable artifact was effective in helping young children grasp AI concepts. We also identified teaching approaches that had the greatest impact on student’s learning. Based on these, we make recommendations for future modules and iterations for the PopBots platform.
This paper presents a framework to integrate Science and Computing teaching using Logic Programming. We developed two modules: one for chemistry and the other for chemistry and physics. They are implemented in an elective course for 8th graders. Through clinical interviews, video taped class observations, exit interviews and our own experiences with the class, Logic Programming based approach is accessible to the students.
In August 2017, the ACM Education Council initiated a task force to add to the broad, interdisciplinary conversation on data science, with an articulation of the role of computing discipline-specific contributions to this emerging field. Specifically, the task force is seeking to define what the computing contributions are to this new field, in order to provide guidance for computer science or similar departments offering data science programs of study at the undergraduate level. The ACM Data Science Task Force has completed the initial draft of a curricular report. The computing-knowledge areas identified in the report are drawn from across computing disciplines and include several sub-areas of AI. This short paper describes the overall project, highlights AI-relevant areas, and seeks to open a dialog about the AI competencies that are to be considered central to a data science undergraduate curriculum.
In this paper, we analyze Birds of a Feather (BoaF), a solitaire game played with 16 cards. While the large majority of deals are solvable, the set of unsolvable deals share certain characteristics that can be determined from the adjacency matrix of the corresponding “compatibility graph”. We create a binary decision tree based on just three variables to predict whether a given deal is solvable. Our predictive model, tested on 30,000 random deals, correctly classifies over 99.9% of our data.
The Model AI Assignments session seeks to gather and disseminate the best assignment designs of the Artificial Intelligence (AI) Education community. Recognizing that assignments form the core of student learning experience, we here present abstracts of ten AI assignments from the 2019 session that are easily adoptable, playfully engaging, and flexible for a variety of instructor needs. Assignment specifications and supporting resources may be found at http: //modelai.gettysburg.edu.