I would like to show how to code the NAO robot to beat us at Jotto (5-letter Mastermind) with
Choregraphe. I will employ a brute force technique that does not require any knowledge of the English language, the frequency of its letters, or smart combinations of vowels and consonants to try to minimize the number of attempts. It goes like this:
- Gather all 5-letter words with no repeated letters in a list.
- Choose a random word from that list—your guess—, and ask it to be scored ala Mastermind.
- Filter through the list all words that share the same score with your guess; discard the rest.
- Go back to step 2 and repeat until the target word is found.
Coding this strategy in
python requires only four variables:
whole_dict: the list with all the words
step = [x for x in whole_dict]: A copy of
whole_dict, which is going to be shortened on each step (hence the name). Note that stating
step = whole_dictwill change the contents of
whole_dictwhen we change the contents of
step— not a good idea.
guess = random.choice(step): A random choice from the list
score: A string containing the two digits we obtain after scoring the guess. The first digit indicates the number of correct letters in the same position as the target word; the second digit indicates the number of correct letters in the wrong position.
attempts: optional. The number of attempts at guessing words. For quality control purposes.
At this point, I urge the reader to stop reading the post and try to implement this strategy as a simple script. When done, come back to see how it can be coded in the NAO robot.
Every summer before school was over, I was assigned a list of books to read. Mostly nonfiction and historical fiction, but in fourth grade there that was that first science fiction book. I often remember how that book made me feel, and marvel at the impact that it had in my life. I had read some science fiction before—Well’s Time Traveller and War of the Worlds—but this was different. This was a book with witty and thought-provoking short stories by Isaac Asimov. Each of them delivered drama, comedy, mystery and a surprise ending in about ten pages. And they had robots. And those robots had personalities, in spite of their very simple programming: The Three Laws of Robotics.
- A robot may not injure a human being or, through inaction, allow a human being to come to harm.
- A robot must obey the orders given to it by human beings, except where such orders would conflict with the First Law.
- A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.
Back in the 1980s, robotics—understood as autonomous mechanical thinking—was no more than a dream. A wonderful dream that fueled many children’s imaginations and probably shaped the career choices of some. I know in my case it did.
Fast forward some thirty-odd years, when I met Astro: one of three research robots manufactured by the French company Aldebaran. This NAO robot found its way into the computer science classroom of Tom Simpson in Heathwood Hall Episcopal School, and quickly learned to navigate mazes, recognize some student’s faces and names, and even dance the Macarena! It did so with effortless coding: a basic command of the computer language
python, and some idea of object oriented programming.
I could not let this opportunity pass. I created a small undergraduate team with Danielle Talley from USC (a brilliant sophomore in computer engineering, with a minor in music), and two math majors from Morris College: my Geometry expert Fabian Maple, and a McGyver-style problem solver, Wesley Alexander. Wesley and Fabian are supported by a Department of Energy-Environmental Management grant to Morris College, which funds their summer research experience at USC. Danielle is funded by the National Science Foundation through the Louis Stokes South Carolina-Alliance for Minority Participation (LS-SCAMP).
They spent the best of their first week on this project completing a basic programming course online. At the same time, the four of us reviewed some of the mathematical tools needed to teach Astro new tricks: basic algebra and trigonometry, basic geometry, and basic calculus and statistics. The emphasis—I need to point out in case you missed it—is in the word basic.
Talk the talk
The psychologist seated herself and watched Herbie narrowly as he took a chair at the other side of the table and went through the three books systematically.
At the end of half an hour, he put them down, “Of course, I know why you brought these.”
The corner of Dr. Calvin’s lip twitched, “I was afraid you would. It’s difficult to work with you, Herbie. You’re always a step ahead of me.”
“It’s the same with these books, you know, as with the others. They just don’t interest me. There’s nothing to your textbooks. Your science is just a mass of collected data plastered together by makeshift theory — and all so incredibly simple, that it’s scarcely worth bothering about.”
“It’s your fiction that interests me. Your studies of the interplay of human motives and emotions” – his mighty hand gestured vaguely as he sought the proper words.Liar!
— Isaac Asimov
Astro can understand what I say, and maintain conversations with me. He has four microphones for voice recognition and sound localization, and two speakers for text-to-speech synthesis. But he sometimes gets confused: I say “acute”, and he understands “abide,” for example. This might sound frustrating by all standards. But mathematicians can’t be judged by any reasonable standard. Far from seeing this as a shortcoming, my team used as motivation the mechanics behind his speech recognition functionality, and they wrote some code to turn him into an expert Mastermind player.
Wait, what? How are these two things possibly connected?
Since Astro’s hearing is far from perfect, when he hears a word which is not clear, he gathers a short list of possible candidates. He then chooses the most likely guess based upon different considerations—using clues from context, for example. Based on similar strategies, he can be taught to be a perfect player of 5-letter-word Mastermind: Pick any five-letter word in the English language. Any word, provided it has no repeated letters. Astro chooses one random word as his first guess, and requests a score like in Mastermind.
To illustrate this process, I will show you how the game went when I chose Fabian’s favorite word: “acute.”
Astro: Is it firth? Me : NO Astro: How many letters of my guess are in your word, in the right position? How many letters of my guess are in your word, in the wrong position? Me : 1, 0 Astro: Is it foams? Me : NO Astro: How many letters of my guess are in your word, in the right position? How many letters of my guess are in your word, in the wrong position? Me : 0, 1 Astro: Is it junta? Me : NO Astro: How many letters of my guess are in your word, in the right position? How many letters of my guess are in your word, in the wrong position? Me : 1, 2 Astro: Is it acute? Me : YES Astro: Wonderful, I found it in 4 attempts!
I don’t want to get too technical here, but will mention some of the ideas. The main algorithm is based on techniques of numerical root finding and solving nonlinear equations — nothing complex: high-school level bracketing by bisection, or Newton’s method. To design better winning strategies, my team exploits the benefits of randomness. The analysis of this part is done with basic probability and statistics.
Walk the walk
Donovan’s pencil pointed nervously. “The red cross is the selenium pool. You marked it yourself.”
“Which one is it?” interrupted Powell. “There were three that MacDougal located for us before he left.”
“I sent Speedy to the nearest, naturally; seventeen miles away. But what difference does that make?” There was tension in his voice. “There are penciled dots that mark Speedy’s position.”
And for the first time Powell’s artificial aplomb was shaken and his hands shot forward for the man.
“Are you serious? This is impossible.”
“There it is,” growled Donovan.
The little dots that marked the position formed a rough circle about the red cross of the selenium pool. And Powell’s fingers went to his brown mustache, the unfailing signal of anxiety.
Donovan added: “In the two hours I checked on him, he circled that damned pool four times. It seems likely to me that he’ll keep that up forever. Do you realize the position we’re in?”Runaround
— Isaac Asimov
Astro moves around too. It does so thanks to a sophisticated system combining one accelerometer, one gyrometer and four ultrasonic sensors that provide him with stability and positioning within space. He also enjoys eight force-sensing resistors and two bumpers. And that is only for his legs! He can move his arms, bend his elbows, open and close his hands, or move his torso and neck (up to 25 degrees of freedom for the combination of all possible joints). Out of the box, and without much effort, he can be coded to walk around, although in a mechanical way: He moves forward a few feet, stops, rotates in place or steps to a side, etc. A very naïve way to go from
B retrieving an object at
C, could be easily coded in this fashion as the diagram shows:
Fabian and Wesley devised a different way to code Astro taking full advantage of his inertial measurement unit. This will allow him to move around smoothly, almost like a human would. The key to their success? Polynomial interpolation and plane geometry. For advanced solutions, they need to learn about splines, curvature, and optimization. Nothing they can’t handle.
Sing me a song
He said he could manage three hours and Mortenson said that would be perfect when I gave him the news. We picked a night when she was going to be singing Bach or Handel or one of those old piano-bangers, and was going to have a long and impressive solo.
Mortenson went to the church that night and, of course, I went too. I felt responsible for what was going to happen and I thought I had better oversee the situation.
Mortenson said, gloomily, “I attended the rehearsals. She was just singing the same way she always did; you know, as though she had a tail and someone was stepping on it.”One Night of Song
— Isaac Asimov
Astro has excellent eyesight and understanding of the world around him. He is equipped with two HD cameras, and a bunch of computer vision algorithms, including facial and shape recognition. Danielle’s dream is to have him read from a music sheet and sing or play the song in a toy piano. She is very close to completing this project: Astro is able now to identify partitures, and extract from them the location of the pentagrams. Danielle is currently working on identifying the notes and the clefs. This is one of her test images, and the result of one of her early experiments:
Most of the techniques Danielle is using are accessible to any student with a decent command of vector calculus, and enough scientific maturity. The extraction of pentagrams and the different notes on them, for example, is performed with the Hough transform. This is a fancy term for an algorithm that basically searches for straight lines and circles by solving an optimization problem in two or three variables.
The only thing left is an actual performance. Danielle will be leading Fabian and Wes, and with the assistance of Mr. Simpson’s awesome students Erica and Robert, Astro will hopefully learn to physically approach the piano, choose the right keys, and play them in the correct order and speed. Talent show, anyone?
Let so that too.
Show that and
I got this problem by picking some strictly positive value and breaking the integral as follows:
Let us examine now the factors and above:
We have thus proven that with At this point, all you have to do is pick (provided the denominator is not zero) and you are done.
Given a triangle the circle that goes through the midpoints of each side, is called the Feuerbach circle. It has very surprising properties:
- It also goes through the feet of the heights, points
- If denotes the orthocenter of the triangle, then the Feuerbach circle also goes through the midpoints of the segments For this reason, the Feuerbach circle is also called the nine-point circle.
- The center of the Feuerbach circle is the midpoint between the orthocenter and circumcenter of the triangle.
- The area of the circumcircle is precisely four times the area of the Feuerbach circle.
Most of these results are easily shown with sympy without the need to resort to Gröbner bases or Ritt-Wu techniques. As usual, we realize that the properties are independent of rotation, translation or dilation, and so we may assume that the vertices of the triangle are and for some positive parameters To prove the last statement, for instance we may issue the following:
>>> import sympy >>> from sympy import * >>> A=Point(0,0) >>> B=Point(1,0) >>> r,s=var('r,s') >>> C=Point(r,s) >>> D=Segment(A,B).midpoint >>> E=Segment(B,C).midpoint >>> F=Segment(A,C).midpoint >>> simplify(Triangle(A,B,C).circumcircle.area/Triangle(D,E,F).circumcircle.area) 4
But probably the most amazing property of the nine-point circle, is the fact that it is tangent to the incircle of the triangle. With exception of the case of equilateral triangles, both circles intersect only at one point: the so-called Feuerbach point.
We are familiar with that result that states that, on any given triangle, the circumcenter, centroid and orthocenter are always collinear. I would like to illustrate how to use Gröbner bases theory to prove that the incenter also belongs in the previous line, provided the triangle is isosceles.
We start, as usual, indicating that this property is independent of shifts, rotations or dilations, and therefore we may assume that the isosceles triangle has one vertex at , another vertex at and the third vertex at for some value In that case, we will need to work on the polynomial ring since we need the parameter free, the variables and are used to input the conditions for the circumcenter of the triangle, the variables and for centroid, and the variables and for the incenter (note that we do not need to use the orthocenter in this case).
We may obtain all six conditions by using sympy, as follows:
>>> import sympy >>> from sympy import * >>> A=Point(0,0) >>> B=Point(1,0) >>> s=symbols("s",real=True,positive=True) >>> C=Point(1/2.,s) >>> T=Triangle(A,B,C) >>> T.circumcenter Point(1/2, (4*s**2 - 1)/(8*s)) >>> T.centroid Point(1/2, s/3) >>> T.incenter Point(1/2, s/(sqrt(4*s**2 + 1) + 1))
This translates into the following polynomials
The hypothesis polynomial comes simply from asking whether the slope of the line through two of those centers is the same as the slope of the line through another choice of two centers; we could use then, for example, It only remains to compute the Gröbner basis of the ideal Let us use SageMath for this task:
sage: R.<s,x1,x2,x3,y1,y2,y3,z>=PolynomialRing(QQ,8,order='lex') sage: h=[2*x1-1,8*r*y1-4*r**2+1,2*x2-1,3*y2-r,2*x3-1,(4*r*y3+1)**2-4*r**2-1] sage: g=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) sage: I=R.ideal(1-z*g,*h) sage: I.groebner_basis() 
This proves the result.
I have just received a copy of Instant SymPy Starter, by Ronan Lamy—a no-nonsense guide to the main properties of SymPy, the Python library for symbolic mathematics. This short monograph packs everything you should need, with neat examples included, in about 50 pages. Well-worth its money.
Segments and are equal. Lines and intersect at Form four circumcircles: Prove that the circumcenters form a rhombus, with
Note that if this construction works, it must do so independently of translations, rotations and dilations. We may then assume that is the origin, that the segments have length one, and that for some parameters it is We let SymPy take care of the computation of circumcenters:
import sympy from sympy import * # Point definitions M=Point(0,0) A=Point(2,0) B=Point(1,0) a,theta=symbols('a,theta',real=True,positive=True) C=Point((a+1)*cos(theta),(a+1)*sin(theta)) D=Point(a*cos(theta),a*sin(theta)) #Circumcenters E=Triangle(A,C,M).circumcenter F=Triangle(A,D,M).circumcenter G=Triangle(B,D,M).circumcenter H=Triangle(B,C,M).circumcenter
Finding that the alternate angles are equal in the quadrilateral is pretty straightforward:
In : P=Polygon(E,F,G,H) In : P.angles[E]==P.angles[G] Out: True In : P.angles[F]==P.angles[H] Out: True
To prove it a rhombus, the two sides that coincide on each angle must be equal. This presents us with the first challenge: Note for example that if we naively ask SymPy whether the triangle is equilateral, we get a False statement:
In : Triangle(E,F,G).is_equilateral() Out: False In : F.distance(E) Out: Abs((a/2 - cos(theta))/sin(theta) - (a - 2*cos(theta) + 1)/(2*sin(theta))) In : F.distance(G) Out: sqrt(((a/2 - cos(theta))/sin(theta) - (a - cos(theta))/(2*sin(theta)))**2 + 1/4)
Part of the reason is that we have not indicated anywhere that the parameter theta is to be strictly bounded above by (we did indicate that it must be strictly positive). The other reason is that SymPy does not handle identities well, unless the expressions to be evaluated are perfectly simplified. For example, if we trust the routines of simplification of trigonometric expressions alone, we will not be able to resolve this problem with this technique:
In : trigsimp(F.distance(E)-F.distance(G),deep=True)==0 Out: False
Finding that with SymPy is not that easy either. This is the second challenge.
How would the reader resolve this situation?
Let me show you an exciting technique to prove some convergence statements using exclusively functional inequalities and Fatou’s Lemma. The following are two classic problems solved this way. Enjoy!
Exercise 1 Let be a measurable space and suppose is a sequence of measurable functions in that converge almost everywhere to a function and such that the sequence of norms converges to . Prove that the sequence of integrals converges to the integral for every measurable set .
Proof: Note first that
Set then (which are non-negative functions) and apply Fatou’s Lemma to that sequence. We have then
It must then be . But this proves the statement, since
Exercise 2 Let be a finite measure space and let . Suppose that is a sequence of measurable functions in whose norms are uniformly bounded in and which converge almost everywhere to a function . Prove that the sequence converges to for all where is the conjugate exponent of .
Proof: The proof is very similar to the previous problem. We start by noticing that under the hypotheses of the problem,
If we prove that , we are done.
We will achieve this by using the convexity of , since in that case it is
Set then (which are non-negative functions) and apply Fatou’s Lemma as before.