Go go gallimaufry

(markus) ~/projects/osbridge/gallimaufry > dict gallimaufry |
>                                          grep -vE '1913|[ ]{13}'
2 definitions found

From The Collaborative International Dictionary of English v.0.48 [gcide]:

  Gallimaufry \Gal`li*mau"fry\, n.; pl. {Gallimaufries}. [F.
     galimafr['e]e a sort of ragout or mixed hash of different
     meats.]

     1. A hash of various kinds of meats, a ragout.
     2. Any absurd medley; a hotchpotch.

From WordNet (r) 3.0 (2006) [wn]:

  gallimaufry
      n 1: a motley assortment of things [syn: {odds and ends},
           {oddments}, {melange}, {farrago}, {ragbag}, {mishmash},
           {mingle-mangle}, {hodgepodge}, {hotchpotch}, {gallimaufry},
           {omnium-gatherum}]

This is going to get a little confusing

© 2012 Pratibha Varshney http://qlikd.com/

Is everyone confused?

Then let’s dive in.

Peace on Earth, doing it wrong

Of course, we would never be that stupid

Project Euler problem #1

An Allegory in n Algorithms

Algorithm 1

for ((t=23,t<1000000,t++)); do
    curl --data="guess=$t" \
        http://projecteuler.net/problem=1
    done

Algorithm 1b

for ((t=23,t<1000000,t++)); do
    for ((c=10000,t<=99999,c++)); do
        curl --data="guess=$t&confirm=$c" \
            http://projecteuler.net/problem=1
        end
    done

Algorithm 1c

for ((t=23,t<1000000,t++)); do
    for ((c=10000,t<=99999,c++)); do
        curl --data="guess=$t&confirm=$c" \
            http://projecteuler.net/problem=1
        sleep 5
        end
    done

Algorithm 2

1 to 999 filter { x => x % 3 == 0 || x % 5 == 0 } sum

Algorithm 3

a = 3
b = 5
t = 0
while a < 1000 or b < 1000:
    if a < b:
        t = t+a
        a = a + 3
    elif b < a:
        t = t+b
        b = b + 5
    else:
        t = t+a
        a = a + 3
        b = b + 5
print t

Algorithm 4

You meet a person who can do it in their head…

Algorithm 5

• We know that the sum < 10 is 23, so to 15 it’s 23+10+12+15

66*60 + 15*7*65*66/2 + 4*990 + 23

So where does that leave us?

The rules of Go

(with possible minor errors or oversimplifications)

The language “Brainfuck”

(with possible minor errors or oversimplifications)

• A is an array of 30,000 bytes.
• I is an integer.
• > means I += 1
• < means I -= 1
• + means A[I] += 1
• - means A[I] -= 1
• . means write_byte A[I]
• , means A[I] = read_byte
• [ means jump ahead past the matching ] if A[I] == 0
• ] means jump back to the matching [

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

 
+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

(Source: http://xkcd.com/365 )

Digression Concerning the Two Brief Formal Systems

We’re that stupid

The real goal of AI

“AI is what computers can’t do yet”

The ornithopter objection

The question of whether a computer can think is no more interesting than the question of whether a submarine can swim. — Edsger Dijkstra

AKA the ornithopter objection

Are we likely to fall into the same trap?

More than birds & feathers

• Birds have lots of features

More a trove of hints than an objection

“Bumble bees can’t fly” — Scientists, according to legend

So are we committing “the ornithopter error”?

© Susan Borgas

So are we committing “the ornithopter error”?

© http://en.wikipedia.org/wiki/User:Mitchipr

This license logo is either public domain or © Aurelio A. Heckert <aurium@gmail.com> but is® FSF; to watch people at their finest see: http://commons.wikimedia.org/wiki/File:Heckert_GNU_white.svg http://commons.wikimedia.org/wiki/File:License_icon-fdl.svg

The kludge objection

http://www.theotherpages.org/spy/spy041.jpg

Progress in the computer industry is driven by

feature size

…

We can now fit ~10,000 transistors in the space occupied by one in 1970.

Progress in the computer industry is driven by

feature size
speed

http://www.singularity.com

Progress in the computer industry is driven by

feature size speed throughput

http://csgillespie.wordpress.com/2011/01/25/cpu-and-gpu-trends-over-time/

Progress in the computer industry is driven by

feature size
speed
throughput
power/heat disipation

…the cooling bill alone at Lawrence Livermore National Laboratory (LLNL) is $6M/year and given that for every watt (W) of power consumed by an HPC system at LLNL, 0.7 W of cooling is needed to dissipate the power; the annual cost to both power and cool HPC systems at LLNL amounts to a total of $14.6M per year…

— Wu-chun Feng, Los Alamos National Laboratory

Commonplace assertion: “AI programs can beat humans at chess, and are close to beating them at go.”

© UC Regents Davis

© 2012 Tangient LLC

“XML is like violence; if it doesn’t solve your problem you aren’t using enough of it.”

As natural selection acts only by the accumulation of slight modifications of structure or instinct, each profitable to the individual under its conditions of life, it may reasonably be asked, how a long and graduated succession of modified architectural instincts, all tending towards the present perfect plan of construction, could have profited the progenitors of the hive-bee?

So what modules might there be?

• a face recognition module
• a spatial relations module
• a rigid objects mechanics module
• a tool-use module
• a fear module
• a social-exchange module
• an emotion-perception module
• a kin oriented motivation module
• an effort allocation and recalibration module
• a child care module
• a social inference module
• a friendship module
• a semantic-inference module
• a grammar acquisition module
• a communication-pragmatics module
• a theory of mind module
• …and so on!

— Mithen 1996

Can we probe for the existence of such modules?

Wason selection task

You are shown a set of four cards placed on a table, each of which has a number on one side and a solid color on the other. The visible faces of the cards show 3, 8, red and blue. Which card(s) must you turn over in order to test the truth of the proposition that cards with an even number on one face are red on the other side?

Wason selection task

You are a chaperon at a student social and see four students. Two are holding glasses and you know that one of them is 19, and the other is 25; the third student has a can of beer and the fourth a can of coke. Which student(s) do you need to check to enforce the rule that no one under 25 may drink alcohol?

What is the smallest integer I such that

3*sin(I)+1.5^I > 0 > 4*cos(I)-I

for all x = I + R, R >= 0, we have

3*sin(x)+1.5^x > 4*cos(x)-x

What’s the left-most berry that you can get at?

(Produced with sage)

Add to 15, reprise

Digression Concerning the Two Small Games

What we got from chess & related games

• minmax, alpha/beta, planning w. good heuristics
• tree pruning
• frame problem(s) generalization & clarity (but not a good solution)
  • What is frame problem
  • Three problems: 1st order logic, general planning (), perception/learning (cf. perception is cognition)
  • Tie back to LAD & to list of bird features vs. flight & how many true statements about birds we didn’t consider
• Blackboard model / GA for experts

Why these fail for go

• No good evaluation function
  • Renormalization needed?
    • Not insoluble, e.g. physics &
  • gestalt & Non-monotonic
  • Based on what isn’t there (star defined by blobs)
• Long term consequences / frame problem writ large
• Highly branching, bushy tree

Avenues to explore

• Giveaway go
• Small boards, generalize up
  • Conventional wisdom: “It doesn’t generalize (esp even/odd)”
  • Clearly not true — humans do it, don’t see as different games
• Predict interesting areas (eye tracking)
  • Model w. finite state machine

Procedural Learning with GAs (digression)

• The necessary properties of a genotype → phenotype mapping; why there are no wheeled creatures

• Asking these sorts of questions can teach you a lot about internal coding.

• Example: hamming distance between ASCII codes vs. phonemes (b/v, s/z, d/j, etc.)

• Math-function space.