## Evaluating Logic Circuits with Ternary Logic Graphs

This article describes how a basic RS NOR flip-flop circuit can be simulated using a directed graph constructed with source nodes (which output a value to nodes), terminal nodes (which take input from nodes), and gate nodes (which take input from nodes, do something with it, and provide the output to nodes). This graph propagates changed values to simulate the flow of electricity in the real-life logic circuit. It is based on a ternary logic system, which consists of a third unknown value in addition to the normal true and false values. In this article, balanced ternary is used to represent these values: +1 for true, 0 for unknown, and -1 for false. The language used in this article is Swift, as I wanted to try it out here by building (the bones of) a circuit simulator iOS app.

### The Logic Graph

Logic nodes are based upon two main protocols, which set out what nodes that provide output to the graph and a nodes that take input from the graph should do. Ternary values are represented by the type TValue, a typealias of Int.

The following structure represents an input to a logic node. This defines the node that the input is connected to, and the index of the input (this is useful when the referenced logic node has more than one input connection):

The protocol for a node that provides an output to the graph (such as a button) is defined below:

Each node providing an output to the graph has an array of child inputs, which are inputs that the source node is connected to in the logic circuit. When the node providing an output changes its outputValue, it passes the updated value and the corresponding input index to each node in its childInputs array using the update function, as shown by this implementation:

The other main protocol is for a node that takes an input from the graph, such as a lamp. This complements the OutputNode protocol to form a prototype for the I/O of a gate node.

As you can see, nodes that takes an input from the graph implement an update function, which is called by the OutputNode implementer whenever an input to the node changes. An example of a class which implements of this function is the TwoGateNode class, the base class for all logic gates with two inputs:

### Simulating an RS Latch

The RS NOR flip-flop circuit contains two source nodes, two gate nodes, and two terminal nodes. Initially their values are initialized to 0 (unknown):

If we set R and S to false, so that the latch is neither being set nor reset, the output (Q) remains unknown, as the state held by the latch is unknown:

Setting R to true resets the flip-flop, setting the value of the latch to false:

In step 1, the value of the reset node is updated. The reset node then updates its child, the NOR node. The updated input causes the NOR node to evaluate to false, as 1 NOR 0 = -1. As its value has changed, the NOR node now updates its children: the Q node and the second NOR node. This second NOR node now evaluates to true, as -1 NOR -1 = +1. Therefore, it updates its children: the Q̄ node and the first NOR node. The first NOR node reevaluates itself with the new input, but its output remains the same, so it does not need to update its children and the update process is concluded.

Setting R to false causes this new value to be propagated to the top NOR node, but the value of the NOR node does not change as the latch retains its state:

Setting S to true sets the value of the latch to true. Because the design of the flip-flop is symmetrical, setting S to true causes the same events to occur except with the vertically opposite nodes. Instead of Q being set to true and Q̄ to false, Q̄ is set to true and Q to false:

Finally, as with setting R to false, setting S to false causes propagation of S=-1, but again the value of the NOR node does not change, and the latch retains its state:

Here is a demonstration of an RS latch created with this circuit simulator running in the iOS Simulator. Notice how both lamps remain off until the reset button is toggled, indicating that the value of Q was initially unknown:

## Threes! AI — A Simple Distribution Method

The expectimax algorithm used by my AI for Threes! is fairly easy to parallelize, because the branches of the game tree can be surveyed in parallel. While developing the AI, I used the std::async function in C++ so that each node (up to a certain depth I defined) would run the expectimax algorithm on all of its child nodes in parallel. For production however, I wanted to run the AI on a small cluster of Raspberry Pis I had available, as they are fairly low power and, more importantly, they run silently.

In order to distribute the work amongst the Pis, I decided I would have one “master” computer that keeps track of the game state, decides what moves to make, and makes the moves. When deciding what the next move should be, this master computer then can use the help of the “worker” computers1. This worked better than just having each computer act as a worker, distributing work to its fellow workers. In this case, as you looked more moves in advance, each worker ended up spending a lot of time trying to find workers to distribute work to, which resulted in a lot of unnecessary holdup.

For communication between the computers, I chose to use simple TCP sockets. As my needs were quite simple, I decided to interface directly with the C APIs rather than finding a C++ socket library.

Here is a basic overview of what the master computer does when deciding what the next move should be:

1. Find the depth (number of moves ahead) which the AI will look. This is done by the dynamic_depth function, which takes into account parameters like how far into the game the current move is and how many empty tiles there are on the board.

2. Call the expectimax function, which traverses the game tree on the master computer until the parallelization depth is reached. The parallelization depth for each move is a constant number of levels above the leaf nodes.

3. When the parallelization depth is reached, iterate through each of the parallelized node’s children, and ask an available worker to find the score of this child. Wait for the results from the workers.

4. Use the results from the workers to find the score of the parallelized node. The score of the parallelized node is then used by the parent node to find the score of the parent, then the parent of the parent node to find the grandparent node’s score, and so on until the root node is reached.

5. When the root node is reached, choose the move corresponding to the highest scoring branch as the next move.

It’s step 3 in which the distribution occurs. This occurs by a short sequence of messages between the master and workers. Each message is prefixed by 4 characters which signify the length of the body of the message2, so the receiving computer knows how many characters it should listen for.

Firstly, the master sends each worker node the “READY” message:

Workers that are currently not processing a job listen out for this message, and will respond with the “READY” message to indicate that they are ready to accept work from the master:

The master then serialises the board data along with a few other parameters and sends this data to the first-responding worker:

This message is structured as follows:

The worker now decodes the message, creates the board object, and surveys the remainder of the branch locally with the expectimax algorithm. It then sends the score of the parallelized node to the master (in this case 2637.436035) and closes the connection:

1. Technically, the master computer is also a worker: due to the low resource usage of the master process, it makes sense to run a worker process on the same computer to utilise as much of the cluster’s computing power as possible.

2. A higher base could have been used to represent this length in order to code for longer message bodies, but this is unnecessary here as the message body length should never exceed 9999 characters.

## Threes! AI — Game Representation

Threes! is a puzzle game about combining numbers.  To start with, 1 and 2 become 3.   After 1 and 2, you can only combine tiles of the same value, so 3 and 3 would become 6, and 6 and 6 would become 12.   You may be familiar with this concept of combining numbers, which is featured in the popular game 2048 (derived from Threes, and in which powers of 2 are combined).

I played the game for a while, and having reached a fairly meagre high score of 27,351, I wondered if I could create an AI which would play Threes better than me.  I chose to use C++ rather than Python to create this AI to take advantage of the threading features in C++11, and also to have more control over how the game state was stored and passed around.

This article will discuss how I represented the game, namely the storage of the game state, the possible moves, the tile generator, and the scoring system.

### Tiles

There are 16 tiles in Threes, each of which can take on a value of either 0 (empty), 1, 2, or $$3 \times 2^n$$ (where n is a non-negative integer).  So I coded the tile value as below:

$c(x) = \left\{ \begin{array}{ll} x & \mbox{if } x \leq 3 \\ 3 + \log_2\left(\frac{x}{3}\right) & \mbox{if } x > 3 \end{array} \right.$

A coded tile value can then be decoded in the following way:

$c^{-1}(x) = \left\{ \begin{array}{ll} x & \mbox{if } x \leq 3 \\ 3 \times 2^{x-3} & \mbox{if } x > 3 \end{array} \right.$

In this way, tile values up to 12288 ($$3 \times 2^{15-3}$$) can be stored in a nibble. The game state contains 16 tiles of 4 bits, so a total of 64 bits is needed to store the game state. I chose to store the game state as a 64 bit integer.

We can now define a function which determines whether two tiles can be paired, and finds the value of the combined tile if they can be paired:

The first conditional allows two tiles with a value of the same multiple of 3 to be paired. The second conditional allows a tile to move into an empty space. For example, if a 6 tile is being moved into an empty space, pair_result(6, 0) will be called, which will give a result of 6, so the value of the empty space becomes 6. The tile value for the initial position of the 6 tile is then set to 0. The last conditional allows 1 and 2 to be paired to make 3. If none of these cases apply, then the tiles cannot be paired.

### Moves

There are four moves in Threes, which are up, down, left, and right. I could have implemented these moves with one function, however for readability purposes and because there are only four moves, I decided to implement a function for each move. Here, I’ll describe the up move.

When the board is slid up, the top row is immobile and cannot move. So we skip the first row and start from the second row. We then try to slide each tile onto the one above it. If they don’t pair, then we leave the tile as it is. If they do pair, then we set the top tile to the combined value and we set the bottom tile to 0 (to represent an empty tile location). Having finished the second row, we repeat this for the third row and finally the last row.

If we manage to pair at least one tile (including pairing a tile with an empty space) during this process, then the move is possible. At least one tile needs to move for the slide to be considered valid: if no tiles move, the game state doesn’t change.

Here is the function which is called to slide the board up:

If the move is valid, then the player’s turn is finished, and the computer will then place the next tile onto the board (we’ll discuss how the AI does this in a later article).

### Tile Generator

In Threes, the tile generator algorithm decides the next tile to be put in play (which is then displayed at the top of the screen). It is also used to select the starting tiles for a new game. The AI I created uses the description of the algorithm posted to Touch Arcade by kamikaze28. Tile generation is divided into two parts: the basic tiles, and the bonus tiles.

The basic tiles are 1, 2, and 3. These are generated by the following procedure, as described by kamikaze28:

The mechanic for drawing basic cards is best described with a face-down stack of cards as one would use in card games like Mau Mau or Gin rummy. In the case of Threes! this stack is comprised of the following cards:

• 4x blue 1s
• 4x red 2s
• 4x white 3s

As with the physical analogy, card stacks in Threes! are also shuffled upon creation. …With every move the top card of the stack is drawn which reveals the next card. When the last card of a stack is drawn after a move, a new stack is instantly created and shuffled. The top card of the fresh stack is then displayed as the next card.

Tiles above 3 are considered bonus tiles. The highest bonus tile that can be generated is the highest tile value on the board divided by 8, so bonus tiles can only be generated when a 48 tile or higher is on the board.

When bonus tiles are available, there is a 1/21 chance that the tile generated will be a bonus tile. Each bonus tile available has an equal chance of being generated, so the chance of a 6 being generated is the same as the chance of a 12 being generated (if both 6 and 12 are available).

#### Basic tile generation

To implement the basic tile mechanism, I created an array called rem_tile_count. This stores the number of each of the 1, 2, and 3 tiles left in the stack. The following function returns the total number of remaining tiles, and regenerates the stack of tiles if it is empty:

The basic tile is then generated by picking a random integer n, 0 ≤ n < total_tiles_remaining(). This can then be mapped to a tile value. The way that I do this can be visualised as assigning indexes to each tile, then generating the tile at index n. Let r(x) indicate the number of tiles of value x that remain in the stack. The 1 tile is assigned indexes 0 ≤ m < r(1). The 2 tile is then assigned indexes r(1) ≤ m < r(1) + r(2). Finally, the 3 tile is assigned indexes r(1) + r(2) ≤ m < r(1) + r(2) + r(3). Once the tile has been generated, we remove it from the stack and return its value. Here is an implementation of the basic tile generator (note that the r(x) function is denoted by rem_tile_count[x-1] due to the zero-indexing of arrays):

#### Bonus tile generation

Because each bonus tile available has an equal chance of being generated, the bonus tile generator is much easier to implement. My implementation uses the fact that the bonus tiles 6, 12, 24, 48 etc have codes 4, 5, 6, 7 etc. First, we determine the maximum bonus tile value b (this is just the highest tile value on the board divided by 8). We then pick a random integer m, 4 ≤ m ≤ c(b). m is the coded value of the bonus tile, so the generated bonus tile value is $$c^{-1}(m)$$.

I implemented this method slightly differently so that the random integer I need is of the format produced by arc4random().

First I found the number of bonus tiles available, s. This is equal to c(b) - 3 because the bonus tiles have codes 4, 5, 6 and so on. Now I can pick an random integer q, 0 ≤ q < s. This inequality is equivalent to 0 ≤ q < c(b) - 3, which is equivalent to 0 ≤ q ≤ c(b) - 4 because we are dealing with integers.

Therefore, to obtain the tile code of the generated tile, we can manipulate the inequality so it takes the form of the inequality 4 ≤ m ≤ c(b) that we found earlier. Adding 4 to each part of the inequality, we get 4 ≤ q + 4 ≤ c(b). It is now easy to see that m = q + 4, so the generated bonus tile value is $$c^{-1}(q+4)$$.

This function defines the number of cards in the bonus pool, s:

And here is the function which generates the bonus tile, $$c^{-1}(m)$$:

We can now generate a tile like so:

### Scoring

Our representation of the game is coming along well, however we need to be able to differentiate between game states so that the AI can choose the move that will lead to the best game state. We do this by scoring the board. For now, we will implement the scoring that Threes uses itself, however we could define heuristics so that the AI will prefer certain characteristics such as empty spaces or a uniform gradient of tiles.

Threes scores each individual tile, so that the score of the board is the sum of all the individual tiles. Tiles less than 3 are worth nothing. For tiles 3 and over, a tile value of x will score $$3^{\log_2(\frac{x}{3}) + 1}$$ points.

Here is an implementation of a function to give the score of an individual tile:

Hence, the score of a game state can then be evaluated using the following function:

We can now store the game state, execute moves, generate new tiles using the correct procedure, and evaluate the score of particular game states. An AI can now be implemented on top of this core logic.

## Regex Crossword →

I recently finished the Hamlet series of the Regex Crossword puzzles. These are crossword puzzles where clues are not in the format of sentences, but instead are regular expressions that the appropriate row or column must satisfy.  The website contains several collections of puzzles, each with a common theme such as cities or palindromes for example.  I enjoyed completing these puzzles and I’d recommend them to any regex fans.

For a more extreme challenge, check out the hexagonal regex crossword created for the 2013 MIT Mystery Hunt.

## Almost Everything's "Just" Philosophy

While discussing the recent xkcd on purity, one of my colleagues suggested to me that pretty much every article on Wikipedia is based on philosophy. His conjecture can be summarised, “For almost any Wikipedia article, if you repeatedly click on the first unbracketed link of an article’s content, you will eventually end up on the Philosophy article”. He demonstrated this by testing the Physics article. Sure enough, after at least 10 clicks, the Philosophy article appeared on his screen.

Somewhat intrigued by this proposition, I decided to write a program to test it myself with random Wikipedia pages. My program would consist of a function which extracted the first non-bracketed link. This would then be used to build a function which determined whether a random page eventually led to philosophy. The program would then get a random sample of links with this function and determine the proportion which follow the conjecture.

The extracting function required me to parse Wikipedia’s HTML to find the first non-bracketed link of each article. Being the silly regex lover that I am, I thought I’d just write a simple regex, rather than deal with superfluous HTML libraries. However, the first <a> tag within the article body usually ended up coming from one of the various bits of non-article content like disambiguation links, tables of contents, and infoboxes. After I had mostly dealt with this, I discovered that Wikipedia’s infoboxes sometimes contain nested <table> tags. I realised yet again that regex was not the right tool to scrape HTML, and yes, I would have to use an HTML library.

I found a surprisingly unconvoluted library named Beautiful Soup and quickly got this working with a reasonable rate of success. After I’d obtained a list of links in the article, I returned the first one which was a Wikipedia article. Finally, I edited the function so that if a section header was referenced in the URL (like /wiki/Structure#Physical_structure), the first link would be taken from the content of the section. Failing that, the remaining article after the referenced section header would be used.

After running my program with a sample size of 100, I noticed a specific error occasionally coming up. The great majority of links in Wikipedia articles linked to articles that existed, but some referenced a section that didn’t actually exist. For example, Power Rangers linked to /wiki/List_of_longest-running_United_States_television_series#16-19_years, resulting in the section not being found.

Consequently, I modified the program so that instead of crashing if it couldn’t find a section, it would just take the first link of the whole article. Perhaps a section link checker would make a useful Wikipedia bot. Anyway, with this modification, my program finally checked the whole 100 articles successfully, printing the following output:

Trial 1
---------
Random URL: /wiki/Annie_Funk
Checking /wiki/United_States
Checking /wiki/Federal_republic
Checking /wiki/Federation
Checking /wiki/Political_union
Checking /wiki/State_(polity)
Checking /wiki/Community
Checking /wiki/Level_of_analysis#Meso-level
Checking /wiki/Sample_population
Checking /wiki/Statistics
Checking /wiki/Data
Checking /wiki/Type%E2%80%93token_distinction
Checking /wiki/Philosophy

Trial 2
---------
Random URL: /wiki/Monks%27_Dyke_Tennyson_College
Checking /wiki/Coeducational
Checking /wiki/Single-sex_education
Checking /wiki/Education
Checking /wiki/Learning
Checking /wiki/Knowledge
Checking /wiki/Fact
Checking /wiki/Proof_(truth)
Checking /wiki/Necessity_and_sufficiency
Checking /wiki/Logic
Checking /wiki/Reasoning
Checking /wiki/Consciousness
Checking /wiki/Quality_(philosophy)
Checking /wiki/Property_(philosophy)
Checking /wiki/Modern_philosophy
Checking /wiki/Philosophy

Trial 3
---------
Random URL: /wiki/Jean_Schmit
Checking /wiki/Cycling
Checking /wiki/Bicycle
Checking /wiki/Human-powered_transport
Checking /wiki/Transport
Checking /wiki/Cargo
Checking /wiki/Good_(economics)
Checking /wiki/Economics
Checking /wiki/Social_science
Checking /wiki/Knowledge

Trial 4
---------
Random URL: /wiki/SS-Oberst-Gruppenf%C3%BChrer
Checking /wiki/Commissioned_officer
Checking /wiki/Armed_forces
Checking /wiki/Country
Checking /wiki/Political_geography
Checking /wiki/Human_geography
Checking /wiki/Geography
Checking /wiki/Earth
Checking /wiki/Planet
Checking /wiki/Astronomical_object
Checking /wiki/Entity
Checking /wiki/Abstraction
Checking /wiki/First_principle
Checking /wiki/Philosophy

Trial 5
---------
Random URL: /wiki/Gas_testing_examination
Checking /wiki/India
Checking /wiki/South_Asia
Checking /wiki/South
Checking /wiki/Noun
Checking /wiki/Part_of_speech
Checking /wiki/Grammar
Checking /wiki/Linguistics
Checking /wiki/Science
Checking /wiki/Knowledge

Trial 6
---------
Random URL: /wiki/Corticotropin-releasing_hormone_receptor_1
Checking /wiki/Protein
Checking /wiki/Biomolecule
Checking /wiki/Molecule
Checking /wiki/Atom
Checking /wiki/Matter
Checking /wiki/Rest_mass
Checking /wiki/Energy
Checking /wiki/Physics
Checking /wiki/Natural_science
Checking /wiki/Science

Trial 7
---------
Random URL: /wiki/Harry_Cunningham_Brodie
Checking /wiki/Liberal_Party_(UK)
Checking /wiki/Liberalism
Checking /wiki/Political_philosophy
Checking /wiki/Politics
Checking /wiki/Governance
Checking /wiki/Public-private_partnership
Checking /wiki/Private_sector
Checking /wiki/Profit_(accounting)
Checking /wiki/Accounting
Checking /wiki/Measurement
Checking /wiki/Mensural_notation
Checking /wiki/Polyphony
Checking /wiki/Music
Checking /wiki/Art
Checking /wiki/Human_behavior
Checking /wiki/Behavior
Checking /wiki/Organism
Checking /wiki/Biology
Checking /wiki/Natural_science

Trial 8
---------
Random URL: /wiki/James_Bevan_Bowen_(MP)
Checking /wiki/Conservative_Party_(UK)
Checking /wiki/Centre-right
Checking /wiki/Right-wing_politics
Checking /wiki/Social_stratification
Checking /wiki/Sociology
Checking /wiki/Social_behavior
Checking /wiki/Physiology
Checking /wiki/Function_(biology)
Checking /wiki/Evolved
Checking /wiki/Heredity
Checking /wiki/Phenotypic_trait
Checking /wiki/Phenotype
Checking /wiki/Organism

Trial 9
---------
Random URL: /wiki/2007_European_Junior_Baseball_Championship
Checking /wiki/European_Junior_Baseball_Championship
Checking /wiki/Baseball
Checking /wiki/Bat-and-ball_game
Checking /wiki/Playing_field
Checking /wiki/British_English
Checking /wiki/English_language
Checking /wiki/West_Germanic_languages
Checking /wiki/Germanic_languages
Checking /wiki/Indo-European_languages
Checking /wiki/Language_family
Checking /wiki/Language
Checking /wiki/Human
Checking /wiki/Hominini
Checking /wiki/Tribe_(biology)
Checking /wiki/Biology

Trial 10
----------
Random URL: /wiki/This_Storm
Checking /wiki/Sonya_Kitchell
Checking /wiki/United_States

Trial 11
----------
Random URL: /wiki/Hollyoaks_Later_(series_4)
Checking /wiki/Hollyoaks_Later
Checking /wiki/Channel_4
Checking /wiki/BBC
Checking /wiki/Wireless
Checking /wiki/Telecommunication
Checking /wiki/Communication
Checking /wiki/Information
Checking /wiki/Data

Trial 12
----------
Random URL: /wiki/Lowrider_(disambiguation)
Checking /wiki/Lowrider
Checking /wiki/Ground_clearance
Checking /wiki/Tire
Checking /wiki/Wheel
Checking /wiki/Bearing_(mechanical)
Checking /wiki/Machine_element
Checking /wiki/Machine
Checking /wiki/Tool
Checking /wiki/Matter

Trial 13
----------
Random URL: /wiki/Open-mid_central_unrounded_vowel
Checking /wiki/Vowel
Checking /wiki/Phonetics
Checking /wiki/Linguistics

Trial 14
----------
Random URL: /wiki/George_May_Keim
Checking /wiki/Democratic_Party_(United_States)
Checking /wiki/Two_party_system
Checking /wiki/Major_party
Checking /wiki/Political_party
Checking /wiki/Political_organisation
Checking /wiki/Organisation
Checking /wiki/Social
Checking /wiki/Organisms
Checking /wiki/Biology

Trial 15
----------
Random URL: /wiki/Francis_Parkman_House
Checking /wiki/National_Historic_Landmark
Checking /wiki/Building
Checking /wiki/Structure#Physical_structure
Checking /wiki/Engineering
Checking /wiki/Science

Trial 16
----------
Random URL: /wiki/Richard_Congress
Checking /wiki/President_of_the_United_States
Checking /wiki/Sovereign_state
Checking /wiki/Centralized_government
Checking /wiki/Political_power
Checking /wiki/Social_science

Trial 17
----------
Random URL: /wiki/Phyllopod_bed
Checking /wiki/USNM
Checking /wiki/Natural_history
Checking /wiki/Research
Checking /wiki/Theorem
Checking /wiki/Mathematics
Checking /wiki/Quantity
Checking /wiki/Property_(philosophy)

Trial 18
----------
Random URL: /wiki/New_Croton_aqueduct
Checking /wiki/Old_Croton_aqueduct
Checking /wiki/New_York_City
Checking /wiki/List_of_United_States_cities_by_population
Checking /wiki/Municipal_corporation
Checking /wiki/Local_government
Checking /wiki/Politics

Trial 19
----------
Random URL: /wiki/1996_Toronto_Blue_Jays_season
Checking /wiki/Toronto_Blue_Jays
Checking /wiki/Professional_baseball
Checking /wiki/Baseball

Trial 20
----------
Random URL: /wiki/Douglas_Township,_Clay_County,_Iowa
Checking /wiki/Township_(United_States)
Checking /wiki/United_States

Trial 21
----------
Random URL: /wiki/Keswick_Museum_and_Art_Gallery
Checking /wiki/Cumbria
Checking /wiki/Non-metropolitan_county
Checking /wiki/Metropolitan_and_non-metropolitan_counties_of_England
Checking /wiki/Subdivisions_of_England
Checking /wiki/England
Checking /wiki/Constituent_country
Checking /wiki/Country

Trial 22
----------
Random URL: /wiki/David_McGregor_(water_polo)
Checking /wiki/Great_Britain
Checking /wiki/Island
Checking /wiki/Continent
Checking /wiki/Landmass
Checking /wiki/Earth

Trial 23
----------
Random URL: /wiki/Montgey
Checking /wiki/Communes_of_France
Checking /wiki/Country

Trial 24
----------
Random URL: /wiki/Christopher_Wiehl
Checking /wiki/United_States

Trial 25
----------
Random URL: /wiki/Wonewoc
Checking /wiki/Wonewoc,_Wisconsin
Checking /wiki/Juneau_County,_Wisconsin
Checking /wiki/County_(United_States)
Checking /wiki/United_States

Trial 26
----------
Random URL: /wiki/Escudilla_Mountain
Checking /wiki/Apache_County
Checking /wiki/U.S._state
Checking /wiki/United_States

Trial 27
----------
Random URL: /wiki/Arguda
Checking /wiki/Lepidoptera
Checking /wiki/Order_(biology)
Checking /wiki/Biological_classification
Checking /wiki/Taxonomy_(biology)
Checking /wiki/Science

Trial 28
----------
Random URL: /wiki/Shilton_railway_station
Checking /wiki/Railway_station
Checking /wiki/Railway
Checking /wiki/Transport

Trial 29
----------
Random URL: /wiki/BZ20
Checking /wiki/Boy_band
Checking /wiki/Vocal_group
Checking /wiki/17:28
Checking /wiki/Boy_band

Trial 30
----------
Random URL: /wiki/Munkbrohamnen
Checking /wiki/Quay
Checking /wiki/Harbor
Checking /wiki/Ship
Checking /wiki/Buoyancy
Checking /wiki/Science

Trial 31
----------
Random URL: /wiki/Discant
Checking /wiki/Liturgy
Checking /wiki/Worship
Checking /wiki/Religion
Checking /wiki/Religious_studies
Checking /wiki/Secular
Checking /wiki/Religion

Trial 32
----------
Random URL: /wiki/Yuko_Moriguchi
Checking /wiki/Japan
Checking /wiki/Island_country
Checking /wiki/Country

Trial 33
----------
Random URL: /wiki/1971_San_Francisco_49ers_season
Checking /wiki/1971_NFL_season
Checking /wiki/Regular_season_(NFL)
Checking /wiki/National_Football_League
Checking /wiki/American_football
Checking /wiki/Team_sport
Checking /wiki/Sport
Checking /wiki/Competition
Checking /wiki/Biology

Trial 34
----------
Random URL: /wiki/The_Pictou_Highlanders
Checking /wiki/Infantry
Checking /wiki/Warfare
Checking /wiki/Politics

Trial 35
----------
Random URL: /wiki/335th_Theater_Signal_Command_(United_States)
Checking /wiki/United_States_Army
Checking /wiki/United_States_Armed_Forces
Checking /wiki/Armed_forces

Trial 36
----------
Random URL: /wiki/Jacques_Freitag
Checking /wiki/South_Africa
Checking /wiki/Africa
Checking /wiki/Continent

Trial 37
----------
Random URL: /wiki/Corvallis-Benton_County_Public_Library
Checking /wiki/Public_library
Checking /wiki/Library
Checking /wiki/Book
Checking /wiki/Ink
Checking /wiki/Liquid
Checking /wiki/State_of_matter#The_Four_Fundamental_States
Failed to find section The_Four_Fundamental_States.
Checking /wiki/Physics

Trial 38
----------
Random URL: /wiki/Bulatov
Checking /wiki/Alexei_Bulatov
Checking /wiki/Ice_hockey
Checking /wiki/Ice_skating
Checking /wiki/Ice
Checking /wiki/Water
Checking /wiki/Chemical_compound
Checking /wiki/Chemical_substance
Checking /wiki/Chemistry
Checking /wiki/Physical_science
Checking /wiki/Physics

Trial 39
----------
Random URL: /wiki/Pyramid_Hills
Checking /wiki/California_Coast_Ranges
Checking /wiki/California
Checking /wiki/U.S._State
Checking /wiki/United_States

Trial 40
----------
Random URL: /wiki/Tischeria_ceanothi
Checking /wiki/Moth
Checking /wiki/Insect
Checking /wiki/Class_(biology)
Checking /wiki/Biological_classification

Trial 41
----------
Checking /wiki/Institution
Checking /wiki/Social_structure
Checking /wiki/Social_science

Trial 42
----------
Random URL: /wiki/HMS_Havock_(1893)
Checking /wiki/Havock_class_destroyer
Checking /wiki/Ship_class
Checking /wiki/Ship

Trial 43
----------
Random URL: /wiki/Ultraist_movement
Checking /wiki/Literature
Checking /wiki/Ordinary_language
Checking /wiki/Phrase
Checking /wiki/Word
Checking /wiki/Linguistics

Trial 44
----------
Random URL: /wiki/Six_Degrees_(beverage)
Checking /wiki/Absinthe
Checking /wiki/Distillation
Checking /wiki/Separation_process
Checking /wiki/Chemistry

Trial 45
----------
Random URL: /wiki/Pinktoe_tarantula
Checking /wiki/Tarantula
Checking /wiki/Arachnid
Checking /wiki/Class_(biology)

Trial 46
----------
Random URL: /wiki/Milka_Bliznakov
Checking /wiki/Bulgaria
Checking /wiki/Southeast_Europe
Checking /wiki/Greece
Checking /wiki/Southern_Europe
Checking /wiki/Policy
Checking /wiki/Executive_order_(United_States)
Checking /wiki/President_of_the_United_States

Trial 47
----------
Random URL: /wiki/Matte_Le%C3%A3o
Checking /wiki/The_Coca-Cola_Company
Checking /wiki/Multinational_corporation
Checking /wiki/Corporation
Checking /wiki/Separate_legal_entity
Checking /wiki/Legal_person
Checking /wiki/Legal_capacity
Checking /wiki/Natural_person
Checking /wiki/Jurisprudence
Checking /wiki/Education

Trial 48
----------
Random URL: /wiki/Chryseofusus_acherusius
Checking /wiki/Species
Checking /wiki/Biology

Trial 49
----------
Random URL: /wiki/Dominic_Johnson
Checking /wiki/St_Lucia
Checking /wiki/Sovereign_state

Trial 50
----------
Random URL: /wiki/Death_of_a_Hussy
Skipping /wiki/File:M._C._Beaton_-_Death_of_a_Hussy.jpeg
Checking /wiki/1990_in_literature
Checking /wiki/Anton_Chekhov
Checking /wiki/Dramaturge
Checking /wiki/Theatre
Checking /wiki/Fine_art
Checking /wiki/Art

Trial 51
----------
Random URL: /wiki/GIVE_Center_West
Checking /wiki/Gwinnett_County
Checking /wiki/County_(United_States)

Trial 52
----------
Random URL: /wiki/Colonization
Checking /wiki/Biogeography
Checking /wiki/Species

Trial 53
----------
Checking /wiki/Romania
Checking /wiki/Danube
Checking /wiki/Central_and_Eastern_Europe
Checking /wiki/Central_Europe
Checking /wiki/Europe
Checking /wiki/Continent

Trial 54
----------
Random URL: /wiki/Armee-Abteilung_Woyrsch
Checking /wiki/Field_army
Checking /wiki/Military_formation
Checking /wiki/State_(polity)

Trial 55
----------
Checking /wiki/England

Trial 56
----------
Random URL: /wiki/Morton_Lucas
Checking /wiki/Sussex_County_Cricket_Club
Checking /wiki/Historic_counties_of_England
Checking /wiki/Normans
Checking /wiki/Normandy
Checking /wiki/France
Checking /wiki/Western_Europe
Checking /wiki/Europe

Trial 57
----------
Random URL: /wiki/Spindle_cell_carcinoma
Checking /wiki/Cancer
Checking /wiki/Malignancy
Checking /wiki/Tumor
Checking /wiki/Cell_(biology)
Checking /wiki/Life
Checking /wiki/Physical_body
Checking /wiki/Physics

Trial 58
----------
Random URL: /wiki/Commission_of_array
Checking /wiki/Letters_patent
Checking /wiki/Legal_instrument
Checking /wiki/Law
Checking /wiki/System
Checking /wiki/Element_(mathematics)
Checking /wiki/Mathematics

Trial 59
----------
Random URL: /wiki/Seasons_End_(album)
Checking /wiki/Marillion
Checking /wiki/British_rock
Checking /wiki/British_Invasion
Checking /wiki/Rock_music
Checking /wiki/Popular_music
Checking /wiki/Musical_genre
Checking /wiki/Music

Trial 60
----------
Checking None

Trial 61
----------
Random URL: /wiki/Masorti
Checking /wiki/Conservative_Judaism
Checking /wiki/Jewish_denominations
Checking /wiki/Jew
Checking /wiki/Nation
Checking /wiki/Culture
Checking /wiki/Classical_antiquity
Checking /wiki/History
Checking /wiki/George_Santayana
Checking /wiki/American_people
Checking /wiki/Americas
Checking /wiki/New_World
Checking /wiki/Western_Hemisphere
Checking /wiki/Geography

Trial 62
----------
Checking /wiki/List_of_countries_and_dependencies_by_area
Checking /wiki/World
Checking /wiki/Human

Trial 63
----------
Random URL: /wiki/List_of_Scottish_monarchs

Trial 64
----------
Random URL: /wiki/Yves_Leterme
Checking /wiki/Flemish_people
Checking /wiki/Germanic_peoples
Checking /wiki/Proto-Indo-Europeans
Checking /wiki/Proto-Indo-European_language
Checking /wiki/Linguistic_reconstruction
Checking /wiki/Attested_language
Checking /wiki/Linguistics

Trial 65
----------
Random URL: /wiki/Reilly_and_Maloney
Skipping http://reillyandmaloney.com/
Checking None

Trial 66
----------
Random URL: /wiki/Texas_State_Highway_Loop_360
Checking /wiki/Loop_route
Checking /wiki/Transport

Trial 67
----------
Random URL: /wiki/Lindauer_Allee_(Berlin_U-Bahn)
Checking /wiki/Berlin_U-Bahn
Checking /wiki/Rapid_transit
Checking /wiki/Public_transport
Checking /wiki/Passenger
Checking /wiki/Vehicle
Checking /wiki/Motion_(physics)
Checking /wiki/Physics

Trial 68
----------
Random URL: /wiki/Hitler_Youth_knife
Checking /wiki/Knife
Checking /wiki/Tool

Trial 69
----------
Random URL: /wiki/Mizrah
Checking /wiki/Diaspora
Checking /wiki/Atlantic_Ocean
Checking /wiki/Ocean
Checking /wiki/World_Ocean
Checking /wiki/Ocean

Trial 70
----------
Random URL: /wiki/Neeta_Shah
Checking /wiki/India

Trial 71
----------
Random URL: /wiki/Philip_Magee
Checking /wiki/Ireland
Checking /wiki/Ulster_Scots_dialects
Checking /wiki/Scots_language
Checking /wiki/Germanic_languages

Trial 72
----------
Random URL: /wiki/Don_Caley

Trial 73
----------
Random URL: /wiki/Robert_Bodley
Checking /wiki/South_Africa

Trial 74
----------
Random URL: /wiki/Muscodor
Checking /wiki/Genus
Checking /wiki/Biology

Trial 75
----------
Random URL: /wiki/Rutherford_Township,_Martin_County,_Indiana
Checking /wiki/Civil_township
Checking /wiki/Local_government

Trial 76
----------
Random URL: /wiki/Children_of_Tsunami:_No_More_Tears
Checking /wiki/Short_film
Checking /wiki/Feature_film
Checking /wiki/Film
Checking /wiki/Phi_phenomenon
Checking /wiki/Phi
Skipping /wiki/Wikipedia:Pronunciation_respelling_key
Checking /wiki/Voiceless_bilabial_plosive
Checking /wiki/Consonant
Checking /wiki/Articulatory_phonetics
Checking /wiki/Phonetics

Trial 77
----------
Random URL: /wiki/Cecil_Martin
Checking /wiki/American_football

Trial 78
----------
Random URL: /wiki/Cristian_Valenzuela
Checking /wiki/Congenital_glaucoma
Checking /wiki/Epiphora_(medicine)
Checking /wiki/Tears
Checking /wiki/Eye
Checking /wiki/Organ_(anatomy)
Checking /wiki/Biology

Trial 79
----------
Random URL: /wiki/The_Critics_Group
Checking /wiki/Ewan_MacColl
Checking /wiki/Folk_singer
Checking /wiki/Music

Trial 80
----------
Random URL: /wiki/Pro_Sport_Hockey
Checking /wiki/Japan

Trial 81
----------
Random URL: /wiki/List_of_major_power_stations_in_Hubei_province
Checking /wiki/Power_stations
Checking /wiki/Power_(physics)
Checking /wiki/Physics

Trial 82
----------
Random URL: /wiki/Vince_Peart
Checking /wiki/Alston,_Cumbria
Checking /wiki/Cumbria

Trial 83
----------
Random URL: /wiki/Yonrico_Scott
Checking /wiki/United_States

Trial 84
----------
Random URL: /wiki/Protein_Expression_and_Purification
Checking /wiki/Peer_review
Checking /wiki/Field_of_study
Checking /wiki/Knowledge

Trial 85
----------
Random URL: /wiki/John_B._Henderson
Checking /wiki/United_States_Senator
Checking /wiki/Bicameralism
Checking /wiki/Classical_antiquity

Trial 86
----------
Random URL: /wiki/Vitaliy_Sobko
Checking /wiki/Ukraine
Checking /wiki/Eastern_Europe
Checking /wiki/Europe

Trial 87
----------

Trial 88
----------
Random URL: /wiki/Donja_Toponica_(Prokuplje)
Checking /wiki/Village
Checking /wiki/Human_settlement
Checking /wiki/Statistics

Trial 89
----------
Random URL: /wiki/Melanomyinae
Checking /wiki/Calliphoridae
Checking /wiki/Family_(biology)
Checking /wiki/Biological_classification

Trial 90
----------
Random URL: /wiki/Coitus_interruptus
Checking /wiki/Sexual_intercourse
Checking /wiki/Pelvic_thrusting
Checking /wiki/Pelvis
Checking /wiki/Anatomy
Checking /wiki/Body_plan
Checking /wiki/Phylum
Checking /wiki/Taxonomic_rank
Checking /wiki/Biological_classification

Trial 91
----------
Checking /wiki/Census-designated_place
Checking /wiki/Place_(United_States_Census_Bureau)
Checking /wiki/United_States_Census_Bureau
Checking /wiki/Federal_Statistical_System_of_the_United_States
Checking /wiki/Federal_government_of_the_united_states
Checking /wiki/Federal_government
Checking /wiki/Political_union

Trial 92
----------
Random URL: /wiki/Queen_Elizabeth_Islands
Checking /wiki/Island

Trial 93
----------
Random URL: /wiki/South_Korean_football_league_system
Checking /wiki/South_Korea
Checking /wiki/East_Asia
Checking /wiki/Subregion
Checking /wiki/Region
Checking /wiki/Geography

Trial 94
----------
Random URL: /wiki/Eanmund_of_Kent
Checking /wiki/King_of_Kent
Checking /wiki/Anglo-Saxons
Checking /wiki/Great_Britain

Trial 95
----------
Random URL: /wiki/Linwood_Boulevard_(Kansas_City,_Missouri)
Checking /wiki/Kansas_City,_Missouri
Checking /wiki/United_States

Trial 96
----------
Random URL: /wiki/Marko_Martini%C4%87
Checking /wiki/Croatia
Checking /wiki/Parliamentary_republic
Checking /wiki/Republic
Checking /wiki/Form_of_government
Checking /wiki/State_(polity)

Trial 97
----------
Random URL: /wiki/Achille_Richard
Checking /wiki/Louis_Claude_Richard
Checking /wiki/France

Trial 98
----------
Random URL: /wiki/Twigg_Township,_Hamilton_County,_Illinois
Checking /wiki/Civil_township

Trial 99
----------
Random URL: /wiki/Lester_Orlebeck
Checking /wiki/Film_editor
Checking /wiki/Post-production
Checking /wiki/Filmmaking
Checking /wiki/Film

Trial 100
-----------
Random URL: /wiki/Broken_Down_in_Tiny_Pieces
Checking /wiki/Country_music
Checking /wiki/American_popular_music
Checking /wiki/Ragtime
Checking /wiki/Syncopation
Checking /wiki/Music