Ian Gent (St Andrews): The Winnability of Klondike and Many Other Single-Player Card Games (School Seminar)

This is joint work with Charlie Blake.

Abstract:

The most famous single-player card game is ‘Klondike’, but our ignorance of its winnability percentage has been called “one of the embarrassments of applied mathematics”. Klondike is just one of many single-player card games, generically called ‘solitaire’ or ‘patience’ games, for which players have long wanted to know how likely a particular game is to be winnable for a random deal. A number of different games have been studied empirically in the academic literature and by non-academic enthusiasts.

Here we show that a single general purpose Artificial Intelligence program, called “Solvitaire”, can be used to determine the winnability percentage of approximately 30 different single-player card games with a 95% confidence interval of ± 0.1% or better. For example, we report the winnability of Klondike to within 0.10% (in the ‘thoughtful’ variant where the player knows the location of all cards). This is a 30-fold reduction in confidence interval, and almost all our results are either entirely new or represent significant improvements on previous knowledge.

Speaker Bio:

Ian Gent is professor of Computer Science at the University of St Andrews. His mother taught him to play patience and herself showed endless patience when he “helped” her by taking complete control of the game. A program to play a patience game was one of the programs he wrote on his 1982 Sinclair Spectrum now on the wall outside his office.

Event details

  • When: 5th February 2019 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Emanuele Trucco (Dundee): Retinal image analysis and beyond in Scotland: the VAMPIRE project (School Seminar)

Abstract:

This talk is an overview of the VAMPIRE (Vessel Assessment and Measurement Platform for Images of the REtina) project, an international and interdisciplinary research initiative created and led by the Universities of Dundee and Edinburgh in Scotland, UK, since the early 2000s. VAMPIRE research focuses on the eye as a source of biomarkers for systemic diseases (e.g. cardiovascular, diabetes, dementia) and cognitive decline, as well as on eye-specific diseases. VAMPIRE is highly interdisciplinary, bringing together medical image analysis, machine learning and data analysis, medical research, and data governance and management at scale. The talk introduces concisely the aims, structure and current results of VAMPIRE, the current vision for effective translation to society, and the several non-technical factors complementing technical research needed to achieve effective translation.

Speaker Bio:

Emanuele (Manuel) Trucco, MSc, PhD, FRSA, FIAPR, is the NRP Chair of Computational Vision in Computing, School of Science and Engineering, at the University of Dundee, and an Honorary Clinical Researcher of NHS Tayside. He has been active since 1984 in computer vision, and since 2002 in medical image analysis, publishing more than 270 refereed papers and 2 textbooks, and serving on the organizing or program committee of major international and UK conferences. Manuel is co-director of VAMPIRE (Vessel Assessment and Measurement Platform for Images of the Retina), an international research initiative led by the Universities of Dundee and Edinburgh (co-director Dr Tom MacGillivray), and part of the UK Biobank Eye andVision Consortium. VAMPIRE develops software tools for efficient data and image analysis with a focus on multi-modal retinal images. VAMPIRE has been used in UK and international biomarker studies on cardiovascular risk, stroke, dementia, diabetes and complications, cognitive performance, neurodegenerative diseases, and genetics.

Event details

  • When: 29th January 2019 14:00 - 15:00
  • Where: Cole 1.33a
  • Series: School Seminar Series
  • Format: Seminar

Job vacancies: Lecturers in Computer Science

The School of Computer Science is recruiting two new Lecturers as part of a large on-going expansion of our academic staff.

You will be a scholar with a growing international research reputation in Computer Science and a commitment to delivering high quality teaching within the broad field of Computer Science and its applications. The successful candidate will be expected to have a range of interests, to be active in research publication that strengthens or complements those in the School and to be capable of teaching the subject to undergraduate and taught postgraduate students who come to us with a wide range of backgrounds.

Candidates should hold a PhD in a cognate discipline. Excellent teaching skills and an interest in promoting knowledge exchange are essential. You should also have some familiarity with grant seeking processes in relation to research councils and other sources.

Closing date: 14th January 2019

Informal enquiries can be directed to Professor Simon Dobson (hos-cs@st-andrews.ac.uk) or Dr Dharini Balasubramaniam (dot-cs@st-andrews.ac.uk).

Find out more about the vacancies further particulars on the recruitment website.

Job vacancies: Interdisciplinary Data Scientists

The Schools of Medicine and Computer Science are seeking to appoint three highly motivated data scientists with a passion for computer vision and deep learning, and specifically their application to medical imaging. The data scientists will be based in the Schools of Computer Science and Medicine at the University of St Andrews and will work on a national Innovate UK funded initiative to create a pan Scotland Industrial Centre for AI Research in Digital Diagnostics (iCAIRD).

The successful candidates will have the opportunity to work alongside and learn from clinicians, industrial experts from Philips Healthcare and academics to help develop artificial intelligence solutions for the automatic reporting of cancer diagnoses in endometrial and cervical cancer. The main duties of the role will involve being an active member of an interdisciplinary team of scientists to help develop deep learning algorithms, within industry standard guidelines, to analyse patient samples in a manner that allows rapid clinical transfer. This work will therefore have the opportunity to impact both patient welfare and relieve pathologist work burden.

Applicants should have experience in machine learning, demonstrable experience in computer programming languages and an interest in the medical applications of computer science. The candidates would benefit from a track record in scientific writing and working in interdisciplinary teams as well as experience in computer vision.

The posts are full time and over a period of 36 months.
Closing Date: 18 January 2019

Find out more about the vacancies further particulars on the recruitment website.

December Graduation 2018

Congratulations to the Masters Class of 2018, and PhD students Dr Daniel Rough and Dr Adeola Fabola who graduated last week. The School also celebrated the Installation of Professor Adam Barker. Students and guests were invited to a reception in Computer Science after the ceremony to celebrate their achievement and reflect on their time in the School.

Our graduates move on to a wide variety of interesting and challenging employment and further study opportunities, and we wish them all well with their future careers.

PhD viva success: Shyam Reyal

Congratulations to Shyam Reyal, who successfully defended his thesis yesterday. He is pictured with Internal examiner Dr Tom Kelsey and external examiner Dr Mark Dunlop , from the University of Strathclyde. Shyam’s research was supervised by Dr Per Ola Kristensson and Dr Mark-Jan Nederhof.

Image courtesy of Annemarie Paton

PhD viva success: Julian Petford

Congratulations to Julian Petford, who successfully defended his thesis today. He is pictured with internal examiner Professor Aaron Quigley and external examiner Dr Jason Alexander, from Lancaster University. Julian’s PhD research in Full Coverage Displays for Non-Immersive Applications was supervised by Dr Miguel Nacenta.

Image courtesy of Wendy Boyter

Dr Roy Dyckhoff: A Eulogy

A Service of Thanksgiving was held at St Salvator’s Chapel on Saturday in memory of Roy Dyckhoff who died in hospital in September. The service included a eulogy composed and delivered by Head of School Professor Simon Dobson.

Since his death I’ve been fascinated to hear how others saw Roy — and how their views differed noticeably from what I saw in him. My perception was of a mathematician who’d made his home in computer science, at the computational end of our shared disciplines: someone fascinated by notions of proof as applied to computation, with a far broader and deeper mathematical knowledge than most of his colleagues and an ability to point out links between the practical and the theoretical. But in recent months I’ve learned of many different Roys: the one who moved from topology to category theory in his PhD; the one who worked on proof theory; the one who was a mainstay of computational logic in the UK; the one who rang bells here in our beautiful chapel; who climbed mountains; who studied languages — and probably many others that I’ll learn more of over the course of today.

Roy started at programming early: a one-year job with punched cards before going up to Cambridge as a maths undergraduate. And while doing his degree he spent his second year — when for some reason he had no maths exams — attending all the lectures, tutorials, and seminars for a degree in Persian. (As one does.) Perhaps this should have been a hint there that maths was only ever going to be a part of his intellectual career; or perhaps it was an early signature of an individual with exceptionally wide-ranging interests, who would constantly return to pure maths from lengthy diversions into other subjects. One look at the bookshelves of his house in St Andrews tells you this — volumes on renaissance art, arts and crafts, world history, and early music sitting alongside the algebra and number theory. It’s interesting also to look at theses of his nine PhD students, interesting how many of them sit at interfaces: between proof theory and category theory, between logic and search, between logic programming, functional programming, and type theory.

But such a broad base of interests sat on a bedrock of fascination for precision — indeed, a demand for precision, and an irritation that other people and organisations seemed so unreasonably comfortable with anything less than precise approaches to subjects. We saw this clearly in Roy’s (repeated) attempts to translate some or other aspect of the university’s regulations into first-order logic — an activity with which he persisted in the face of almost complete bafflement on the part of those to whom he addressed his memoranda. “Let S be the set of all students, and consider a set M of modules operated on by a collection of groups G-sub-i such that…” and so on. I’ve sometimes wondered how those on the receiving end felt about this mathematician’s take on their job — or indeed whether Roy himself imagined the university’s administration to be populated entirely by frustrated logicians, trapped in an imprecise world of programme requirements and module anti-requisites, and as anxious as him to re-write the rules with precision.

Given all this, I think it’s hard to assess what Roy’s influence has been, since it’s been spread over so many disparate areas — and that’s probably a good thing. “Activity is the enemy of thought,” as Christopher Strachey once observed, and the attempt to measure and quantify thought isn’t far behind. It’s not bad in itself, but we now know it breeds a narrow specialisation that over-values increasingly deep looks at increasingly tiny areas of knowledge, and systematically under-values those who want, and feel able, to contribute more widely — as Roy did. If there’s anything to take away from his career, I think it would be this, an example of scholarship that is at once broad, deep, intellectually honest, and constantly curious.

For those who’d like to mark his passing in some way, the family have suggested giving blood as a suitable marker. Alternatively, they are collecting for the Scottish Mountain Bothies Association, which was a charity he supported for many years. https://mydonate.bt.com/fundraisers/roydyckhoff