Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Simulating dynamic covariance structures for testing the adaptive behavior of variable selection algorithms (Invited Paper)

Variable selection for regression is a classical statistical problem, motivated by concerns that too large a number of covariates may bring about overfitting and unnecessarily high measurement costs. Novel difficulties arise in streaming contexts, where the correlation structure of the process may be drifting, in which case it must be constantly tracked so that selections may be revised accordingly. A particularly interesting phenomenon is that non-selected covariates become missing variables, inducing bias on subsequent decisions. This raises an intricate exploration-exploitation tradeoff, whose dependence on the covariance tracking algorithm and the choice of variable selection scheme is too complex to be dealt with analytically. We hence capitalise on the strength of simulations to explore this problem, taking the opportunity to tackle the difficult task of simulating dynamic correlation structures. © 2008 IEEE.

Collective evolution characteristics and computer simulation of short fatigue cracks

Fatigue testing was conducted using a kind of triangular isostress specimen to obtain the short-fatigue-crack behaviour of a weld low-carbon steel. The experimental results show that short cracks continuously initiate at slip bands within ferrite grain domains and the crack number per unit area gradually increases with increasing number of fatigue cycles. The dispersed short cracks possess an orientation preference, which is associated with the crystalline orientation of the relevant slip system. Based on the observed collective characteristics, computer modelling was carried out to simulate the evolution process of initiation, propagation and coalescence of short cracks. The simulation provides progressive displays which imitate the appearance of experimental observations. The results of simulation indicate that the crack path possesses a stable value of fractal dimension whereas the critical value of percolation covers a wide datum band, suggesting that the collective evolution process of short cracks is sensitive to the pattern of crack site distribution.

Lancaster and Morecambe College: Uses serious computer games as a teaching tool

John Latham, International Projects Co-ordinator at Lancaster and Morecambe College (LMC), got involved with the project Serious Computer Games as a Teaching Tool (SCOGATT) after using the game EnerCities with his students. The web based platform at www.scogatt.eu serves as a One Stop Toolkit for vocational teachers and trainers who want to use serious computer games (SCG) in their teaching environments but might need a helping hand. There they will be able to find a compendium of serious games, SCOGATT pilot results, teacher reports and the exemplar games, EnerCities.

The Computer Input/Output Subsystem Education in an undergraduate introductory course: a Multiperspective Study

240 p.

A Test of Computer-assisted Matching Using the North Pacific Humpback Whale, Megaptera novaeangliae, Tail Flukes Photograph Collection

Testing was conducted of a computer-assisted system for matching humpback whale tail flukes photographs. Trials with a 12,000-photographs database found no differences in match success between matching by computer and matching by comparing smaller catalogs ranging in size from 200 to 400 photographs. Tests with a 24,000-photographs database showed that, on average, the first match was found after examining about 130 photographs whether the photograph quality was excellent, good, or poor. Match success did not appear to be strongly related to whether the tail flukes had especially distinctive markings or pigment patterns (recognition quality). An advantage of computer-assisted matching is the ability to compare new photographs to the entire North Pacific collection, where no bias is introduced based on expectation of resightings within or between specific areas, or based on expectation of behavioral role (e.g. matching “known” females to “known” females).

Articulated wooden blades for a horizontal-axis wind turbine. Design, construction and testing.

A pair of blades were constructed following a Tapered Chord, Zero Twist pattern after Anderson. The construction uses the Wood Epoxy Saturation Technique, with a solid Beech main spar and leading edge joined together with laminated veneers of beech forming a D-section; the trailing edge is formed from millimetre ply skins, foam filled to resist compressive loads. This construction leads to an extremely light, flexible blade, with the centres of gravity and torsion well forward, giving good stability. Each blade has three built-in strain gauges, alowing flapwise bending to be measured. Stiffness, and natural frequencies, were measured, to input to a numerical computer model to calculate blade deformation during operation, and to determine stability boundaries of the blade. Preliminary aerodynamic performance measurements are presented and close agreement is found with theory.

A reason for unreason: returns-based beliefs in game theory

Players cooperate in experiments more than game theory would predict. We introduce the ‘returns-based beliefs’ approach: the expected returns of a particular strategy in proportion to total expected returns of all strategies. Using a decision analytic solution concept, Luce’s (1959) probabilistic choice model, and ‘hyperpriors’ for ambiguity in players’ cooperability, our approach explains empirical observations in various classes of games including the Prisoner’s and Traveler’s Dilemmas. Testing the closeness of fit of our model on Selten and Chmura (2008) data for completely mixed 2 × 2 games shows that with loss aversion, returns-based beliefs explain the data better than other equilibrium concepts.

basic research in computer science and software engineering at sklcs

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.

Computer Perception of Three-Dimensional Objects

We first pose the following problem: to develop a program which takes line-drawings as input and constructs three-dimensional objects as output, such that the output objects are the same as the ones we see when we look at the input line-drawing. We then introduce the principle of minimum standard-deviation of angles (MSDA) and discuss a program based on MSDA. We present the results of testing this program with a variety of line- drawings and show that the program constitutes a solution to the stated problem over the range of line-drawings tested. Finally, we relate this work to its historical antecedents in the psychological and computer-vision literature.

The Computer as Coach: An Athletic Paradigm for Intellectual Education

Over the next five years, computer games will find their way into a vast number of American homes, creating a unique educational opportunity: the development of "computer coaches" for the serious intellectual skills required by some of these games. From the player's perspective, the coach will provide advice regarding strategy and tactics for better play. But, from the perspective of the coach, the request for help is an opportunity to tutor basic mathematical, scientific or other kinds of knowledge that the game exercises.

SIR: A Computer Program for Semantic Information Retrieval

SIR is a computer system, programmed in the LISP language, which accepts information and answers questions expressed in a restricted form of English. This system demonstrates what can reasonably be called an ability to "understand" semantic information. SIR's semantic and deductive ability is based on the construction of an internal model, which uses word associations and property lists, for the relational information normally conveyed in conversational statements. A format-matching procedure extracts semantic content from English sentences. If an input sentence is declarative, the system adds appropriate information to the model. If an input sentence is a question, the system searches the model until it either finds the answer or determines why it cannot find the answer. In all cases SIR reports its conclusions. The system has some capacity to recognize exceptions to general rules, resolve certain semantic ambiguities, and modify its model structure in order to save computer memory space. Judging from its conversational ability, SIR, is a first step toward intelligent man-machine communication. The author proposes a next step by describing how to construct a more general system which is less complex and yet more powerful than SIR. This proposed system contains a generalized version of the SIR model, a formal logical system called SIR1, and a computer program for testing the truth of SIR1 statements with respect to the generalized model by using partial proof procedures in the predicate calculus. The thesis also describes the formal properties of SIR1 and how they relate to the logical structure of SIR.

Agency and animation: the performance of interactive game characters

As an animator and practice-based researcher with a background in games development, I am interested in technological change in the video game medium, with a focus on the tools and technologies that drive game character animation and interactive story. In particular, I am concerned with the issue of ‘user agency’, or the ability of the end user to affect story development—a key quality of the gaming experience and essential to the aesthetics of gaming, which is defined in large measure by its interactive elements. In this paper I consider the unique qualities of the video game1 as an artistic medium and the impact that these qualities have on the production of animated virtual character performances. I discuss the somewhat oppositional nature of animated character performances found in games from recent years, which range from inactive to active—in other words, low to high agency. Where procedural techniques (based on coded rules of movement) are used to model dynamic character performances, the user has the ability to interactively affect characters in real-time within the larger sphere of the game. This game play creates a high degree of user agency. However, it lacks the aesthetic nuances of the more crafted sections of games: the short cut-scenes, or narrative interludes where entire acted performances are mapped onto game characters (often via performance capture)2 and constructed into relatively cinematic representations. While visually spectacular, cut-scenes involve minimal interactivity, so user agency is low. Contemporary games typically float between these two distinct methods of animation, from a focus on user agency and dynamically responsive animation to a focus on animated character performance in sections where the user is a passive participant. We tend to think of the majority of action in games as taking place via playable figures: an avatar or central character that represents a player. However, there is another realm of characters that also partake in actions ranging from significant to incidental: non-playable characters, or NPCs, which populate action sequences where game play takes place as well as cut scenes that unfold without much or any interaction on the part of the player. NPCs are the equivalent to supporting roles, bit characters, or extras in the world of cinema. Minor NPCs may simply be background characters or enemies to defeat, but many NPCs are crucial to the overall game story. It is my argument that, thus far, no game has successfully utilized the full potential of these characters to contribute toward development of interactive, high performance action. In particular, a type of NPC that I have identified as ‘pivotal’3—those constituting the supporting cast of a video game—are essential to the telling of a game story, particularly in genres that focus on story and characters: adventure games, action games, and role-playing games. A game story can be defined as the entirety of the narrative, told through non-interactive cut-scenes as well a interactive sections of play, and development of more complex stories in games clearly impacts the animation of NPCs. I argue that NPCs in games must be capable of acting with emotion throughout a game—in the cutscenes, which are tightly controlled, but also in sections of game play, where player agency can potentially alter the story in real-time. When the animated performance of NPCs and user agency are not continuous throughout the game, the implication is that game stories may be primarily told through short movies within games, making it more difficult to define video games animation as a distinct artistic medium.

Project Sanitarium: gaming TB: a serious game for a serious problem

Collaborative projects between Industry and Academia provide excellent opportunities for learning. Throughout the academic year 2014-2015 undergraduates from the School of Arts, Media and Computer Games at Abertay University worked with academics from the Infection Group at the University of St Andrews and industry partners Microsoft and DeltaDNA. The result was a serious game prototype that utilized game design techniques and technology to demystify and educate players about the diagnosis and treatment of one of the world's oldest and deadliest diseases, Tuberculosis (TB). Project Sanitarium is a game incorporating a mathematical model that is based on data from real-world drug trials. This paper discusses the project design and development, demonstrating how the project builds on the successful collaborative pedagogical model developed by academic staff at Abertay University. The aim of the model is to provide undergraduates with workplace simulation, wider industry collaboration and access to academic expertise to solve challenging and complex problems.

The game jam movement: disruption, performance and artwork

This paper explores the current conventions and intentions of the game jam - contemporary events that encourage the rapid, collaborative creation of game design prototypes. Game jams are often renowned for their capacity to encourage creativity and the development of alternative, innovative game designs. However, there is a growing necessity for game jams to continue to challenge traditional development practices through evolving new formats and perspectives to maintain the game jam as a disruptive, refreshing aspect of game development culture. As in other creative jam style events, a game jam is not only a process but also, an outcome. Through a discussion of the literature this paper establishes a theoretical basis with which to analyse game jams as disruptive, performative processes that result in original creative artefacts. In support of this, case study analysis of Development Cultures: a series of workshops that centred on innovation and new forms of practice through play, chance, and experimentation, is presented. The findings indicate that game jams can be considered as processes that inspire creativity within a community and that the resulting performances can be considered as a form of creative artefact, thus parallels can be drawn between game jams and performative and interactive art.