Monthly Archives: January 2016

Interesting probability theory descriptions of games like minesweeper

minesweeperWhat are some interesting probability theory descriptions of games like minesweeper?

The Minesweeper game was (surprisingly) often used as a toy model for studying randomized algorithms and algorithms working in random environments.

A nice introduction to both algorithmic and probabilistic aspects of the Minesweeper can be found in this B. Sc. thesis “Algorithmic Approaches to Playing Minesweeper” by David J. Becerra from Harvard.

Some advanced studies exploring different algorithms and their relation to probabilistic models of the Minesweeper can be seen in the paper “Optimistic Heuristics for MineSweeper” by O. Buffet, Ch.-Sh. Lee, W. Lin, O. Teytaud,

or in the paper by M. Sebag and O. Teytaud “Combining Myopic Optimization and Tree Search: Application to MineSweeper”.

As for games like minesweeper in general, some of them were found to be connected with percolation theory (which is one of the most fashionable branches of probability at the moment), as well as with Markov decision processes, and computational complexity studies.

A good example of research in this direction is a paper “The Minesweeper game: Percolation and Complexity” written by Elchanan Mossel from Microsoft Research.

pc-gamersWhat does all of this beautiful mathematics says to a passionate gamer? Namely, what would be a good algorithm for solving the puzzle, and is the solution computationally hard?

In fact, the minesweeper is one of the classical board puzzles based on algebras of binary variables. Algorithmic solutions to these problems are typically sought with the use of integer linear programming. Unlike simple linear programming, integer programming problems are typically NP-hard. This is true even for binary integer programming where variables can only be 0 or 1 rather than arbitrary integers.

This transforms into the fact that, in its general formulation, the minesweeper is indeed algorithmically NP-complete. However, there is an argument that, if the minesweeper board is already known to be consistent, solving it is only guaranteed to be co-NP-complete, and might be (or not be) NP-complete.

And here is the raining defending Minesweeper world rekord holder Kamil Muranski performs his skillful play. Not sure if his brain is using integer linear programming or not 🙂


Good introduction to general relativity theory for mathematicians

einstein1_7What is a good introduction to general relativity for a mathematician?

A direct and specific Quora question. Definitely demands a direct and specific answer 🙂

If you are a fan of vintage classics, you can go with Hermann Weyl “Space, time, matter”.

It’s an old book, but still very readable as an introduction for mathematicians. And the author is Hermann Weyl, out of all people. And I personally like him even more since he also graduated from the University of Göttingen.

And then, of course, you have the all-time classics L.D. Landau & E.M. Lifshitz “The Classical Theory of Fields” ( Volume 2 of A Course of Theoretical Physics ).

Yes, these are the guys from the Landau-Lifshitz equation. Landau was a Nobel Prize winner (and a student at Göttingen 🙂 ), and both Landau and Evgeny Lifshitz were academicians of the Russian Academy of Sciences and honorary members of many other national scientific societies around the globe.

Their book is rough, tough and mathematical, but provides a great introduction and explains so many important aspects of the theory, while most of modern introductory books just do hand waving and popular lingo speaking for hundreds of pages.

And, as a note of caution: if you aim to understand the general relativity and do not want to read pseudo-scientific fantasy, avoid books by Stephen Hawking.

P.S.  The guy from the picture above is famous not only for his creation of the relativity theory, but also for some of the work that he did at the German Federal Institute of Physical and Technical Affairs, also known as PTB and as the place where I’m happily doing my own  research affairs for the past three years. The world feels so small right now 🙂

What careers are avaliable that require an extensive knowledge of mathematical logic?

Russian_Sherlock_Holmes_1Besides Computer Engineering / Computer Science, of course. Naturally, this is a Quora question once again.

As a good example, any profession that involves data analysis, processing or modeling, requires a solid knowledge of mathematical logic. By solid knowledge I mean finishing at least one semester course on formal logic at a university.

The reason for this is that data is represented to us as numbers, and studying numbers is governed by mathematics. Numbers belong to mathematics, they were born within mathematics. And any type of work in maths requires decent understanding of formal logic.

Therefore, not only careers in Computer Science, but also careers in data science, machine learning, quantitative finance, economics or meteorology all demand having a good knowledge of logic.

Additionally, formal logic is instrumental in any profession that requires Sherlock Holmes-level deduction and argumentation on the basis of facts. This includes lawyers and criminal investigators. They do have courses on formal logic in some of the better institutes.

Just having a good common sense can’t fully replace a course in formal logic. Since the times of the Russell or Zermelo paradoxes, it was understood that the so-called naive logic (based on unformalized common sense and the naive set theory) is self-contradictory. Good understanding of basics of formal logic prevents you from running into paradoxes in your debates.