ken

From the beginning, the world of game-playing by machine has been fortunate in attracting contributions from the leading names of computer science. Charles Babbage, Konrad Zuse, Claude Shannon, Alan Turing, John von Neumann, John McCarthy, Alan Newell, Herb Simon and Ken Thompson all come to mind, and each reader will wish to add to this list. Recently, the Journal has saluted both Claude Shannon and Herb Simon. Ken’s retirement from Lucent Technologies’ Bell Labs to the start-up Entrisphere is also a good moment for reflection.

Ken Thompson's 6-man Tables

Ken Thompson recently communicated some results mined from his set of 64 6-man endgame tables. These list some positions of interest, namely, mutual zugzwangs and those of maximum depth. The results have been analysed by the authors and found to be identical or compatible with the available or published findings of Karrer, Nalimov, Stiller and Wirth.

Ken Thompson's 6-man Statistical Graphs

This note reviews Ken Thompson's statistics on 6-man White wins with Black to move and explains the way in which the statistics have been graphed logarithmically.

An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters

Bloom filters are a data structure for storing data in a compressed form. They offer excellent space and time efficiency at the cost of some loss of accuracy (so-called lossy compression). This work presents a yes-no Bloom filter, which as a data structure consisting of two parts: the yes-filter which is a standard Bloom filter and the no-filter which is another Bloom filter whose purpose is to represent those objects that were recognised incorrectly by the yes-filter (that is, to recognise the false positives of the yes-filter). By querying the no-filter after an object has been recognised by the yes-filter, we get a chance of rejecting it, which improves the accuracy of data recognition in comparison with the standard Bloom filter of the same total length. A further increase in accuracy is possible if one chooses objects to include in the no-filter so that the no-filter recognises as many as possible false positives but no true positives, thus producing the most accurate yes-no Bloom filter among all yes-no Bloom filters. This paper studies how optimization techniques can be used to maximize the number of false positives recognised by the no-filter, with the constraint being that it should recognise no true positives. To achieve this aim, an Integer Linear Program (ILP) is proposed for the optimal selection of false positives. In practice the problem size is normally large leading to intractable optimal solution. Considering the similarity of the ILP with the Multidimensional Knapsack Problem, an Approximate Dynamic Programming (ADP) model is developed making use of a reduced ILP for the value function approximation. Numerical results show the ADP model works best comparing with a number of heuristics as well as the CPLEX built-in solver (B&B), and this is what can be recommended for use in yes-no Bloom filters. In a wider context of the study of lossy compression algorithms, our researchis an example showing how the arsenal of optimization methods can be applied to improving the accuracy of compressed data.

Modelling the growth and movement of cyanobacteria in river systems

Bloom-forming and toxin-producing cyanobacteria remain a persistent nuisance across the world. Modelling of cyanobacteria in freshwaters is an important tool for understanding their population dynamics and predicting the location and timing of the bloom events in lakes and rivers. In this article, a new deterministic model is introduced which simulates the growth and movement of cyanobacterial blooms in river systems. The model focuses on the mathematical description of the bloom formation, vertical migration and lateral transport of colonies within river environments by taking into account the four major factors that affect the cyanobacterial bloom formation in freshwaters: light, nutrients, temperature and river flow. The model consists of two sub-models: a vertical migration model with respect to growth of cyanobacteria in relation to light, nutrients and temperature; and a hydraulic model to simulate the horizontal movement of the bloom. This article presents the model algorithms and highlights some important model results. The effects of nutrient limitation, varying illumination and river flow characteristics on cyanobacterial movement are simulated. The results indicate that under high light intensities and in nutrient-rich waters colonies sink further as a result of carbohydrate accumulation in the cells. In turbulent environments, vertical migration is retarded by vertical velocity component generated by turbulent shear stress. (c) 2006 Elsevier B.V. All rights reserved.

A review and classification of the existing models of cyanobacteria

Bloom-forming and toxin-producing cyanobacteria remain a persistent nuisance across the world. Modelling of cyanobacteria in freshwaters is an important tool for understanding their population dynamics and predicting bloom occurrence in lakes and rivers. In this paper existing key models of cyanobacteria are reviewed, evaluated and classified. Two major groups emerge: deterministic mathematical and artificial neural network models. Mathematical models can be further subcategorized into those models concerned with impounded water bodies and those concerned with rivers. Most existing models focus on a single aspect such as the growth of transport mechanisms, but there are a few models which couple both.

Identifying the critical parameters of a cyanobacterial growth and movement model by using generalised sensitivity analysis

Bloom-forming and toxin-producing cyanobacteria remain a persistent nuisance across the world. Modelling of cyanobacteria in freshwaters is an important tool for understanding their population dynamics and predicting the location and timing of the bloom events in lakes and rivers. A new deterministic-mathematical model was developed, which simulates the growth and movement of cyanobacterial blooms in river systems. The model focuses on the mathematical description of the bloom formation, vertical migration and lateral transport of colonies within river environments by taking into account the major factors that affect the cyanobacterial bloom formation in rivers including, light, nutrients and temperature. A technique called generalised sensitivity analysis was applied to the model to identify the critical parameter uncertainties in the model and investigates the interaction between the chosen parameters of the model. The result of the analysis suggested that 8 out of 12 parameters were significant in obtaining the observed cyanobacterial behaviour in a simulation. It was found that there was a high degree of correlation between the half-saturation rate constants used in the model.

Performance and prediction: Bayesian modelling of fallible choice in chess

Evaluating agents in decision-making applications requires assessing their skill and predicting their behaviour. Both are well developed in Poker-like situations, but less so in more complex game and model domains. This paper addresses both tasks by using Bayesian inference in a benchmark space of reference agents. The concepts are explained and demonstrated using the game of chess but the model applies generically to any domain with quantifiable options and fallible choice. Demonstration applications address questions frequently asked by the chess community regarding the stability of the rating scale, the comparison of players of different eras and/or leagues, and controversial incidents possibly involving fraud. The last include alleged under-performance, fabrication of tournament results, and clandestine use of computer advice during competition. Beyond the model world of games, the aim is to improve fallible human performance in complex, high-value tasks.

Deepest Chess Win Revisited

An examination of the deepest win in KRNKNN in the context of Ken Thompson's results.

Use of remote sensing to measure change in the extent of habitat for the critically endangered Jerdon's Courser Rhinoptilus bitorquatus in India

Jerdon's Courser Rhinoptilus bitorquatus is one of the most endangered and least understood birds in the world. It is endemic to scrub habitats in southeast India which have been lost and degraded because of human land use. We used satellite images from 1991 and 2000 and two methods for classifying land cover to quantify loss of Jerdon's Courser habitat. The scrub habitats on which this species depends decreased in area by 11-15% during this short period (9.6 years), predominantly as a result of scrub clearance and conversion to agriculture. The remaining scrub patches were smaller and further from human settlements in 2000 than in 1991, implying that much of the scrub loss had occurred close to human population centres. We discuss the implications of our results for the conservation of Jerdon's Courser and the use of remote sensing methods in conservation.

Effect of molecule branching and glycosidic linkage on the degradation of polydextrose by gut microbiota.

Polydextrose is a randomly linked complex glucose oligomer that is widely used as a sugar replacer, bulking agent, dietary fiber and prebiotic. Polydextrose is poorly utilized by the host and, during gastrointestinal transit, it is slowly degraded by intestinal microbes, although it is not known which parts of the complex molecule are preferred by the microbes. The microbial degradation of polydextrose was assessed by using a simulated model of colonic fermentation. The degradation products and their glycosidic linkages were measured by combined gas chromatography and mass spectrometry, and compared to those of intact polydextrose. Fermentation resulted in an increase in the relative abundance of non-branched molecules with a concomitant decrease in single-branched glucose molecules and a reduced total number of branching points. A detailed analysis showed a preponderance of 1,6 pyranose linkages. The results of this study demonstrate how intestinal microbes selectively degrade polydextrose, and provide an insight into the preferences of gut microbiota in the presence of different glycosidic linkages.

Constructing Melchior Lorichs's 'Panorama of Constantinople'

In Constructing Melchior Lorichs's Panorama of Constantinople, Nigel Westbrook, Kenneth Rainsbury Dark, and Rene Van Meeuwen propose that Melchior Lorichs's 1559 Panorama of Constantinople was created by using a viewing grid. The panorama is thus a reliable graphic source for the lost or since-altered Ottoman and Byzantine buildings of the city. The panorama appears to lie outside the conventional symbolic mode of topographical depiction common for its period and constitutes a rare "scientific" record of an encounter of a perspicacious observer with a vast subject. The drawing combines elements of allegory with extensive empirical observation. Several unknown structures, shown on the drawing, have been located in relation to the present-day topography of Istanbul, as a test-case for further research.