"The Volatility Smile" - a first impression

I always do this.

I'm casually scanning the Amazon Vine list, scrolling past beauty aids and iPhone covers when I come across "The Volatility Smile".

What kind of title is that? A detective story with a Japanese print on its front cover?

OK, it's got my attention. And then it gets worse:

"The Black–Scholes–Merton option model was the greatest innovation of 20th century finance, and remains the most widely applied theory in all of finance. Despite this success, the model is fundamentally at odds with the observed behavior of option markets: a graph of implied volatilities against strike will typically display a curve or skew, which practitioners refer to as the smile, and which the model cannot explain. Option valuation is not a solved problem, and the past forty years have witnessed an abundance of new models that try to reconcile theory with markets.

"The Volatility Smile presents a unified treatment of the Black–Scholes–Merton model and the more advanced models that have replaced it. It is also a book about the principles of financial valuation and how to apply them. Celebrated author and quant Emanuel Derman and Michael B. Miller explain not just the mathematics but the ideas behind the models."

I have only the haziest memory of understanding puts and calls once, but this sounds fascinating! A free book to review with some serious analysis.

As is the way with Amazon Vine, it arrives the very next day and I begin to appreciate the enormity of what I've done.

• Authors: theoretical physicist, mathematical economist, physicist
• The text, though billed as 'for traders', name-drops Hilbert spaces in the prologue
• We hit Black-Scholes really hard!

When faced with a book in a paradigm I'm barely familiar with, it's Wikipedia time. Derman and Miller's first throwaway formulae for stock volatility sends me scurrying off to random walks.

What really works though is the continuous version, the Wiener process which seems to underlie the Black-Scholes model. This, in its turn, seems to require something I hadn't heard of before, the Itô calculus.

Did I mention Martingales?

My problem is that I lack all orientation in this forest of technical virtuosity. Still, I even know where to go in these situations: YouTube.

Searching for a "conceptual overview of Black-Scholes" gets you a stack of introductory lectures. The Khan Academy (ten minute clip) was really simple and sketched the big picture: I'm to think of it as pricing call options.

I don't think those shouty traders know much about partial differential equations or their extension to stochastic processes. This book is quant territory - I'm not surprised that most senior money managers were all at sea back in 2008.

Still, I have the map of the territory now (I re-read the very clear Wikipedia article on call options) so it's time to get back to the book.

I'm looking forward to writing a semi-informed review .. at some point.

---

Update (Saturday Feb 4th 17): I've now posted the review.

Skubalon

This post in homage to wonderful AI systems such as IBM's Deep Blue, Google's DeepDream and the marvels emanating from DeepMind.

---

Alarms screamed, speakers blared, screens flared red. The nerve centre of US Western Command snapped to high alert. The indicators showed a missile launch from the Pacific, heading for San Francisco.

The new President's aggressive stance towards the Asian powers had already ratcheted tensions. New missile defense platforms had been rushed into service. Perhaps the key issue was real time sensor integration and classification.

With so much data pouring in, how could any one person figure what the hell was going on?

Skubtech inc had won the contract with its innovative deep learning platform. A highly-tuned convolutional neural network running on tens of thousands of cores, it was plugged into every radar, optical, thermal and human tactical asset of Western Command.

The OC called up his Skubtech chatbot interface.

"What the f***'s coming my way?" he demanded.

The chatbot murmured reassurance in its breathless Scarlett Johansson voice; the General began to relax, mentally preparing to stand down from DEFCON 1.

---

The missile wasn't at all accurate, it airburst five miles off the coast. It wasn't the EMP or the thermal flash which did the damage. The shock wave from the multi-kiloton fireball slammed onto the ocean surface: which triggered the San Andreas fault.

It was the big one.

---

Congressional investigators interviewed the CTO of Skubtech. He explained that the AI had been trained on hundreds of submarine missile launches.

"The North Koreans really haven't mastered submarine launches," he told the committee.

"The missile emerged from the sea and promptly set off towards North Korea. Eventually it veered around and took a circuitous path towards the American shoreline. Really, the CNN had never experienced anything like it."

The investigators had been thorough, and were not about to accept this bland reassurance as any kind of answer. They had their whistleblowers inside the company.

"This is not the first time your AI has misclassified. In internal trials, we've been led to believe that your product systematically overfits.

"Isn't it true that the development team call it .. DeepSh*t?"

Replies to recent comments

For some reason Blogger isn't letting me respond to other people's comments. Sorry about that. So I'm doing it here.

Roy had three comments.

1. On the Lisp code for noughts and crosses:

"Not sure that the written explanation of the final test board makes sense. If X plays next then X plays 1 and wins. If O plays next then O plays 2 and wins. So why are we told about e.g. "If O plays 3"...?"

My response: It is X to go next. The options I document reflect the structure of the game tree from this board position onwards.

2. To the comment on the Imperial College lecture series:

"The Logic presented in Lecture 7 is strongly Classical: ¬¬P = P and ¬P v P = True. One may need to reflect on how universally applicable this is in the full AI context (e.g. Databases with incomplete information, etc)."

My response: I think that's normal for a first, undergraduate course on computational logic. There's a large and diverse literature on how to cope with more open worlds.

3.  The comment on My noughts and crosses program finally works!:

"So is it : "Minimax Depth 4 solves 3 X 3 noughts and crosses" but Depth 3 might not? The "Infant's Brain" Challenge, of course, is to determine how they can succeed without calculating a complete tree/solution. Although there are errors, in general settings the (advanced) Infant performance is superior... I am not sure that ANNs are really helping understand this, as you remarked after that earlier book review."

My response: Agree that no-one really knows how toddlers brains do noughts and crosses, or most other stuff. Limitations on search depth - the *depth* parameter - put the mx-player in the hands of the heuristic evaluation function. I really did not spend a lot of time with this, either designing or testing it. It just rewards lines where you have a chance to complete and penalises lines where your opponent can, and returns the difference. One could do a lot better.

The end point would presumably be an evaluation function equivalent to the competent toddler.

Imperial College: automated theorem proving & neural nets

These Imperial College lectures date back to 2006 and 2009 (Simon Colton), but the underlying principles haven't changed. The earlier lectures (starting here) provide an introduction to AI and logic: we get to implementation at lecture 7 and subsequent.

I've chosen them for their clarity and completeness. The level of detail is that of a good overview.

---

Lecture 7: Making Deductive Inferences

We have shown how knowledge can be represented in first-order logic, and how rule-based expert systems expressed in logic can be constructed and used. We now look at how to take some known facts about a domain and deduce new facts from them. This will, in turn, enable agents to prove things, i.e., to start with a set of statements we believe to be true (axioms) and deduce whether another statement (theorem) is true or not.

We will first look at how to tell whether a sentence in propositional logic is true or false. This will suggest some equivalences between propositional sentences, which allow us to rewrite sentences to other sentences which mean the same thing, regardless of the truth or meaning of the individual propositions they contains. These are reversible inferences, in that deduction can be applied either way.

We then look at propositional and first-order inference rules in general, which enable us deduce new sentences if we know that certain things are true, and which may not be reversible.

Lecture 8: The Resolution Method

A minor miracle occurred in 1965 when Alan Robinson published his resolution method. This method uses a generalised version of the resolution rule of inference we saw in the previous lecture. It has been mathematically proven to be refutation-complete over first order logic. This means that if you write any set of sentences in first order logic which are unsatisfiable (i.e., taken together they are false, in that they have no models), then the resolution method will eventually derive the False symbol, indicating that the sentences somehow contradict each other.

In particular, if the set of first order sentences comprises a set of axioms and the negation of a theorem you want to prove, the resolution method can be used in a proof-by-contradiction approach. This means that, if your first order theorem is true then proof by contradiction using the resolution method is guaranteed to find the proof to a theorem eventually.

Lecture 9: Resolution Theorem Proving

To recap, we have looked at logic and some rules of deduction in order to understand automated reasoning in the general case. In the last lecture we looked at a particular rule of inference, the resolution rule. We know that the application of this rule produces a complete search method, which means that it will prove any true theorem which can be written in first order logic. Application of the rule relies on having two sentences in conjunctive normal form (CNF) where one literal of one unifies with the negation of a literal in the other. We described how to write first order sentences in CNF, and how to find unifying substitutions in lecture 8. In this lecture, we look at exactly how to use the resolution rule to prove first order theorems in practice.

Lecture 10: Overview of Machine Learning

We have looked at the automation of intelligent tasks using deduction to infer new information from old. We now look at the use of inductive reasoning to infer new information from old. ...

As with many areas in AI, machine learning has become fairly specialised. In this case, learning from examples dominates the field, partially because of the applications it affords. If a learning agent can look at the examples of share prices and learn a reason why some shares fall during the first financial quarter, this is of great commercial advantage. If another agent can learn reasons why certain chemicals are toxic and others are not, this is of great scientific value. If another agent yet can learn what a tank looks like given just photographs of tanks, this is of great military advantage.

Lecture 11: Decision Tree Learning

As discussed in the last lecture, the representation scheme we choose to represent our learned solutions and the way in which we learn those solutions are the most important aspects of a learning method. We look in this lecture at decision trees - a simple but powerful representation scheme, and we look at the ID3 method for decision tree learning.

Lecture 12: Two Layer Artificial Neural Networks

Decision trees, while powerful, are a simple representation scheme. While graphical on the surface, they can be seen as disjunctions of conjunctions, and hence are a logical representation, and we call such schemes symbolic representations. In this lecture, we look at a non-symbolic representation scheme known as Artificial Neural Networks. This term is often shortened to Neural Networks, but this annoys neuro-biologists who deal with real neural networks (inside our human heads).

As the name suggests, ANNs have a biological motivation, and we briefly look at that first. Following this, we look in detail at how information is represented in ANNs, then we look at the simplest type of network, two layer networks. We look at perceptrons and linear units, and discuss the limitations that such simple networks have. In the next lecture, we discuss multi-layer networks and the back-propagation algorithm for learning such networks.

Lecture 13: Multi-Layer Artificial Neural Networks

We can now look at more sophisticated ANNs, which are known as multi-layer artificial neural networks because they have hidden layers. These will naturally be used to undertake more complicated tasks than perceptrons.

We first look at the network structure for multi-layer ANNs, and then in detail at the way in which the weights in such structures can be determined to solve machine learning problems. There are many considerations involved with learning such ANNs, and we consider some of them here. First and foremost, the algorithm can get stuck in local minima, and there are some ways to try to get around this.

As with any learning technique, we will also consider the problem of overfitting, and discuss which types of problems an ANN approach is suitable for.

Diary: books + Clare's health

Not many posts for the next few days as we have a visitor: my 'study' reverts to its ur-status as bedroom.

I ordered Sean Carroll's book (which should be arriving tomorrow or Saturday) ..

.. on account that one reviewer (3 stars) complained it was 'too hard'. I'll try to let you know.

---

Strange how hard it is to predict another's taste in books. I really appreciated Scott Bakker's "The Disciple of the Dog" but all that inline philosophy slowed it down way too much for Clare.

It's been replaced - amazingly - by the famous "The Mote in God's Eye" which she is lapping up as I read it to her.

We haven't even reached the gripping alien lightsail contact event yet; still in the early chapters of Niven's and Pournelle's backstory building, usually condemned as 'boring'.

---

I remain a fan of Scott Bakker and have purchased (Kindle) this: (start of a mega-epic) ..

.. which seems awfully complicated. I have dipped my toe in.

---

My third ordered volume is "The Genome Factor: What the Social Genomics Revolution Reveals About Ourselves, Our History, and the Future" by Dalton Conley and Jason Fletcher.

I'm hyper-wary of the fluffy-bunny pleasantries of the Standard Social Science Model, but it seems well-regarded so I'm taking the risk. Should be out some time in late February.

---

Do you hear that hacking cough from the bedroom? Clare is much recovered today but the sub-zero windchill of our lunchtime shopping trip to Waitrose has sapped her energy .. and she has retired to bed. Still, direction of progress is positive.

---

Well, enough time here. I think it's time to re-acquaint myself with J. A Robinson's exemplary treatment of unification with those substitution subtleties ... .

My noughts and crosses program finally works!

Oh the euphoria which strikes the programmer when that final bug has been defeated and the program actually works!

It's been a long road: the philosophical meditation, the success implementing a random opponent and finally getting the minimax player to work.

And it's as cunning as a fox!

My previous post has the boring, but necessary code. Be impressed.

My next project is this Israeli Resolution Theorem Prover - to thoroughly understand it, and bend it to my will.

---

Noughts and crosses seems such a simple game. But it's anything but when your game-strategy is tree search.

Take this board position, X to move.

CL-USER 5 >    (setf b '(X 1 2 3 X 5 O 7 O))

(X 1 2 3 X 5 O 7 O)

CL-USER 6 >    (print-board b)

     X | 1 | 2
     3 | X | 5
     O | 7 | O

Plainly X has to move to 7, otherwise it's game over. If X does so, and O incompetently fails to move to 1, then X wins. Otherwise, it's mostly a draw.

---

Here is what the minimax algorithm (playing X) produces from:

CL-USER 7 >   (setf mx-tree (txminimax (xtree 'X 'X (mknode b 9 T) *depth*) t) )

CL-USER 8 >  (pprint mx-tree)

This tree:

(((X 1 2 3 X 5 O 7 O) 9 0)
 ((((X X 2 3 X 5 O 7 O) 1 -32)
   ((((X X O 3 X 5 O 7 O) 2 32)
     ((((X X O X X 5 O 7 O) 3 -32)
       ((((X X O X X O O 7 O) 5 -32) NIL) (((X X O X X 5 O O O) 7 -32) NIL)))
      (((X X O 3 X X O 7 O) 5 -32)
       ((((X X O O X X O 7 O) 3 0) NIL) (((X X O 3 X X O O O) 7 -32) NIL)))
      (((X X O 3 X 5 O X O) 7 32) NIL)))
    (((X X 2 O X 5 O 7 O) 3 32)
     ((((X X X O X 5 O 7 O) 2 32) NIL)
      (((X X 2 O X X O 7 O) 5 -32)
       ((((X X O O X X O 7 O) 2 0) NIL) (((X X 2 O X X O O O) 7 -32) NIL)))
      (((X X 2 O X 5 O X O) 7 32) NIL)))
    (((X X 2 3 X O O 7 O) 5 32)
     ((((X X X 3 X O O 7 O) 2 32) NIL)
      (((X X 2 X X O O 7 O) 3 -32)
       ((((X X O X X O O 7 O) 2 -32) NIL) (((X X 2 X X O O O O) 7 -32) NIL)))
      (((X X 2 3 X O O X O) 7 32) NIL)))
    (((X X 2 3 X 5 O O O) 7 -32) NIL)))
  (((X 1 X 3 X 5 O 7 O) 2 -32)
   ((((X O X 3 X 5 O 7 O) 1 0)
     ((((X O X X X 5 O 7 O) 3 -32)
       ((((X O X X X O O 7 O) 5 -2) NIL) (((X O X X X 5 O O O) 7 -32) NIL)))
      (((X O X 3 X X O 7 O) 5 -32)
       ((((X O X O X X O 7 O) 3 -2) NIL) (((X O X 3 X X O O O) 7 -32) NIL)))
      (((X O X 3 X 5 O X O) 7 0)
       ((((X O X O X 5 O X O) 3 0) NIL) (((X O X 3 X O O X O) 5 0) NIL)))))
    (((X 1 X O X 5 O 7 O) 3 32)
     ((((X X X O X 5 O 7 O) 1 32) NIL)
      (((X 1 X O X X O 7 O) 5 -32)
       ((((X O X O X X O 7 O) 1 -2) NIL) (((X 1 X O X X O O O) 7 -32) NIL)))
      (((X 1 X O X 5 O X O) 7 0)
       ((((X O X O X 5 O X O) 1 0) NIL) (((X 1 X O X O O X O) 5 4) NIL)))))
    (((X 1 X 3 X O O 7 O) 5 32)
     ((((X X X 3 X O O 7 O) 1 32) NIL)
      (((X 1 X X X O O 7 O) 3 -32)
       ((((X O X X X O O 7 O) 1 -2) NIL) (((X 1 X X X O O O O) 7 -32) NIL)))
      (((X 1 X 3 X O O X O) 7 0)
       ((((X O X 3 X O O X O) 1 0) NIL) (((X 1 X O X O O X O) 3 4) NIL)))))
    (((X 1 X 3 X 5 O O O) 7 -32) NIL)))
  (((X 1 2 X X 5 O 7 O) 3 -32)
   ((((X O 2 X X 5 O 7 O) 1 32)
     ((((X O X X X 5 O 7 O) 2 -32)
       ((((X O X X X O O 7 O) 5 -2) NIL) (((X O X X X 5 O O O) 7 -32) NIL)))
      (((X O 2 X X X O 7 O) 5 32) NIL)
      (((X O 2 X X 5 O X O) 7 -2)
       ((((X O O X X 5 O X O) 2 0) NIL) (((X O 2 X X O O X O) 5 -2) NIL)))))
    (((X 1 O X X 5 O 7 O) 2 32)
     ((((X X O X X 5 O 7 O) 1 -32)
       ((((X X O X X O O 7 O) 5 -32) NIL) (((X X O X X 5 O O O) 7 -32) NIL)))
      (((X 1 O X X X O 7 O) 5 32) NIL)
      (((X 1 O X X 5 O X O) 7 -32)
       ((((X O O X X 5 O X O) 1 0) NIL) (((X 1 O X X O O X O) 5 -32) NIL)))))
    (((X 1 2 X X O O 7 O) 5 -32)
     ((((X X 2 X X O O 7 O) 1 -32)
       ((((X X O X X O O 7 O) 2 -32) NIL) (((X X 2 X X O O O O) 7 -32) NIL)))
      (((X 1 X X X O O 7 O) 2 -32)
       ((((X O X X X O O 7 O) 1 -2) NIL) (((X 1 X X X O O O O) 7 -32) NIL)))
      (((X 1 2 X X O O X O) 7 -32)
       ((((X O 2 X X O O X O) 1 -2) NIL) (((X 1 O X X O O X O) 2 -32) NIL)))))
    (((X 1 2 X X 5 O O O) 7 -32) NIL)))
  (((X 1 2 3 X X O 7 O) 5 -32)
   ((((X O 2 3 X X O 7 O) 1 32)
     ((((X O X 3 X X O 7 O) 2 -32)
       ((((X O X O X X O 7 O) 3 -2) NIL) (((X O X 3 X X O O O) 7 -32) NIL)))
      (((X O 2 X X X O 7 O) 3 32) NIL)
      (((X O 2 3 X X O X O) 7 0)
       ((((X O O 3 X X O X O) 2 2) NIL) (((X O 2 O X X O X O) 3 0) NIL)))))
    (((X 1 O 3 X X O 7 O) 2 32)
     ((((X X O 3 X X O 7 O) 1 -32)
       ((((X X O O X X O 7 O) 3 0) NIL) (((X X O 3 X X O O O) 7 -32) NIL)))
      (((X 1 O X X X O 7 O) 3 32) NIL)
      (((X 1 O 3 X X O X O) 7 2)
       ((((X O O 3 X X O X O) 1 2) NIL) (((X 1 O O X X O X O) 3 2) NIL)))))
    (((X 1 2 O X X O 7 O) 3 0)
     ((((X X 2 O X X O 7 O) 1 -32)
       ((((X X O O X X O 7 O) 2 0) NIL) (((X X 2 O X X O O O) 7 -32) NIL)))
      (((X 1 X O X X O 7 O) 2 -32)
       ((((X O X O X X O 7 O) 1 -2) NIL) (((X 1 X O X X O O O) 7 -32) NIL)))
      (((X 1 2 O X X O X O) 7 0)
       ((((X O 2 O X X O X O) 1 0) NIL) (((X 1 O O X X O X O) 2 2) NIL)))))
    (((X 1 2 3 X X O O O) 7 -32) NIL)))
  (((X 1 2 3 X 5 O X O) 7 0)
   ((((X O 2 3 X 5 O X O) 1 0)
     ((((X O X 3 X 5 O X O) 2 0)
       ((((X O X O X 5 O X O) 3 0) NIL) (((X O X 3 X O O X O) 5 0) NIL)))
      (((X O 2 X X 5 O X O) 3 -2)
       ((((X O O X X 5 O X O) 2 0) NIL) (((X O 2 X X O O X O) 5 -2) NIL)))
      (((X O 2 3 X X O X O) 5 0)
       ((((X O O 3 X X O X O) 2 2) NIL) (((X O 2 O X X O X O) 3 0) NIL)))))
    (((X 1 O 3 X 5 O X O) 2 32)
     ((((X X O 3 X 5 O X O) 1 32) NIL)
      (((X 1 O X X 5 O X O) 3 -32)
       ((((X O O X X 5 O X O) 1 0) NIL) (((X 1 O X X O O X O) 5 -32) NIL)))
      (((X 1 O 3 X X O X O) 5 2)
       ((((X O O 3 X X O X O) 1 2) NIL) (((X 1 O O X X O X O) 3 2) NIL)))))
    (((X 1 2 O X 5 O X O) 3 32)
     ((((X X 2 O X 5 O X O) 1 32) NIL)
      (((X 1 X O X 5 O X O) 2 0)
       ((((X O X O X 5 O X O) 1 0) NIL) (((X 1 X O X O O X O) 5 4) NIL)))
      (((X 1 2 O X X O X O) 5 0)
       ((((X O 2 O X X O X O) 1 0) NIL) (((X 1 O O X X O X O) 2 2) NIL)))))
    (((X 1 2 3 X O O X O) 5 32)
     ((((X X 2 3 X O O X O) 1 32) NIL)
      (((X 1 X 3 X O O X O) 2 0)
       ((((X O X 3 X O O X O) 1 0) NIL) (((X 1 X O X O O X O) 3 4) NIL)))
      (((X 1 2 X X O O X O) 3 -32)
       ((((X O 2 X X O O X O) 1 -2) NIL) (((X 1 O X X O O X O) 2 -32) NIL)))))))))

All to conclude that:

CL-USER 9 >    (setf nodes (mapcar #'car (tree-children mx-tree)))

(((X X 2 3 X 5 O 7 O) 1 -32) ((X 1 X 3 X 5 O 7 O) 2 -32) ((X 1 2 X X 5 O 7 O) 3 -32) ((X 1 2 3 X X O 7 O) 5 -32) ((X 1 2 3 X 5 O X O) 7 0))

CL-USER 10 >    (pprint nodes)

(((X X 2 3 X 5 O 7 O) 1 -32)
 ((X 1 X 3 X 5 O 7 O) 2 -32)
 ((X 1 2 X X 5 O 7 O) 3 -32)
 ((X 1 2 3 X X O 7 O) 5 -32)
 ((X 1 2 3 X 5 O X O) 7 0))

CL-USER 11 >    (choose-mx-move mx-tree)

7

Yep, it successfully searched that whole tree to discover that any move other than 7, it's toast.

Plainly whatever toddlers are doing in their little infant brains, it's not minimax ...

Noughts and Crosses in Common Lisp

#|  This file at:

http://interweave-consulting.blogspot.co.uk/2017/01/noughts-and-crosses-in-common-lisp.html

This is the complete code in Common Lisp for implementing the game of noughts and crosses (tic-tac-toe). You should be able to select this entire post, paste it into a CL system, and compile and load.

Some examples are here.

There are three kinds of players defined: humans, random players and a minimax player which searches a game-tree to a configurable depth.

To invoke the three kinds of players use one of these function calls - see the end of the file.

(play-game 'X *initial-board* #'human #'human)

(play-game 'X *initial-board* #'rand-player #'human)

(play-game 'X *initial-board* #'mx-player-X #'human)

A game looks like this (using the random player). Warning: there may still be bugs - I have not tested the functions to death, particularly minimax.

---------

|#

;;; Noughts and Crosses
;;; Functions to explore game tree management and minimax
;;;
;;; December 29th 2016 - January 25th 2017
;

; ------------------- Datatype BOARD ------------------------------------

(defparameter *initial-board* '(0 1 2 3 4 5 6 7 8))   ; empty board

(defvar *win-score*   32)   ; the score assigned to a terminal win position
(defvar *lose-score* -32)   ; the score assigned to a terminal lose position
(defvar *draw-score*   0)   ; the score assigned to a terminal draw position

(defun print-board (b)
(let   ((b0 (nth 0 b))
         (b1 (nth 1 b))
         (b2 (nth 2 b))
         (b3 (nth 3 b))
         (b4 (nth 4 b))
         (b5 (nth 5 b))
         (b6 (nth 6 b))
         (b7 (nth 7 b))
         (b8 (nth 8 b)))
         (format t "~%")
  (format t "     ~{~a~^ | ~} ~%" (list b0 b1 b2))
  (format t "     ~{~a~^ | ~} ~%" (list b3 b4 b5))
(format t "     ~{~a~^ | ~} ~%" (list b6 b7 b8))
          ))

; This is the output of 'print-board' when applied to *arbitrary*
;
;     X | 1 | O
;     O | 4 | 5
;     X | 7 | X

; These parameters available for testing

(defparameter *top-side-win* '(X X X 3 4 5 6 7 8))
(defparameter *bot-side-win* '(0 1 2 3 4 5 X X X))
(defparameter *arbitrary*    '(X 1 O O 4 5 X 7 X))
(defparameter *end-in-draw*  '(X X O O X X X O O))   ; this is a draw position


(defun opp (m)  ; MARK -> MARK    - switches player around
  (if (equal m 'X) 'O 'X) )


(defun triple-score (m r)  ; MARK x POSITION-list -> Int
  "my good positions - opponent's good positions"
  (let ((good  (if (zerop (count (opp m) r)) (count m r) 0) )
        (bad   (if (zerop (count m r)) (count (opp m) r) 0)) )
    (- good bad)  ))

(defun heuristic-score (m B)    ; MARK x BOARD -> Nat
  "heuristic score absolute value <= around 4 or 5 "
  (let ((sum1 (triple-score m (list (nth 0 B) (nth 1 B) (nth 2 B))))
          (sum2 (triple-score m (list (nth 3 B) (nth 4 B) (nth 5 B))))
          (sum3 (triple-score m (list (nth 6 B) (nth 7 B) (nth 8 B))))
          (sum4 (triple-score m (list (nth 0 B) (nth 3 B) (nth 6 B))))
          (sum5 (triple-score m (list (nth 1 B) (nth 4 B) (nth 7 B))))
          (sum6 (triple-score m (list (nth 2 B) (nth 5 B) (nth 8 B))))
          (sum7 (triple-score m (list (nth 0 B) (nth 4 B) (nth 8 B))))
          (sum8 (triple-score m (list (nth 2 B) (nth 4 B) (nth 6 B)))) )
    (+ sum1 sum2 sum3 sum4 sum5 sum6 sum7 sum8)  ))


(defun is-win (mark B)  ; MARK x BOARD -> Bool
  "mark is X or O, B is the board"
  (let ((triple (list mark mark mark)))
    (or (equal triple (list (nth 0 B) (nth 1 B) (nth 2 B)))
          (equal triple (list (nth 3 B) (nth 4 B) (nth 5 B)))
          (equal triple (list (nth 6 B) (nth 7 B) (nth 8 B)))
          (equal triple (list (nth 0 B) (nth 3 B) (nth 6 B)))
          (equal triple (list (nth 1 B) (nth 4 B) (nth 7 B)))
          (equal triple (list (nth 2 B) (nth 5 B) (nth 8 B)))
          (equal triple (list (nth 0 B) (nth 4 B) (nth 8 B)))
          (equal triple (list (nth 2 B) (nth 4 B) (nth 6 B)))
        )))

(defun is-draw (b)  ; BOARD -> BOOL
   (null (remove 'O (remove 'X b))))


; ------------------ Datatype OXO-NODE -----------------------------
;
;  BOARD x MOVE (Nat) x SCORE (Nat)
;
;  MOVE: 9 is the non-assigned move (legal values 0-8)
;                the number is the move which got to this node.
;
;  SCORE: only applies to minimax.
;         t is the non-assigned score (assigned scores are terminal,
;         heuristic or backed up via minimax).
;

(defun mknode (board move score)
  "node is board + move (undefined=9 or 0-8) + board-score (undefined=t)"
  (list board move score))

(defparameter *initial-node*   (mknode *initial-board* 9 t))      ; empty root node

; ------------- Node projection functions -----------------------------------

(defun board (n)     ; OXO-NODE -> BOARD (1st element)
   (car n))

(defun cmove (n)  ; OXO-NODE -> Nat (2nd element)  --  Index number of current move
   (cadr n))

(defun score (n)     ;  OXO-NODE -> Nat (3rd element) -- (backed up) board rating
   (caddr n))


; ------------------- Datatype OXO-TREE --------------------------------------
;

(defun mktree (node treelist)  ; OXO-NODE x TREE-list -> TREE
  "build a tree"
  (list node treelist))

(defun tree-node (tree)
   (car tree))

(defun tree-children (tree)    ; TREE -> TREE-list
   (cadr tree))

(defun leafp (tree)    ; TREE -> bool
   (null (tree-children tree)))


; ----------- XTREE: the main function to build a game-tree to depth n -----

(defun xtree (s m n d)  ; MARK x MARK x OXO-NODE x Nat -> TREE
  "Generate game tree. Mark s is the mark the player is playing (X or O).
   Mark m to move next. Initial node n to depth d"
  (let ( (s1 (opp s))
           (m1 (opp m))
           (b   (board n))
           (i    (cmove n))  )
    (cond ((is-win s b)   (mktree (mknode b i *win-score*)  nil) )
          ((is-win s1 b)     (mktree (mknode b i *lose-score*) nil) )
          ((is-draw b)       (mktree (mknode b i *draw-score*) nil) )
          ((zerop d)          (mktree (mknode b i (heuristic-score m b)) nil))
          ( t                      (mktree n
                                                (mapcar #'(lambda (n1) (xtree s m1 n1 (1- d)))
                                                                       (mk-children m n) ) ))
          ) ) )

; -----------MK-CHILDREN: main function for building a game-tree -----------

(defun mk-children (m n)  ; MARK x OXO-NODE -> OXO-NODE-list
  "From  (board node) creates list of possible next-boards, then
   changes them into nodes.
   The 'currently unknown' board-score is t, meaning unassigned"
    (let ((possibles (poss-boards m (board n) ) ) )
         (mapcar #'(lambda (b i) (mknode b i t))                            ; create a child-node
                     (car  possibles)                                                       ; .. over list of boards
                     (cadr possibles)  )  ))                                              ; ..  and list of moves


(defun poss-boards (m b)  ; MARK x BOARD -> BOARD-list x Nat-list
  "Creat next poss boards for 'mark' m from board b, + list of poss moves"
  (let* ((remaining-moves (remove 'O (remove 'X b)))     ; example (2 5 6 8)
;         "use remaining-moves to make copies of board b, then insert m"
         (pre-boards   (mapcar #'(lambda (n) b) remaining-moves))
         (child-boards (mapcar #'(lambda (n b1) (substitute m n b1))
                                                           remaining-moves pre-boards))  )
         (list child-boards remaining-moves)  ) )

; test:   (poss-boards 'X *initial-board*)

; ----- TEST XTREE -----

; test:  (xtree 'X 'X *initial-node* 0)
; test:  (pprint (xtree 'X 'X *initial-node* 0))   ; one level deep for X
; test:  (pprint (xtree 'X 'X *initial-node* 5))   ; first wins for X

;;
;; ------------------------ TREE-BUILDING MINIMAX --------------------------
;;
;; --- This version of minimax rebuilds the tree, updated with
;; --- minimax scores and best move. (First found. Perhaps Random better?)

(defun txminimax (tree maxp)    ; TREE x Bool -> TREE
  "Traverses tree, rebuilds it using minimax with leaf-scores from xtree.
   We always start with tree root as maxplayer (maxp) = true as any
   player invoking this function always wants to win."
  (let* ( (n1       (tree-node tree))
             (minp     (not maxp))
             (ch1       (mapcar #'(lambda (tr) (txminimax tr minp)) (tree-children tree)) )
             (b1        (board n1))
             (move1  (cmove n1))
             (score1 (score n1))    )
    (cond  ((leafp tree) (mktree (mknode b1 move1 score1) ch1)  ) ; xtree leaf-score
           ( maxp   (mktree (mknode b1 move1 (tmax-child-value ch1)  ) ch1) )
           ( minp   (mktree (mknode b1 move1 (tmin-child-value ch1)  ) ch1) ) )
    ) )


(defun tmax-child-value (ch1)     ; TREE-list -> Nat
  " Finds the maximum score-value of the children of the root-node of tree"
  (apply #'max (mapcar #'(lambda (tr1) (score (tree-node tr1)))  ch1)  ) )

(defun tmin-child-value (ch1)    ; TREE-list -> Nat
  " Finds the minimum score-value of the children of the root-node of tree"
  (apply #'min (mapcar  #'(lambda (tr1) (score (tree-node tr1))) ch1)  ) )


;  test:  (pprint (txminimax (xtree 'X 'X *initial-node* 2) t) )


;; -------------------- GAME FRAMEWORK -----------------------------------
;;
;; The game is about boards, not nodes or trees. Those are purely internal
;; to tree-search players.
;;
;; The function 'play' takes functional arguments as players
;;

(defun play-game (m b p1 p2)   ; MARK x BOARD x PLAYER x PLAYER -> BOARD
  "This is the top-level function to play oxo, p1 plays first and so 'X'  "
  (cond ((is-win m b) (format t "Win for ~a~2%" m)   (print-board b))
           ((is-win (opp m) b) (format t "Win for ~a~2%" (opp m))   (print-board b))
           ((is-draw b)  (format t "It's a draw ~2%" ) (print-board b) )
           ( t    (format t "~%")
                  (let ((board1 (next-board m b p1)))
                  (play-game (opp m) board1 p2 p1)  )  ))  )

(defun next-board (m b p)  ; MARK x BOARD x PLAYER -> BOARD
  (print-board b)
  (let ((next (funcall p m b)))
    (substitute m next b) )  )

; ------------- HUMAN PLAYER --------------------------------

(defun human (m b)  ; (MARK x BOARD -> NAT) ...  aka type PLAYER
  (format t "~%")
  (format t "You play:  ~a~%" m)
  (print "Please enter an available number: ")
  (read) )

;  test:  (play-game 'X *initial-board* #'human #'human)

; ------------- RANDOM PLAYER --------------------------------

(defun rand-player (m b)   ; (MARK x BOARD -> NAT)
   (let* ((remaining-numbers (remove 'O (remove 'X b)))
          (n                 (length remaining-numbers))
          (random-index      (random n))  )
      (format t "~%")
      (format t "Rand is playing:  ~a~%" m)
      (sleep 2)
      (nth random-index remaining-numbers))  )

; test: (rand-player 'X *arbitrary*)
; test:  (play-game 'X *initial-board* #'human #'rand-player)
; test:  (play-game 'X *initial-board* #'rand-player #'human)

; ------------- MINIMAX PLAYER --------------------------------

(defvar *depth* 4)         ; minimax search depth

(defun mx-player-X (m b)  ; MARK x BOARD -> Nat    Plays X
    (mx-player 'X m b))

(defun mx-player-O (m b)  ; MARK x BOARD -> Nat    Plays O
    (mx-player 'O m b))

(defun mx-player (s m b)   ; (MARK x MARK x BOARD -> Nat)
   "Builds a game tree to *depth*, uses minimax for best move"
  (let* ((initial-node (mknode b 9 t) )
            (initial-tree (xtree s m initial-node *depth*))
            (mx-tree      (txminimax initial-tree t))  )
    (format t "~%")
    (format t "MX is playing:  ~a~2%" m)
    (if (< *depth* 4) (sleep 3) (sleep 1))
    (choose-mx-move mx-tree))  )


(defun choose-mx-move (tree)   ; TREE -> Nat
   (let* ( (n1  (tree-node tree))
              (ch1 (tree-children tree))
              (best-score  (score n1))
              (child-nodes (mapcar #'tree-node ch1))
              (move-score-pairs (mapcar 'cdr child-nodes)) )
      (first (find best-score move-score-pairs :key #'second))   ) )


; -----  TEST -----

; test:  (play-game 'X *initial-board* #'human #'mx-player-O)
; test:  (play-game 'X *initial-board* #'mx-player-X #'human)

#|
; ----------------- MINIMAX TESTING (Historical bug) --------------------

;  Bug: in b below, X plays 1 rather than 7. Easy win for O.

   (setf b '(X 1 2 3 X 5 O 7 O))     ;  -- X to play next
   (print-board b)

;     X | 1 | 2
;     3 | X | 5
;     O | 7 | O

   (setf n (mknode b 9 T))

   (setf initial-tree (xtree 'X 'X n *depth*))
   (pprint initial-tree)

   (setf mx-tree (txminimax initial-tree t))

   (setf mx-tree (txminimax (xtree 'X 'X (mknode b 9 T) *depth*) t) )

   (pprint mx-tree)
   (setf nodes (mapcar #'car (tree-children mx-tree)))
   (pprint nodes)

   (mx-player 'X 'X b)

   (choose-mx-move mx-tree)

   (play-game 'X b #'mx-player-X #'human)

; ------- test board this works correctly -----

   (setf b1 '(X 1 2 3 X O O X O))     ;  -- X to play next
   (print-board b1)
;
;     X | 1 | 2              -- X plays 1 and win. If X plays 2
;     3 | X | O              -- If O plays 3, X plays 1 and wins
;     O | X | O              -- so O will play 1 => draw
;
    (setf mx-tree1 (txminimax (xtree 'X 'X (mknode b1 9 T) *depth*) t) )
    (pprint mx-tree1)

|#

;---------------------------- END -----------------------------

Diary: Clare's health + debugging 'noughts and crosses'

A quiet day, interrupted by croaking and coughing from the bedroom.

Clare has retired to bed with a heavy cold, shivering under a duvet, a second duvet and a fleece, despite both radiators being on. I tell her she looks like something out of a mediaeval plague scene, perhaps Hieronymus Bosch?

She opens a bleary eye and croaks.

My complementary immune system is functioning just fine. Did weights yesterday - pretty much the whole programme - and today spun the exercise bike for 18 minutes and 14 seconds to burn 200 Calories. That was breakfast.

I have spent most of the day debugging my noughts and crosses program. First the function that builds the game tree didn't work: I had mentally elided the distinction between the tree-building function recursively 'switching sides' as it constructs alternating plies of crosses and noughts down the tree .. vs. the need to continually remember which side the player is actually playing so you can distinguish a win from a loss. You need two parameters, not one.

Silly that.

Now the minimax function, which traverses that tree and bubbles terminal scores to the top (alternating between propagating minimum and maximum subtree values) is playing up - but only some of the time.

Both these functions are deeply recursive and quite general to any tree-search program. At this point the bugs are subtle .. and I have given up for the day.

I hope to dump the working code here one of these days. It's harder (when you do generalised tree-search) than one might initially think.

Our forebears were peaceful and pious - as are we

The presenter is beautifully turned out. She started her career on a well-regarded archaeology show but has blossomed into every public broadcaster's dream of a popular science presenter. She's attractive, well-informed and of impeccable views.

As befits a photogenic media star, she is also a professor at one of our better universities.

The archaeologist she is interviewing is old-school. His teeth aren't right, his clothes an afterthought and his accent atrocious.

"This hill fort," she says pointing to it, "There's the ditch and wall surrounding it, and this curious set of angled avenues making the entrance diagonal, with sharp turns before you can ..."

"Yes," replies the archaeologist, "An attacking force can't directly ..."

She talks over him.

"Many scientists believe it's to allow the children to get a good view of visitors bringing interesting and exciting goods to trade."

The camera now turns to a mass grave, excavated outside the walls. Skeletons had been dumped in disarray with missing limbs and cut marks to the bones, particularly the skulls.

"This grave shows how fascinating were the burial practices of our neolithic ancestors, ..."

"It's consistent with a band of attackers being repulsed with heavy casualties and their ..."

"On the other hand, many scientists think what we're seeing here are the results of a sky burial, where the bodies of the revered dead were offered to wildlife and then the bones carefully decorated and buried. There's been a great deal of time for ground-disturbance of course."

His face set, the archaeologist turns his attention to the table, where bronze swords have been laid out. But he's too slow.

"These swords, quite corroded now, show the beautiful craftsmanship of grave goods or perhaps marks of status for the most elite leaders. You can see how much effort has gone into them as prestigious works of art ..."

At this point, the set is invaded by a young man draped in a black flag and toting a Kalashnikov. He shouts religious slogans and brings his weapon to bear.

The presenter is unfazed.

"What a beautifully-designed artefact he's carrying. Clearly it's of great religious signif ..."

The tape ends there.

How smart are software developers?

It's quite hard getting figures but based on this raw data, it appears that the average IQ of students applying for PhD programmes at good universities in computer science is around 128.

That sounds right to me. Most software development companies don't take people without good first degrees or a higher degree in a STEM subject - and that's just the pool we're talking about here.

Neural Nets written in 'logic gate assembler'

From TechCrunch: "XNOR.ai frees AI from the prison of the supercomputer"

"When someone talks about AI, or machine learning, or deep convolutional networks, what they’re really talking about  -  as is the case for so many computing concepts  -  is a lot of carefully manicured math.

At the heart of these versatile and powerful networks is a volume of calculation only achievable by the equivalent of supercomputers. More than anything else, this computational cost is what is holding back applying AI in devices of comparatively little brain: phones, embedded sensors, cameras. ...

Machine learning, Farhadi continued, tends to rely on convolutional neural networks (CNN); these involve repeatedly performing simple but extremely numerous operations on good-sized matrices of numbers. But because of the nature of the operations, many have to be performed serially rather than in parallel. ...

It’s the unfortunate reality of both training and running the machine learning systems performing all these interesting feats of AI that they feature phenomenally computationally expensive processes.

“It’s hard to scale when you need that much processing power,” Farhadi said. Even if you could fit the “beefy”  -  his preferred epithet for the GPU-packed servers and workstations to which machine learning models are restricted -  specs into a phone, it would suck the battery dry in a minute.

Meanwhile, the accepted workaround is almost comically clumsy when you think about it: You take a load of data you want to analyze, send it over the internet to a data center where the AI actually lives and computers perhaps a thousand miles away work at top speed to calculate the result, hopefully getting back to you within a second or two."

The Allen Institute for Artificial Intelligence has a new idea.

"It’s not such a problem if you don’t need that result right away, but imagine if you had to do that in order to play a game on the highest graphical settings; you want to get those video frames up ASAP, and it’s impractical (not to mention inelegant) to send them off to be resolved remotely.

But improvements to both software and hardware have made it unnecessary, and our ray-traced shadows and normal maps are applied without resorting to distant data centers.

Farhadi and his team wanted to make this possible for more sophisticated AI models. But how could they cut the time required to do billions of serial operations?

“We decided to binarize the hell out of it,” he said. By simplifying the mathematical operations to rough equivalents in binary operations, they could increase the speed and efficiency with which AI models can be run by several orders of magnitude.

Here’s why. Even the simplest arithmetic problem involves a great deal of fundamental context, because transistors don’t natively understand numbers — only on and off states. Six minus four is certainly two, but in order to arrive at that, you must define six, four, two and all the numbers in between, what minus means, how to check the work to make sure it’s correct, and so on. It requires quite a bit of logic, literally, to be able to arrive at this simple result.

But chips do have some built-in capabilities, notably a set of simple operations known as logic gates. One gate might take an input, 1 (at this scale, it’s not actually a number but a voltage), and output a 0, or vice versa. That would be a simple NOT gate, also known as an inverter. Or of two inputs, if either is a 1, it outputs a 1 — but if neither or both is a 1, it outputs a 0. That’s an XOR gate.

These simple operations are carried out at the transistor level and as such are very fast. In fact, they’re pretty much the fastest calculations a computer can do, and it happens that huge arrays of numbers can be subjected to this kind of logic at once, even on ordinary processors.

The problem is, it’s not easy to frame complex math in terms that can be resolved by logic gates alone. And it’s harder still to create an algorithm that converts mathematical operations to binary ones. But that’s exactly what the AI2 engineers did."

And they have something which works, at least in prototype.

"Farhadi showed me the fruits of their labor by opening an app on his phone and pointing it out the window. The view of the Fremont cut outside was instantly overlaid with boxes dancing over various objects: boat, car, phone, their labels read.

In a way it was underwhelming: after all, this kind of thing is what we see all the time in blog posts touting the latest in computer vision.

But those results are achieved with the benefit of supercomputers and parallelized GPUs; who knows how long it takes a state of the art algorithm to look at an image and say, “there are six boats, two cars, a phone and a bush,” as well as label their boundaries.

After all, it not only has to go over the whole scene pixel by pixel, but identify discrete objects within it and their edges, compare those to known shapes, and so on; even rudimentary object recognition is a surprisingly complex task for computer vision systems.

This prototype app, running on an everyday smartphone, was doing it 10 times a second."

I still remember programming in IBM System/360 Assembler. I later discovered that every assembly language I had ever used was itself further compiled to/interpreted by microcode.

Matryoshka.

Their paper, "XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks", shows that they're using CNN algorithms relying upon fast CPU bit-operators such as 'XNOR and bit-counting operations'. A spin-off company is productising this, XNOR.ai.

I guess the ultimate would be to forgo leveraging fast CPU/Register operations, implementing the algorithms directly onto the logic gates of a special-purpose chip, an AI accelerator.

Can't get simpler than that .. until quantum computing.

Programming is so .. arid

Helena Cronin wrote:

"Women on average have a strong preference for working with people - hence the nurses and teachers; and, compared to men, they care more about family and relationships and have broader interests and priorities—hence little appeal in becoming CEOs. Men have far more interest in "things" - hence the engineers ... "

I'm sitting here looking at a short recursive function which returns a tree whose nodes are themselves a complicated data-type (Atom-list x Nat x Nat) and I'm trying to do minimax on it. The Lispworks 'Listener' has replaced the Atom lists with hash signs (why?) and the arithmetic min function complains it's getting something weird rather than Real - and has thrown me into the debugger.

Why?

The code looks good, although there are so many good-practice projector and constructor functions, cluttering the text.

I sit in frustration, trying to visualise the unwrapping of the computation as the nested mutually-recursive functions execute their combined paths to disaster. Part of me wants to chuck this code away; another part muses that this would mean I was getting even more stupid in my old age.

I review the psychological characteristics required for successful programming.

• An ability to mentally visualise complex and abstract structures - (heavily g-loaded)
• A minute attention to detail - the smallest typos kill you
• Obsessional perseverance when nothing goes right and time-wasting options beckon.

If ever an occupation required what Simon Baron-Cohen calls the 'systemizing brain', this is it.

---

Update: (Twenty minutes later).

OK, so it was a type clash. I forgot to update a previous sub-function. Needed to add some projectors. So now I have a result.

Shame it's not the one I actually need ...

---

Some print-journalism stays with you. I regularly recall a right-on female commentator on The Times using her column to weigh in on gender equality in programming. After some shocking statistics she recounts how she asked her daughter if she had considered becoming a programmer. Her daughter looks at her as if she is mad: "Why would I want to do anything as boring as that?"

The daughter's mother is not of course a programmer. She's an opinion-piece journalist, a job where you get to meet and socialise with important people and then write lots of stuff of interest to your like-minded pals.

*Sigh*.

---

In case it isn't obvious, I know there are good female programmers. I know there are good female physicists (see here). It's just .. we're talking distributions here - you know, bell-shaped curves? - and the male-female means are noticeably different.

Strive for equality of opportunity; do not expect equality of outcome.

Scotoma after exercise

So this evening was the second time in two months that I've experienced a scotoma.

"5th November 2016. After weights exercise, a visual illusion to the right of central visual field (both eyes separately). A flickering jagged arc. This is consistent with a scotoma. Same phenomenon with either eye closed. After half an hour it began to move out and enlarge while retreating further into peripheral vision. After an hour it disappeared.

This phenomenon reappeared 19th January 2017, a couple of hours after fairly intense exercise, at 6.10 pm. Visible duration 20 minutes. Started at the centre of the visual field, a flashing-lightning V-shape with vertex at 8 o'clock. Gradually got larger until it vanished past the boundary of the visual field.

Other relevant information: I skipped lunch today as part of my weight-control programme."

After the first time I checked with Wikipedia to discover scintillating scotoma - it looks like this:

although as mentioned I'm seeing a well-defined white jagged shape, growing slowly in size.

I'm not the only one. A google search for "Scotoma after exercise" returns this.

"f you read the title and opened this post, you most likely do suffer from Scintillating Scotoma. You know, start to lose part of vision because of a flashing spot .. . The flashing zig-zag moves to outer edge of eyes, then, after 20 minute or so, goes away.

The common consensus is that is a migraine headache, without the pain.

Anyhow, since I started upping my intensity on the bike trainer workouts, I seem to be getting them after each workout. Could it be clustering since the intensity is greater? I used to get them sometimes after early season races, then as the season wore on and I got used to the intensity, they went away.

I know they're not really an issue, but, hard not go to into a mini-panic each time. "

Wikipedia talks about "cortical spreading depression" as the cause:

"a wave of electrophysiological hyperactivity followed by a wave of inhibition. Spreading depolarization (SD) describes a phenomenon characterized by the appearance of depolarization waves of the neurons and neuroglia that propagates across the gray matter at a velocity of 2–5 mm/min.

SD can be induced by hypoxic conditions and facilitates neuronal death in energy-compromised tissue. SD has also been implicated in migraine aura, where SD is assumed to ascend in well-nourished tissue and is typically benign in most of the cases, although it may increase the probability in migraine patients to develop a stroke."

I don't suffer from migraine, and the effect is purely visual although if pressed, I might admit to an ill-defined feeling of 'headiness' which persists for rather longer.

It seems benign and not a precursor to anything serious so I'm inclined to see it as no more than a warning to ease up a little on high-intensity training, which is currently sending my pulse north of 156, close to the maximum heart rate (207 - 0.7 * 66 = 161) for my age.

---

Apart from any intrinsic interest, I put this post up to compensate for the lack of engagement many of you feel for my science posts - such as the one posted earlier - fascinating though they are 😐 ..

Roy asks in the comments how I know this. Family verbal feedback and - to an extent - view counts.

The quantum-theoretic block universe

Eternalism is not hard to justify.

Yesterday I contemplated my situation and concluded: "This is real, this is now."

Today, when I recollect that scene, I'm inclined to think it was indeed real, and shows the reality of the past (which has not flickered out of existence but is .. elsewhere).

Yesterday, I also thought, "Tomorrow, I will be writing a post."

Today, here I am doing it. For yesterday's me, that shows the reality of the future.

As Frank Sinatra observed, "You can't have one without the other."

---

For greater conviction, we can appeal to special relativity. As I wrote in a piece for sciencefiction.com,

"Brian Greene in ‘The Fabric of the Cosmos’ (page 134) considers an alien in a galaxy ten billion light years away, at the edge of the visible universe. Simply by ambulating towards or away from us at 10 mph, the alien’s view of what is happening ‘right now’ on earth swings from 149 years in the past to 149 years in the future."

Still, the block universe is classical and therefore inaccurate. It's necessary to move to quantum theory where, as usual, one needs to take the red pill.

Theoretical physicist Jeremy Bernstein on 'A Quantum Past'.

"In FAPP (For All Practical Purposes) language we have a quantum mechanical system described by a wave function ψ(t), I am  only interested in the time variable.

The wave function obeys a Schrödinger equation with a Hamiltonian H. The formal solution to this equation is ψ(t) = exp(iHt)ψ(0). Throughout I am setting ћ = 1. Thus to recover Ψ(0) from ψ(t) all we have to do is to multiply by exp(-iHt).

Haven’t we then recovered the past? What is all the fuss about? The problem is that there is more to life than the wave function. There are the “observables” which represent what we really want to know about the system. These observables are described by Hermitian operators A. B. C and so on. We can expand ψ in a sum over the orthonormal eigenfunctions of any of these operators. The coefficients in the expansion are related to the probabilities that in a measurement the system will be found to have one of these eigenvalues. This is “Born’s rule” and in FAPP it must be assumed.

To find which of these eigenvalues the system actually has, we must perform a measurement. Stripped to its essence the apparatus that produces this measurement projects out from the sum of eigenfunctions one of them.

After the measurement the rest of the terms in the sum disappear. Using the term of art, the wave function “collapses”. It is at this point that we lose our capacity to reconstruct the past.

Projection operators are singular. They do not have inverses. All the king’s horses and all the king’s men cannot put the wave function back together again.

It was von Neumann in the early 1930’s who first noted that in FAPP mechanics there were two kinds of processes. There were processes that could be described by a Schrödinger equation and there were measurements which could not. He did not, as far as I know, comment on what this implied for retrodiction.

A case in point is an electron described by a spherically symmetric Schrödinger wave. If this electron strikes a detector is does so at a place - a spot. After this happens all trace of the spherically symmetric wave function vanishes.

I have certainly not made a careful search of the literature but among the founding fathers of FAPP I can come up with only two references that deal with the matter of the quantum past.

One is Heisenberg and the other is a paper by Einstein, Richard Tolman, and Boris Podolsky, “Knowledge of Past and Future in Quantum Mechanics” which they wrote in 1931 when Einstein was spending time at CalTech."

Bernstein talks about these two references, and then discusses where he thinks the problem resides, and what is to be done.

"It seems to me that any interpretation of the quantum theory that addresses this [the problem of wavefunction collapse] must have the feature that measurements are simply just another interaction like the rest.

Von Neumann’s notion that there were two classes of interactions one whose time evolution could be described by a Schrödinger equation and one of which couldn’t, has to be abandoned.

I will discuss two proposals for doing this each of which has its adherents and its detractors. On the one hand I am going to discuss what I will call “Bohmian mechanics” a term which David Bohm, who invented this approach , apparently did not like. As far as he was concerned, he was just doing quantum mechanics but in a different way. However nearly everyone else calls it Bohmian mechanics - so will I.

On the other hand, I am going to discuss the “decoherent history” interpretation which Murray Gell-Mann and Jim Hartle have done the most on. Sometimes this is called the “many worlds” interpretation, but not by them. I think that the term “many worlds” is misleading. As far as we know there is one world, the one we live in."

I'm not a fan of “Bohmian mechanics” and insofar as any quantum ontology works for me, it has to be "Many Worlds" (Sean Carroll explains why).

So I'll skip over Bernstein's description of Bohm's view of the quantum past and quote his take on “decoherent histories”.

"In the "Many Histories Interpretation" what indeed is history?

At first sight this might seem to be obvious. All we have to do is to run the chain backwards.

Yes this gives one history but there are others, possibly very many others. The reason is that if all we know is the present state vector there are many paths by which we could have arrived there depending on which initial state vector we started from. We have no way of knowing this from the data we have at hand.

Let us take an example discussed by Hartle - the Schrödinger cat (I can’t resist noting that when I spent an afternoon with Schrödinger in his apartment in Vienna there was no cat). In any event this unfortunate feline is put in a box that contains a capsule of poison gas and a sample of uranium. The capsule is triggered so that if the uranium has an alpha decay, the alpha sets off the trigger and the unfortunate feline expires.

After a time interval we open the box and happily the cat is alive. It could, according to the many history approach have arrived at this state in two ways. The initial state might have been a cat alive state or it might have been a coherent sum of a cat alive and a cat dead state. From the presence of the living cat we cannot decide.

The vision of the past given by the decoherent history interpretation and the Bohmian seems radically different. In Bohmian mechanics we could in principle follow all the cat molecules backwards in time and arrive at one and only one past.

I don’t know how you feel, but the ambiguity of the past makes me queasy. It might be entertaining to imagine that in an alternate past my grandmother who was born in a Polish stetl could have been Eleanor Roosevelt.

I readily accept that these pasts to not communicate but there seem to be too many of them from the point of view of economy. A trip to a barber wielding Occam’s razor seems warranted.

In any case when it comes to quantum pasts, as Duke Ellington taught us, “Things ain’t what they used to be.”

Perhaps Bernstein wrote this short paper just for that final joke at the end?

To summarise, if you take quantum theory seriously and you take eternalism (the block universe) seriously, then it seems that the past is as indeterminate as the future.

---

How does this relate to the 'low entropy in the past' idea used to explain the 'arrow of time'?

Since quantum theory is consistent with the second law of thermodynamics, a picture emerges of backwards branching towards (superpositions of) Big Bang variants.

My ex-colleague Roy said as much in this comment, on an earlier post devoted to the MWI. See here for more.

The Meaning of Life

In the beginning we should all be physicists. As Sean Carroll has repeatedly pointed out, the laws underlying the physics of everyday life are completely understood.

"Many people resist the implication that this theory is good enough to account for the physics underlying phenomena such as life, or consciousness. They could, in principle, be right, of course; but the only way that could happen is if our understanding of quantum field theory is completely wrong.

When deciding between “life and the brain are complicated and I don’t understand them yet, but if we work harder I think we can do it” and “I understand consciousness well enough to conclude that it can’t possibly be explained within known physics,” it’s an easy choice for me."

Carroll summarises our complete theory of the universe in one equation. As he points out, "No experiment ever done here on Earth has contradicted this model."

For the physicist, life is merely a parameter subspace in the evolution of the universal wavefunction. I'm tempted to mention cats. The physicist is professionally a psychopath. So note that the next time a famous physicist expresses an opinion on politics or public policy. They are talking outside their discipline.

---

It's not wrong to start with physics, how could it be? But we seek more enlightenment from biology. At least the subjects we study there are actually living.

The title of this post is the meaning of life. Did you see the word 'human' anywhere?

Consider the plants and animals, the germs and fungi, occupants of this planet for four billion years. Darwin gave us the answer - the meaning of life is to survive and have reproducing progeny. All those ancestral entities which didn't 'get that' were eliminated from reality.

And for most creatures, there is no more meaning than that. If they were to waste their time and energy on doing anything else, they would be outcompeted and removed from the gene pool.

---

On to sociology. It seems unbearable to a cultured person in the twenty first century that the meaning of their life is reduced to the number of child-bearing children they manage to create. This has thrown reductionist biologists into confusion.

I once read that the reason Catholic priests were celibate was some variation of the alleged 'gay uncle' phenomenon. Utterly delusional.

To state the obvious, humans are social creatures and large-scale agrarian societies rapidly outcompeted hunter-gathers. Almost all contemporary humans are the descendants of individuals who successfully adapted to living in large-scale cooperative societies.

Until the recent advent of contraception, reproductive success was strongly linked to social status. Social status in large-scale societies selects for social accomplishment: it helps to be good at something people value, and not to be a muppet.

A desire simply to breed is not really enough: your neighbours can get lethally irritated.

It's surprising how many people delude themselves that being an actor, a rock star, a politician or a top executive or even intellectual is not about getting the girl (or, if a girl, getting a better class of admirer).

What do you think?

---

Social creatures have complex life histories, no longer purely individualistic. We all recall "Haldane famously joking that he would willingly die for two brothers or eight cousins."

Those celibate Catholic priests are using prosocial psychological drives to inhibit their more primal reproductive imperatives. No society could cohere without such inhibitory mechanisms and since the ages of rape and pillage of outgroups, there has been selection for male self-control.

As ever, there is variation in the population and a celibate occupation strongly selects within that.

---

Some conclusions. The biologists are right: for humans the meaning of life is in some extended sense to have offspring. A society which fails to reproduce abolishes itself and vanishes from reality. The extended sense means that we could profitably devote our lives to aiding close kin, or even those whose social-solidarity benefits our kin (the foundation of reciprocal altruism).

We all benefit from the continuing integrity of our societies with their high carrying capacities.

It's OK to be a celibate, rule-abiding priest .. really. Even if you are professionally confused about the meaning of life.

I win my first noughts and crosses game!

Much excitement amongst regular readers here as to when I will play my first game against my AI noughts and crosses system.

Well, it just happened and I won playing X.

Here's the game-transcript.

---

CL-USER 22 >  (play-game 'X *initial-board* 'human 'rand-player)

Next to play:  X

     0 | 1 | 2
     3 | 4 | 5
     6 | 7 | 8

"Please enter an available number: " 8

     0 | 1 | 2
     3 | 4 | 5
     6 | 7 | X

--- Computer playing O now moves ---

     O | 1 | 2
     3 | 4 | 5
     6 | 7 | X


"Please enter an available number: " 6

     O | 1 | 2
     3 | 4 | 5
     X | 7 | X 


--- Computer playing O now moves ---

     O | 1 | 2
     3 | 4 | 5
     X | O | X

"Please enter an available number: " 2

     O | 1 | X
     3 | 4 | 5
     X | O | X

--- Computer playing O now moves ---

     O | 1 | X
     O | 4 | 5
     X | O | X


"Please enter an available number: " 1

     O | X | X
     O | 4 | 5
     X | O | X

--- Computer playing O now moves ---

     O | X | X
     O | 4 | O
     X | O | X


"Please enter an available number: " 4

Win for X

     O | X | X
     O | X | O
     X | O | X

Perhaps I shouldn't get too excited: here's my opponent - noting that ...

• the parameter m is the 'mark' -  X or O; 
• b is the evolving board, eg:  '(X 1 O O 4 5 X 7 X).

(defun rand-player (m b)
   (let* ((remaining-numbers (remove 'O (remove 'X b)))
          (n                 (length remaining-numbers))
          (random-index      (random n))  )
      (nth random-index remaining-numbers))  )

The considerably more difficult task of getting the tree-search system debugged I'll leave for tomorrow!

---

You may have noticed my poor fourth move. OK, I was toying with it.

---

Update Wednesday 18th January.

To Roy's comment below: yes, it's random. I used it to test the game-playing framework and user interface. It is rather spooky and apparently cunning to play against - hard to second-guess 😏.

Today I've been working on the tree-generation algorithm and minimax. Probably a session or two away from the first capable AI player.

The liberal colonisation of western elites: why?

The British Prime Minister, Theresa May, gave a defensive speech on Brexit today and was duly patronised on the talk shows by Remain liberals in their characteristic, languid upper-class drawl.

I wonder yet again why western capitalist elites seem dominated by liberals. The phenomenon is too widespread to be explained by purely national histories. From the Clintons to the Camerons to the Merkels the caste is pervasive.

I turn again to Jonathan Haidt and Moral Foundations Theory, quoting him from this previous post.

"Think of it like this: Evolution gave all human beings the same taste receptors — for sweet, sour, salt, bitter, and umami (or MSG) — but cultures then create unique cuisines, constrained by the fact that the cuisine must please those taste receptors. Moral foundations work much the same way. The six main moral taste receptors, according to MFT, are:

Care/harm: We feel compassion for those who are vulnerable or suffering.

Fairness/cheating: We constantly monitor whether people are getting what they deserve, whether things are balanced. We shun or punish cheaters.

Liberty/oppression: We resent restrictions on our choices and actions; we band together to resist bullies.

Loyalty/betrayal: We keep track of who is "us" and who is not; we enjoy tribal rituals, and we hate traitors.

Authority/subversion: We value order and hierarchy; we dislike those who undermine legitimate authority and sow chaos.

Sanctity/degradation: We have a sense that some things are elevated and pure and must be kept protected from the degradation and profanity of everyday life. (This foundation is best seen among religious conservatives, but you can find it on the left as well, particularly on issues related to environmentalism.)

"As with cuisines, societies vary a great deal in the moralities they construct out of these universal predispositions. Many traditional agricultural and herding societies rely heavily on the loyalty, authority, and sanctity  foundations to create rituals, myths, and religious institutions that bind groups together with a strong tribal consciousness.

"That can be highly effective for groups that are often attacked by neighboring rivals, but commercial societies (such as Amsterdam in the 17th century or New York City today) are far less in need of these foundations, and so make much less use of them.

Jonathan Haidt and his co-workers found that modern political tribes project differently onto these six dimensions.

Source: Wikipedia

Liberals are motivated almost entirely by the Caring dimension and Fairness, which they tend to interpret as equality of outcome. We might also observe that liberals tend to value self-control and eschew displays of physical aggression. Playing by the formal rules demands both.

Conservatives score less on Caring, stronger on Fairness which they tend to interpret as equality of opportunity, and are supportive of their own institutions via Groupishness.

Libertarians are like Mr Spock in Star Trek: cool and unemotional, detached and strongly autonomous as shown by their focus on Liberty - freedom from interference.

Modern capitalism in its full, globalist, multi-ethnic majesty is a kind of ecosystem-filter for these different moral types.

As I mentioned in the previous post about the current state of Russia, capitalism works best - as a network of anonymous economic relationships distributed over time and space - with a system of rules in place to enforce property rights and ensure transaction-integrity.

The point about rules is that they should be impersonal, not unduly biased by power and stable. In turn this requires an enforcing state which upholds associated values. These, however, can easily conflict with common psychological drives.

• Universal abstract rights can undermine particularist family, kin and ethnic interests
• Formal process requires the replacement of arbitrary force to resolve disputes
• A safety net is needed to keep the masses from toppling the elites.

In MFT terms, this prioritises Fairness and Caring, and undermines the kinds of particularism expressed in the three Groupish dimensions. In theory Libertarian Freedom might suit an idealised capitalism but in reality its disengaged state-model is just ineffective and dangerously uncaring.

If these points carry a ring of truth then it's no surprise that liberals are so strongly selected for when populating elite positions, particularly within the state apparatus and organs of elite ideology like the media and social sciences.

When Groupish, 'populist' conservatives come to power, propelled by disgruntled in-groups, liberals react with fear and loathing seeing the threat to their carefully-crafted model of atomised society composed of formally-equal individuals.

They are right to do so: as discussed in the previous post, authoritarian leaders privilege their supporters while demonising others as out-groups. This can end in tears.

But .. the tenets of liberal ideology are so tendentious, so self-serving, and often so plainly delusional and damaging to the social fabric that sometimes, something just has to be done.

I think Theresa May clearly understands this, which makes her deference to the liberal establishment besieging her so depressing.

---

Is it possible to run a free, productive, dynamic, inclusive capitalist society without its natural ideology of social atomisation, blank-slate equality and hyper-individualism?

You might want to read this.