Guessing What Comes Next

// internal/lang/guess.go
func Count(ids []int, size int) (*Chain, error) {
	if size < 1 {
		return nil, fmt.Errorf("lang: a chain wants a vocabulary of at least 1, not %d", size)
	}
	tally := make(map[int]map[int]int)
	for i, id := range ids {
		if id < 0 || id >= size {
			return nil, fmt.Errorf("lang: token %d of %d is %d, and the vocabulary holds %d", i+1, len(ids), id, size)
		}
		if i+1 == len(ids) {
			break
		}
		if tally[id] == nil {
			tally[id] = make(map[int]int)
		}
		tally[id][ids[i+1]]++
	}

The rest of the function turns each inner map into a slice sorted commonest first, with ties broken by the lower token number, which is the same rule the merge counting uses and is there for the same reason. A Go map hands its keys back in a different order on every run. A row whose order came out of the map would be a different row on Tuesday, and a draw made against it would be unreproducible for a reason that has nothing to do with the seed. Sorting the row once, at counting time, is what makes everything after it a fixed object.

$ go run ./cmd/guess -mode counts
guess: which token followed which across the chronicle, a table of 256 merges

  the corpus and the table it is cut with
    chronicle entries                            91
    bytes of text                              7123
    vocabulary                                  512
    tokens the whole corpus encodes to         1419

  the counting
    adjacent pairs walked                      1418
    tokens anything was ever seen after         289
    distinct continuations among them          1168
    rows with nothing to choose between          73
    rows a temperature cannot change            215
    the widest row                               25

  the 8 widest rows
    token  width  total  stands for
       53     25     25  "5"
       51     24     24  "3"
       56     22     22  "8"
       57     22     22  "9"
       55     20     20  "7"
       50     19     19  "2"
       48     18     18  "0"
       32     17     17  " "

  the model is 1168 numbers

Eleven hundred and sixty-eight numbers. That is the entire model, and it is the figure to sit with before anything else on this page happens, because every claim made later about what such a thing can and cannot know has to be true of a tally this small. Of the 512 tokens in the vocabulary, only 289 were ever followed by anything at all. Seventy-three of those 289 have exactly one continuation, so whatever setting anybody picks they have nothing to choose between. Another line in that block will not mean much until the next section and is measured here because it belongs with the others: 215 of the 289 rows hold nothing but equal counts, and a row of equal counts is a row no setting on this page can move. Three quarters of this model is already decided. And the widest rows in the table are all single digits: token 53 is the character 5, and twenty-five different tokens were seen after it in seven thousand bytes.

// internal/lang/guess.go
// Row is the continuations of one token, commonest first. A token the
// corpus never followed with anything has an empty row, which is not
// an error: it is a token that only ever ended a line.
func (c *Chain) Row(from int) ([]Step, error) {
	if from < 0 || from >= c.size {
		return nil, fmt.Errorf("lang: no token %d in a chain over a vocabulary of %d", from, c.size)
	}
	return c.rows[from], nil
}

$ go run ./cmd/guess -mode row
guess: one token's row of counts, and the same row as shares, a table of 256 merges, temperature 1.00

  the token the row belongs to
    token 10, 1 byte, "\n"

  what followed it, how often, and what that is as a share
       to  count   share  running  stands for
      328     11  0.1222   0.1222  "year 1"
      329     11  0.1222   0.2444  "year 2"
      330     11  0.1222   0.3667  "year 3"
      331     11  0.1222   0.4889  "year 4"
      332     11  0.1222   0.6111  "year 5"
      333     11  0.1222   0.7333  "year 6"
      334     11  0.1222   0.8556  "year 7"
      269      5  0.0556   0.9111  "The "
      303      3  0.0333   0.9444  "year "
       80      2  0.0222   0.9667  "P"
       87      2  0.0222   0.9889  "W"
       65      1  0.0111   1.0000  "A"

  continuations it has                         12
  times the token was followed at all          90
  the shares add to                        1.0000

That block is the sentence at the top of the page, printed. It is not an answer to anything. It is twelve options with a number against each, and the numbers add to one. Ask this model how a chronicle entry begins and the honest report of what it holds is the whole column, and any single token you pull out of it is a decision somebody else made.

Read the counts and the corpus is visible in them. The chronicle is an append-only log and its entries are written in two registers: eleven founding rows in an operator's prose and eighty annual rows in the terse annalistic form the yearly count uses. Seven of the twelve options are the tokens year 1 through year 7, each occurring eleven times, because eighty years numbered 1 to 80 give ten entries starting with each of those and one more from the single-digit year itself. Then The five times and a capital letter here and there, which is ten of the eleven founding rows. The total is 90 and not 91 for two reasons that come to one line: the last line ending in the file is followed by nothing at all, and the first entry in the file has no line ending in front of it, so the founding row missing from that column is the one the document opens with.

// internal/lang/guess.go
// Zero is refused here rather than handled. Dividing by it is not a
// temperature and the limit it stands for is a different operation,
// which Draw does under its own name.
func (c *Chain) Shares(from int, temp float64) ([]float64, error) {
	if temp <= 0 {
		return nil, fmt.Errorf("lang: a temperature divides every score, so it has to be above zero, not %g", temp)
	}
	row, err := c.Row(from)
	if err != nil {
		return nil, err
	}
	if len(row) == 0 {
		return nil, nil
	}
	scores := make([]float64, len(row))
	for i, s := range row {
		scores[i] = math.Log(float64(s.N)) / temp
	}
	return Softmax(scores), nil
}

$ go run ./cmd/guess -mode dial -from 311
guess: one row of counts, a table of 256 merges, at temperatures 5.00,1.00,0.30 and at the likeliest token every time

  the token the row belongs to
    token 311, " born and 15"

  the same counts as shares, at each temperature
       to  count  T=5.00  T=1.00  T=0.30  stands for
       55      2  0.2231  0.3333  0.7159  "7"
       53      1  0.1942  0.1667  0.0710  "5"
      417      1  0.1942  0.1667  0.0710  "27 gone"
      476      1  0.1942  0.1667  0.0710  "10 gone"
      493      1  0.1942  0.1667  0.0710  "67 gone"

  the largest share in the row
    T=5.00                                 0.2231
    T=1.00                                 0.3333
    T=0.30                                 0.7159
    the likeliest token every time                     1.0000

Token 311 stands for twelve bytes reading born and 15, which is the model standing halfway through a number in the middle of a yearly entry with five ways to finish it. One of them was seen twice and four were seen once each. At temperature 1 the shares are those counts and nothing else: a third and four sixths. Turn the dial down to 0.30 and the one that was seen twice takes 0.7159 of the row while the four others share what is left. Turn it up to 5.00 and the five options converge toward being equally likely, with the commonest holding 0.2231 against 0.1942 for each of the rest. The counts have not moved. Nothing has been counted again. One division changed how hard the row leans on what it knows.

// internal/lang/guess.go
func (c *Chain) Draw(r *rand.Rand, from int, temp float64) (int, float64, error) {
	u := r.Float64()
	row, err := c.Row(from)
	if err != nil {
		return 0, u, err
	}
	if len(row) == 0 {
		return 0, u, fmt.Errorf("lang: nothing ever followed token %d", from)
	}
	if temp == 0 {
		return row[0].To, u, nil
	}
	share, err := c.Shares(from, temp)
	if err != nil {
		return 0, u, err
	}
	run := 0.0
	for i, p := range share {
		run += p
		if u < run {
			return row[i].To, u, nil
		}
	}
	return row[len(row)-1].To, u, nil
}

$ go run ./cmd/guess -mode draw -from 311
guess: one number off the stream, and the token it lands on, a table of 256 merges, seed 83 on stream 23, temperature 1.00

  the row, laid end to end from 0 to 1
       to  share   from      to  stands for
       55 0.3333 0.0000  0.3333  "7"
       53 0.1667 0.3333  0.5000  "5"
      417 0.1667 0.5000  0.6667  "27 gone"
      476 0.1667 0.6667  0.8333  "10 gone"
      493 0.1667 0.8333  1.0000  "67 gone"

  the first number off the stream        0.6338
  the segment it falls in                     3
  the token that segment belongs to         417   "27 gone"

  20 draws from the same row, from the same seed
       to  drawn  expected  stands for
       55      7      6.67  "7"
       53      3      3.33  "5"
      417      4      3.33  "27 gone"
      476      5      3.33  "10 gone"
      493      1      3.33  "67 gone"

The picking is a running total and a comparison. Lay the shares end to end from 0 to 1 so each option owns a stretch of the line as wide as its share, take a number between 0 and 1, and see whose stretch it fell in. The first number this stream ever produces is 0.6338, which falls between 0.5000 and 0.6667, so the answer is token 417 and the model has finished the number as 1527 gone. Nothing in that decision consulted what the tokens mean, and nothing in it could have. A share and a stretch of a line are the same object measured two ways.

Twenty draws off the same seed give 7, 3, 4, 5 and 1 against expectations of 6.67, 3.33, 3.33, 3.33 and 3.33. Close, and not equal, and it would be a mistake to want them equal: twenty draws from a five-way split are twenty draws, and a run that came out exactly on the expectation every time would be a run that was not drawing.

// internal/lang/guess.go
func (c *Chain) Write(r *rand.Rand, from, stop, limit int, temp float64) ([]int, bool, error) {
	var out []int
	at := from
	for len(out) < limit {
		next, _, err := c.Draw(r, at, temp)
		if err != nil {
			return out, false, err
		}
		if next == stop {
			return out, true, nil
		}
		out = append(out, next)
		at = next
	}
	return out, false, nil
}

$ go run ./cmd/guess -mode write
guess: 10 entries out of the counting table, a table of 256 merges, seed 83 on stream 23, temperature 1.00

  every line below is the table's output. Nothing in the valley wrote any of it.

   1  year 6: 12 hobbs standing in The Hollow, 62 born and 1753 gone
   2  year 126 gone
   3  year 45: 238 hobbs standing in The Hollow, 1912 born and 1732 gone
   4  year 372 born and 166: 240 hobbs standing in The Hollow, 191 hobbs standing in The Hollow, 1643 hobbs standing in The Hollow, 205 gone
   5  Plast now whit is filt of what ce of them is agak afoulacksaft ground. I ks. Anything here ten Pending. I have skn it, and not one ppria named nothing stands mades it bread there is griced going tomes ho I have soes this is The what igh it.
   6  year 605 born and 168391 gone
   7  year 683 gone
   8  year 531 born and 1744 gone
   9  year 209 born and 1684 gone
  10  year 31: 237 hobbs standing in The Hollow, 1771 hobbs standing in The Hollow, 45 born and 9 born and 9: 238 hobbs standing in The Hollow, 173: 238 hobbs standing in The Hollow, 169: 239 hobbs standing in The Hollow, 166727 gone

  entries that stopped on the entry break     10 of 10
  the rest ran to the limit of 200 tokens, and are marked +

Line 1 is the thing this chapter exists to show you. It is a chronicle entry. It has the year, the count standing, the ground's name, the births and the deaths, in the order the world writes them, with the punctuation in the right places and no word out of register. It is also not something that happened. In the world this table counted, year 6 finished with 338 born and 355 gone, and 1,753 dead against 62 born is not a year, it is two unrelated years' figures ending up next to each other because a token that ends one number is a perfectly ordinary token to follow with a token that begins another.

The header line above the block is printed by the bench and it is there on purpose. Every one of those ten lines is the output of a counting table, shown as the output of a counting table. Nothing in the valley wrote any of it, nothing in the valley has been told about it, and the chronicle those counts came off is untouched: it is an append-only log, it gained nothing today, and the ninety-one entries in it are the ninety-one entries it had this morning.

// cmd/guess/show.go
// annual is the sentence this valley writes at the end of every year,
// worked out from the chronicle rather than typed in: the digit runs
// of a real entry become holes and everything between them stays put.
// Four holes in this order: the year, the count standing, the number
// born and the number gone.
func annual(lines []exemplars.Line) (*regexp.Regexp, string) {
	var from string
	for _, l := range lines {
		if l.Kind == "count" {
			from = l.Text
			break
		}
	}

$ go run ./cmd/guess -mode check
guess: 200 entries, held against the chronicle, a table of 256 merges, seed 83 on stream 23, temperature 1.00

  the sentence this valley writes every year, taken off the chronicle
    year N: N hobbs standing in The Hollow, N born and N gone
    entries that match it                      80 of 91

  the arithmetic every one of those entries keeps
    standing = founded + born - gone
    founded, worked out from the first of them    29
    entries it holds for                       80 of 80

  now the same two tests on what the table wrote
  the first 8 of its entries that came out as exactly that sentence
      n  in the chronicle  the arithmetic  the entry
      1  no                no              year 6: 12 hobbs standing in The Hollow, 62 born and 1753 gone
      3  no                no              year 45: 238 hobbs standing in The Hollow, 1912 born and 1732 gone
     13  no                no              year 61: 237 hobbs standing in The Hollow, 1904 born and 1655 gone
     20  no                no              year 58: 234 hobbs standing in The Hollow, 188 born and 1626 gone
     26  no                no              year 239: 239 hobbs standing in The Hollow, 1927 born and 1427 gone
     34  no                no              year 33: 238 hobbs standing in The Hollow, 1784 born and 552 gone
     35  no                no              year 49: 235 hobbs standing in The Hollow, 18942 born and 1544 gone
     50  no                yes             year 8: 238 hobbs standing in The Hollow, 1962 born and 1753 gone

  entries written                             200
  of those, entries the chronicle holds          0
  of those, exactly the yearly sentence         22
  and of those 22, the arithmetic works           3

The middle block is the part that makes the rest of it a test and not an opinion. Every yearly entry the world has ever written keeps one identity: the count standing is the founding population plus everything born minus everything gone. The bench does not know that number; it works out the 29 from the first annual line and then checks it against all eighty, and gets eighty. So there is a rule the real history obeys without exception, and it costs three subtractions to apply to anything else.

$ go test ./internal/lang/ -run 'SharesAtOneAreTheCountsThemselves|ATemperatureRaisesEveryCountToOneOverIt|EverySharesRowAddsToOne|ADrawCostsOneNumberAtEveryTemperature|TheSameSeedWritesTheSameTokens|TheLikeliestTokenEveryTimeEndsInALoop|ACountedPairIsAnAdjacencyAndNothingElse|AChainRefusesWhatItCannotHaveCounted|ATemperatureOfZeroIsNotATemperature' -v
=== RUN   TestSharesAtOneAreTheCountsThemselves
    guess_test.go:52: 40 rows, every share equal to its own count over the row's total
--- PASS: TestSharesAtOneAreTheCountsThemselves (0.00s)
=== RUN   TestATemperatureRaisesEveryCountToOneOverIt
--- PASS: TestATemperatureRaisesEveryCountToOneOverIt (0.00s)
=== RUN   TestEverySharesRowAddsToOne
--- PASS: TestEverySharesRowAddsToOne (0.00s)
=== RUN   TestADrawCostsOneNumberAtEveryTemperature
    guess_test.go:143: 200 draws at four temperatures, and the generator ends in one state
--- PASS: TestADrawCostsOneNumberAtEveryTemperature (0.00s)
=== RUN   TestTheSameSeedWritesTheSameTokens
--- PASS: TestTheSameSeedWritesTheSameTokens (0.00s)
=== RUN   TestTheLikeliestTokenEveryTimeEndsInALoop
    guess_test.go:211: 40 starting tokens, 40 of them walk into a loop and none of them walks for ever
--- PASS: TestTheLikeliestTokenEveryTimeEndsInALoop (0.00s)
=== RUN   TestACountedPairIsAnAdjacencyAndNothingElse
--- PASS: TestACountedPairIsAnAdjacencyAndNothingElse (0.00s)
=== RUN   TestAChainRefusesWhatItCannotHaveCounted
    guess_test.go:248: counting: lang: token 3 of 3 is 291, and the vocabulary holds 291
    guess_test.go:253: asking: lang: no token 291 in a chain over a vocabulary of 291
--- PASS: TestAChainRefusesWhatItCannotHaveCounted (0.00s)
=== RUN   TestATemperatureOfZeroIsNotATemperature
    guess_test.go:264: shares: lang: a temperature divides every score, so it has to be above zero, not 0
--- PASS: TestATemperatureOfZeroIsNotATemperature (0.00s)
PASS
ok  	theworld/internal/lang	0.009s

The one to look at is the fourth. It runs two hundred draws four times over, at temperatures 0, 0.2, 1 and 5, and then asks the generator itself what state it is in afterwards. All four answers are the same twenty bytes, which is the only way to prove the fixed cost rather than assert it: a generator is the one witness that can say how much of a stream was spent. The sixth walks greedily from every token in the chain that has a continuation and finds a repeat in every one of them, so the loop in the failure box above is a property of the method and not a quirk of where that walk started.