Games like 8-Ball offer many interesting challenges for both AI and optimization communities because of the continuous and stochastic characteristics of the domain. To succeed, a player must be able to plan the best sequence of shots and execute them with accuracy and precision, so that he does not lose the turn. The artificial players developed to date tend to take more than 30 seconds to select and execute a shot. Under a videogame setting, a player would give up playing the game if he had to wait that long for his turn. To solve this problem, we propose a real-time solution using a Monte-Carlo and Expectimax hybrid search algorithm with ray tracing techniques.

A parallel flow of non-interacting point particles is incident on a body at rest. When hitting the body’s surface, the particles are reflected elastically. Assuming that each particle hits the body at most once (the single impact condition (SIC)), the force of resistance of the body along the flow direction can be written down in a simple analytical form. The problem of minimal resistance within this model was first considered by Newton (Newton 1687 Philosophiae Naturalis Principia Mathematica) in the class of bodies with a fixed length M along the flow direction and with a fixed maximum orthogonal cross section , under the additional conditions that the body is convex and rotationally symmetric. Here we solve the problem (first stated in Buttazzo et al 1995 Minimum problems over sets of concave functions and related questions Math. Nachr. 173 71–89) for the wider class of bodies satisfying the SIC and with the additional conditions removed. The scheme of solution is inspired by Besicovitch’s method of solving the Kakeya problem (Besicovitch 1963 The Kakeya problem Am. Math. Mon. 70 697– 706). If is a disc, the decrease of resistance as compared with the original Newton problem is more than twofold; the ratio tends to 2 as M 0 and to 20.25 as M . We also prove that the infimum of resistance is 0 for a wider class of bodies with both single and double reflections allowed.

The book contains an account of results obtained by the author and his collaborators on billiards in the complement of bounded domains and their applications in aerodynamics and geometrical optics. We consider several problems related to aerodynamics of bodies in highly rarefied media. It is assumed that the medium particles do not interact with each other and are elastically reflected when colliding with the body boundary; these assumptions drastically simplify the aerodynamics and allow to reduce it to a number of purely mathematical problems. First we examine problems of minimal resistance in the case of translational motion of bodies. These problems generalize the Newton problem of least resistance; the difference is that the bodies are generally nonconvex in our case and therefore the particles can make multiple reflections from the body surface. It is proved that typically the infimum of resistance equals zero; thus, there exist 'almost perfectly streamlined' bodies. Next we consider the generalization of Newton's problem on minimal resistance of convex axisymmetric bodies to the case of media with thermal motion of particles. Two kinds of solutions are found: first, Newton-like bodies and second, shapes obtained by gluing together two Newton-like bodies along their rear ends. Further, we state results on characterization of billiard scattering by nonconvex and rough bodies; next we solve some special problems of optimal mass transportation. These two groups of results are applied to problems of minimal and maximal resistance for bodies that move forward and at the same time slowly rotate. It is found, in particular, that the resistance of a three-dimensional convex body can be increased at most twice and decreased at most by 3.05% by roughening its surface. Next, we consider a rapidly rotating rough disc moving in a rarefied medium on the plane. It is shown that the force acting on the disc is not generally parallel to the direction of the disc motion, that is, has a nonzero transversal component. This phenomenon is called Magnus effect (proper or inverse, depending on the direction of the transversal component). We show that the kind of Magnus effect depends on the kind of disc roughness, and study this dependence. The problem of finding all admissible values of the force acting on the disc is formulated in terms of a vector-valued problem of optimal mass transportation. Finally, we describe bodies that have zero resistance when translating through a medium, and state results on existence or non-existence of bodies with mirror surface invisible in one or several directions. We also consider the problem of constructing retroreflectors: bodies with specular surface that reverse the direction of any incident beam of light.

We study the problem of invisibility for bodies with a mirror surface in the framework of geometrical optics. We show that for any two given directions it is possible to construct a two-dimensional fractal body invisible in these directions. Moreover, there exists a three-dimensional fractal body invisible in three orthogonal directions. The work continues the previous study in [1, 12], where two-dimensional bodies invisible in one direction and three dimensional bodies invisible in one and two orthogonal directions were constructed.

A body moves in a rarefied medium composed of point particles at rest. The particles make elastic reflections when colliding with the body surface, and do not interact with each other. We consider a generalization of Newton’s minimal resistance problem: given two bounded convex bodies C1 and C2 such that C1 ⊂ C2 ⊂ R3 and ∂C1 ∩ ∂C2 = ∅, minimize the resistance in the class of connected bodies B such that C1 ⊂ B ⊂ C2. We prove that the infimum of resistance is zero; that is, there exist ”almost perfectly streamlined” bodies.

This article presents a brief exposition of recent results of the author on billiard scattering by rough obstacles. We define the notion of a rough body and give a characterization of scattering by rough bodies. Then we define the resistance of a rough body; it can be interpreted as the aerodynamic resistance of the somersaulting body moving through a rarefied medium. We solve the problems of maximum and minimum resistance for rough bodies (more precisely, for bodies obtained by roughening a prescribed convex set) in arbitrary dimension. Surprisingly, these problems are reduced to special problems of optimal mass transportation on the sphere.

We consider a mechanical problem concerning a 2D axisymmetric body moving forward on the plane and making slow turns of fixed magnitude about its axis of symmetry. The body moves through a medium of non-interacting particles at rest, and collisions of particles with the body's boundary are perfectly elastic (billiard-like). The body has a blunt nose: a line segment orthogonal to the symmetry axis. It is required to make small cavities with special shape on the nose so as to minimize its aerodynamic resistance. This problem of optimizing the shape of the cavities amounts to a special case of the optimal mass transfer problem on the circle with the transportation cost being the squared Euclidean distance. We find the exact solution for this problem when the amplitude of rotation is smaller than a fixed critical value, and give a numerical solution otherwise. As a by-product, we get explicit description of the solution for a class of optimal transfer problems on the circle.

We construct semi infinite billiard domains which reverse the direction of most incoming particles. We prove that almost all particles will leave the open billiard domain after a finite number of reflections. Moreover, with high probability the exit velocity is exactly opposite to the entrance velocity, and the particle's exit point is arbitrarily close to its initial position. The method is based on asymptotic analysis of statistics of entrance times to a small interval for irrational circle rotations. The rescaled entrance times have a limiting distribution in the limit when the length of the interval vanishes. The proof of the main results follows from the study of related limiting distributions and their regularity properties. © 2011 AIMSciences.

We study the Magnus effect: deflection of the trajectory of a spinning body moving in a gas. It is well known that in rarefied gases, the inverse Magnus effect takes place, which means that the transversal component of the force acting on the body has opposite signs in sparse and relatively dense gases. The existing works derive the inverse effect from nonelastic interaction of gas particles with the body. We propose another (complementary) mechanism of creating the transversal force owing to multiple collisions of particles in cavities of the body surface. We limit ourselves to the two-dimensional case of a rough disc moving through a zero-temperature medium on the plane, where reflections of the particles from the body are elastic and mutual interaction of the particles is neglected. We represent the force acting on the disc and the moment of this force as functionals depending on 'shape of the roughness;, and determine the set of all admissible forces. The disc trajectory is determined for several simple cases. The study is made by means of billiard theory, Monge-Kantorovich optimal mass transport and by numerical methods. This journal is © 2010 The Royal Society.