Heroes or enemies?

The one-armed woman said, “There was a movie called Maple recently. I don’t know if you’ve seen it. At the end, an adult and a child stand in front of the grave of a Red Guard who had died during the faction civil wars. The child asks the adult, ‘Are they heroes?’ The adult says no. The child asks, ‘Are they enemies?’ The adult again says no. The child asks, ‘Then who are they?’ The adult says, ‘History.’”

From the book “The three body problem”

Advertisements

Learn about chess endgames from stockfish

Stockfish has a very well documented codebase. Someone can learn a lot about chess even by just looking at the comments. As an example, here is what stockfish does in certain end games from the perspective of the strong side. For the weak side, the opposing plan is true. As a note for the rules that follow, they may not characterize all possible positions. If not, then the position has to be evaluated by looking more closely to its specifics.

Plenty of material vs King

– Just push the lone king towards the side and keep the distance of the two kings short.

King + Knight + Bishop vs King

– Similar as above. The difference is that the right corner is the corner with the same color as the bishop.

King + Pawn vs King

– It is evaluated based on some magic tables.

King + Rook vs King + Pawn

– If stronger’s side’s King is in front of the pawn, then this is a win.
– Similarly, if the weaker’s side’s King is too far from the pawn, it is also a win for the strong side.
– The position is a draw if the pawn is advanced and protected by the opposing king.

King + Rook vs King + Bishop

– Draw.

King + Rook vs King + Knight

– Draw, unless King and Kight are too far away.

King + Queen vs King + Pawn

– This is usually a win for the side with the Queen.
– The exception is when the Pawn is on the 7th rank, protected by the King, on the Rook or Bishop files, and the strong’s side King is far away from the pawn.

King + Queen vs King + Rook

– This is a win for the stronger side.
– The strong side wants the two kings closer and the enemy King driven to the edges.

King + 2 Knights vs King

– Draw.

King + Bishop + Pawns vs King

– This is in general a win for the strong side.
– Exception is when the pawns are in the same Rook file, where the promoting square is of different color compared to the Bishop and the enemy King can arrive there in time.

King + Bishop + Pawns vs King + Pawn

– Similar as above.
– Exception is when the pawns of the strong side are on a Knight’s file, there is an enemy’s pawn on the 7th rank and the bishop cannot attack it or if there is only one pawn from the strong side in that file. Then, there is a draw as long as the weak’s side King is within two squares from the blocking pawn, on the back two ranks, and the strong side’s King is farther away.

King + Queen vs King + Rook + Pawns

The weak is the one with King + Rook + Pawns.

– It returns a draw if the pawns form a “fortress” on the third rank and they defend the rook, and the king is at most up to rank 2, and the enemy king is farther away (rank 4 or beyond).

King + Rook + Pawn vs King + Rook

– Draw if the pawn is not too far advanced (5th rank), the defending king protects the queening square, and the attacking king is away. The draw is achieved through the third-rank defense.

– Draw if the pawn is on the 6th rank, by checking from behind the enemy King.

– Draw if the pawn is on the 6th rank or higher, the defending King controls the queening square, the defending rook is on the first rank and either the tempo is on the defending’s side or the distance between the two kings is at least two squares.

– Draw if the pawn is on A7, attacking Rook on A8, defending Rook behind the pawn, and defending King on H7 or G7. Symmetrically for a pawn on H7.

– Draw if the defending king is blocking the pawn and the attacking king is too far away.

– Win if the attacking king is closer to the pawn compared to the defending king. The pawn should not be on a rook’s file, though, and it should be close to be promoted.

King + Rook + Pawn vs King + Bishop

The only rule here concerns a possible pawn on a Rook file, which under some conditions can be a draw.

King + Rook + 2 Pawns vs King + Rook + 1 Pawn

Draw if the stronger side has no passed pawns and the defending king is actively placed.

King + Pawns vs King

Draw only if the pawns are on a Rook’s file and the defending king is in front of them.

King + Bishop + Pawn vs King + Bishop

– Draw if the defending King is in front of the Pawn and he can’t be kicked out.

– Draw if bishops are of opposite color and one of the following is true: (a) pawn is on rank 5 or earlier (b) the defending king is in front of the pawn or (c) the defending bishop attacks one square in front of the pawn and it is at least three squares farther away from the pawn.

King + Bishop + 2 Pawns vs King + Bishop

To have a forced draw, we need opposite color bishops. Then:

– Draw if the pawns are on the same file and the defending king is in front of the pawns.
– Draw if the pawns are on adjacents files, the defending king is in front of them, and the defending bishop controls the squares in front of them.

King + Bishop + Pawn vs King + Knight

– Draw easily if the defending King is in front of the Pawn, in a square that the attacking Bishop cannot go.

King + Knight + Pawn vs King

– Draw if a Rook pawn is on the 7th rank and the defending King is blocking it.

King + Knight + Pawn vs King + Bishop

– Win only if the Knight can prevent the Bishop from taking the Pawn.

King + Pawn vs King + Pawn

– Draw chances if the weaker side could achieve a draw even without its pawn.
– Exception is when the strong’s side Pawn is too advanced and the pawn is not on the Rook’s rank. Then, if the weaker side could have drawn even without its pawn, then it could have winning chances with its pawn.

Married functions

On Gödel Escher Bach, on page 137 there are two “married” functions defined:

for n >= 1:
F(n) = n – M(F(n – 1))
M(n) = n – F(M(n – 1))

for n = 0:
F(0) = 1, M(0) = 0

I wondered whether it is easy to define three function that increase their value every time n is increased by three, using only addition, subtracting and recursive calls to the previous value of the functions. It turns out it is not too hard to find some.

for n >= 1
F(n) = n – M(n – 1) – N(F(n – 1) + M(n – 1) + N(n – 1) – 2)
M(n) = F(n – 1)
N(n) = M(n – 1)

for n = 0:
F(0) = 1, M(0) = 0, N(0) = 0

Reverse recursively single linked list

There are two main ways to reverse a linked list: iteratively and recursively. I find the recursive solution easier to understand and cleaner. Unfortunately, I didn’t find any examples with tail recursion in the top results that I looked at, so I list my approach.

If someone wants to try their own approach, they can try on:
https://leetcode.com/problems/reverse-linked-list/

On marginalization

“I can’t bear to hear a human being spoken of with contempt just because of his group identification-even by other human beings. It’s these respectable people here who create those hooligans out there.”

The quote is from Dors from “Prelude to foundation” by Isaac Asimov.

“These respectable people here” refers to the snobbish class of people who made these comments. The “hooligans out there” refers to the marginalized part of the community who has developed violent behaviour.

Russell’s paradox

Let A be any set. We define B such as:
B = \{x \in A : x \notin x\}

Can it be that B \in A? No.

Proof by contradiction.

Assume B \in A.

  • If B \in B then by the definition of B:
    B \notin B. Contradiction.
  • If B \notin B then by the definition of B:
    B \in A \text{ and } B \notin B \implies B \in B. Contradiction.

Therefore B \notin A.

Credits for the succinct proof.

Some notes on Decision Theory

Once upon a time, I took a course in Decision Theory at ETH. Here are some notes:

normative theory vs descriptive theory (maths vs psychology)

prospect theory

options vs choices

money pump

bond vs shares

Main notions:

  1. Slide
    1. Normative: Perfect rationality, optimality, payoff maximality
    2. Descriptive: How real people think and make decisions.
      1. bias: persistent and systematic deviation from rationality
    3. Prescriptive: How can we help people to make better decisions. How can we structure the choice environment to minimize decision errors and biases.
    4. People use limited heuristics in making decisions
    5. Decision maker
      1. individual, couple, family, firm, country
      2. any monolithic cognitive agent
    6. Goals, preferences, wants, desires
    7. options, alternatives, courses of action
    8. beliefs
    9. Decision under
      1. certainty
        1. all options and outcomes are completely known to the DM (military diet, ups example)
      2. risk
        1. When all the choices and options are known but there are well defined stochastic nodes (gambling, insurance, investing)
      3. uncertainty
        1. options are not well defined, or probabilities are not defined (or both) (examples most of life)
    10. Preferences
      1. Revealed, Complete, Transitive, Independent, Stable
    11. People often satisfice instead of optimize
    12. People guess, estimate and try to do “well enough’’ rather than optimally.
    13. Rationality is bounded in two ways.
      1. Information from the environment
      2. cognitive capacity
    14. Sometimes close enough is fine, sometimes not
    15. Cognitive illusions: Monty hall problem
    16. Limitations in attention and memory. There are tools which compensate for that.
    17. Multi Attribute Evaluation (MAUT)
      1. identify options
      2. define goals
      3. quantify subjective evaluations
      4. weight and scale different evaluations so they can be aggregated meaningfully.
      5. make reasonable and justifiable decisions
    18. Problem, Objectives, Alternatives, Consequences, Tradeoffs (PrOACT)
    19. Comparative, multiple stakeholders (probably not equally important), multiple goals (maybe not equally important), multiple choices with multiple attibutes, judgements are necessary, quantify!
      1. Identify the decision maker
      2. Identify the alternatives
      3. the relevant attributes
      4. assign values to the attributes of each alternatives
      5. determine a weight for each attribute
      6. for each alternative, compute a weighted mean
      7. make a provisional decision
      8. get feedback and run a sensitivity analysis
    20. compensatory vs noncompensatory
      1. sometimes some alternatives are not acceptable (minimum requirements)
    21. minor changes may cause a change in the resulting decision
    22. “fair’’ method and easy to develop political support
    23. analytic hierarchy process: binary comparison of pairs of attributes in terms of their importance and then assign a weight (how much better is on alternative compared to the other)
    24. built in check for transitivity and consistency
    25. a well defined process to turn subjective judgements into more objective ratings
  2. Secretary problem
    1. What makes a good decision (good outcome or good reasons?)
    2. expected value
    3. probability (classical, frequency, subjective)
    4. it can be hard for people to reason about probabilities correctly (monty hall, other pitfalls)
    5. birthday problem
    6. bayes rule
    7. st petersburg gamble
    8. Moral worth: Bernoulli: the worth of something is not the same as its value → Definition of utility (utility = value^a)
    9. Expected utility does not work always
    10. Allais gambles. The result is a contradiction to EUT.
    11. Feelings about risk: People will accept 1000 times greater risks if they are their own volition, rather than involuntary
    12. O.J. SImpson example
    13. People are generally risk averse, but to varying degrees
    14. EVT defines rationality if the goal of the DM is to maximize value in the long run
    15. EUT defines rationality if the goal of the DM is to maximize utility (moral worth) in the long run
    16. Risk seeking in the domain of losses, risk averse in the domain of gains
    17. Decision framing
    18. Money trump
  3. Sequential investment problem
    1. Persistent cognitive noise
    2. systematic departures from EUT – biases
    3. Friedman-Savage utility function
    4. Prospect theory
      1. descriptive account of decision theory under risk
      2. aims to account for systematic deviations from eut and evt
      3. Coding — outcomes relative to the current state in terms of gains and losses
      4. combination — joining similar prospects
      5. segregation — isolation of sure things
      6. cancellation — discarding shared components
      7. simplification — rounding
      8. elimination of dominated options
    5. probability weighting function — the estimation that people do on probabilities (magnification of small values in the expense of larger values)
    6. 4 fold pattern of risk preferences
      1. risk seeking over low p gains — lotteries
      2. risk averse over low p losses — insurance
      3. risk averse over high p losses — certainty effect
      4. risk seeking over high p losses — end of the day effect
    7. certainty effect
      1. insurance which does not pay with a very small probability
    8. end of the day effect
      1. people make large bets on the last day to “break even’’
    9. Shortcomings
      1. average choices on average
      2. not for every one
      3. not even for someone over the domain of time
      4. no insight — just better predictions
      5. does not scale. (portfolio example, mulistage risky decisions)
    10. Dynamic decision contexts are defined by:
      1. sequential choices are made and they are interspersed with updated information about the environment
      2. the decision environment changes over time (depending on the choices of DM)
    11. normative approaches
      1. maximize expected payoff
      2. dynamic programming
    12. descriptive approaches
      1. case studies
      2. experimental methods (behavioral laboratories)
      3. human behaviour is compared to the normative approach
      4. identification of systematic departures from optimality — existent cognitive mechanisms can be accounted for
      5. ⇒ people predictably irrational (underlying assumption)
    13. optimal stopping
      1. example: secretary problem
      2. target: select a maximum value
      3. full information games
        1. perfectly known distribution
        2. draw a number from [0,20] — given the relative order of the number that you encountered so far but not the number
      4. partial information
        1. known distribution but not its parameters
        2. german tank problem
      5. no information
        1. iid random variables with unknown distribution
        2. secretary problem
        3. Sometimes called the Sultan’s Dowry Problem, the Marriage Problem, or the Fussy Suitor Problem
        4. optimal decision policy — threshold (e^{-1})
        5. generalized secretary problem
        6. persistent bias for stopping too soon
        7. probability distortion and not risk aversion is the (assumed) answer
      6. Other dynamic decision problem
        1. sell a good over a time interval where offers in a specific range arrive with a probability
    14. Kelly criterion
      1. always bet the same proportion (2p – 1)
      2. maximizes the expected geometric mean
      3. poor criterion in prediction decision makers behavior
      4. people have strong urge to adjust their investments
      5. evidence of learning to adjust less over rounds
      6. if we charge people when they adjust, we help them
    15. sequential investment problem
      1. optimal policy: bet max or not according to whether we are “above or below the expectation’’
    1. Heuristics as rule of thumb.
    2. gambler’s fallacy (law of small numbers)
    3. hot hand fallacy (law of small numbers)
    4. stars
    5. availability heuristics (how easy it is to recall a piece of information)
    6. anchoring and adjustment
      1. factorial where presented the larger number first or last
      2. use of early values to predict
    7. framing effect (the influence of questions)
    8. confirmation bias
    9. are people really irrational — heuristics evolved for some reason. Carefully designed corner case are examined.
    1. public goods game
      1. selfish players take no interest
      2. social optimal is far off
      3. many people are pro-social
      4. design vector according to the answers
    2. overconfidence quiz
      1. attentional
        1. selective memory/information search: confirmation bias
        2. selective encoding: excuses/rationalizations
        3. selective encoding : rewarded events are remembered better
      2. motivational
        1. need to appear competent and confident to tothers and oneself. confidence and optimism help to get things done.
    1. bordeaux and regression
    2. wisdom of crowds
    3. risky decision theory and gambling
    4. rush of winning
    5. highly reinforcing