The Wikipedia Game Player

Welcome to the The Wikipedia Game Player project! This Go(lang) project gives solutions for The Wikipedia Game through web scrapping, various search algorithms, and parallel computing (hooray for Go routines).

The Wikipedia Game is a game where a player receives two distinct Wikipedia pages, for example, Eiffel Tower and Soybean. The goal is to find a path between the two pages using only Wikipedia links within each page. A possible solution would be the path: Eiffel Tower → List of tallest towers → Brazil → Soybean

Search Algorithms

These are the search algorithms that are currently implemented

Depth-First Search (DFS)

Depth-First Search (DFS) is a search algorithm that explores as far as possible along each branch before backtracking. Since Wikipedia Pages form a Cyclic Graph, this is in fact a Depth-Limited Search to avoid an infinite search. The maximum depth is given as input.

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a search algorithm that explores level by level, visiting all nodes at a certain depth level before moving on to the next.

Bidirectional Breadth-First Search (BDBFS)

Bidirectional Breadth-First Search (BDBFS) is a search algorithm that simultaneously explores from the start and goal nodes, meeting somewhere in the middle. This algorithm is used with Undirected Graphs since there is the need to find a path starting from the end that can then be inverted. Wikipedia is instead a Directed Graph, meaning that A can have a link to B but not necessarily the other way around. To adapt for this, the algorithm is altered so that every time a path from the end to a common middle point is found, it verifies if said path exists in the reverse order. This adaption works for this specific problem since there is a moderately high level of probability (although not too high) that if A has a link to B, B will also have a link to A.

Differences Between Search Algorithms

The Bidirectional Breadth-First Search is, in most cases, the fastest algorithm. Its drawbacks are that it doesn't guarantee the shortest path and only finds bidirectional paths. The Breadth-First Search is the only one that guarantees finding the shortest path. It can beat BDBFS in some cases but it's not as consistent. The Depth-First Search can be quite effective given two conditions: i) the order in which it searches the links is favorable; and ii) we already know the length of the shortest path.

The following table shows the results and times of the various algorithms across different games with single- and multi-threaded variants (the defined maximum depth for DFS corresponds to the depth of the shortest path).

Game	DFS (Single-threaded)	BFS (Single-threaded)	BFS (Multi-threaded)	BDBFS (Single-threaded)	BDBFS (Multi-threaded)
Jesus ↓ Iron	Jesus ↓ Sanhedrin ↓ Iron	Jesus ↓ Sanhedrin ↓ Iron	Jesus ↓ Sanhedrin ↓ Iron	Jesus ↓ Jerusalem ↓ Bronze_Age ↓ Iron	Jesus ↓ Judaea_(Roman_province) ↓ Iron_Age ↓ Iron
Time (seconds)	7.8	7.2	2.2	6.7	3.6
Incandescent light bulb ↓ Logic	Incandescent_light_bulb ↓ Gender_of_connectors_and_fasteners ↓ Machine ↓ Logic	Incandescent_light_bulb ↓ Gender_of_connectors_and_fasteners ↓ Machine ↓ Logic	Incandescent_light_bulb ↓ Gender_of_connectors_and_fasteners ↓ Machine ↓ Logic	Incandescent_light_bulb ↓ Electric_light ↓ Age_of_Enlightenment ↓ Philosophy ↓ Logic	Incandescent_light_bulb ↓ Vacuum ↓ Greek_philosophy ↓ Outline_of_philosophy ↓ Logic
Time (seconds)	5.3	17.9	3.1	1.53	3.0
DNA sequencing ↓ Steam engine	DNA_sequencing ↓ Genetics ↓ Negative_feedback ↓ Steam_engine	DNA_sequencing ↓ Genetics ↓ Negative_feedback ↓ Steam_engine	DNA_sequencing ↓ Genetic_variation ↓ Erasmus_Darwin ↓ Steam_engine	DNA_sequencing ↓ Genome ↓ Homo_sapiens ↓ History_of_technology ↓ Steam_engine	DNA_sequencing ↓ Genome ↓ Economies_of_scale ↓ Industrial_Revolution ↓ Steam_engine
Time (seconds)	16.0	38.6	18.4	2.9	3.7
Medication ↓ Maya civilization	Medication ↓ Honey ↓ Maya_civilization	Medication ↓ Honey ↓ Maya_civilization	Medication ↓ Honey ↓ Maya_civilization	Medication ↓ Pharmacy ↓ Mortar_and_pestle ↓ Maya_civilization	Medication ↓ Pharmacy ↓ Mortar_and_pestle ↓ Maya_civilization
Time (seconds)	24.6	22.3	7.3	3.1	2.4

Usage

The search can be run using the command-line as follows:

./wikiplayer start_page goal_page search_type [depth] [workers]

Where:

• start_page and goal_page define the starting and ending pages of the desired path, which can be full Wikipedia URLs (https://en.wikipedia.org/wiki/Software_engineering) or just the final sections of the URLs representing the topic (Software_engineering).
• search_type defines which search algorithm to use, can be dfs for DFS, bfs for BFS, and bdbfs for BDBFS.
• depth is only needed when using DFS and is an integer defining the maximum depth of the search.
• workers is only needed when using BFS or BDBFS and is an integer defining the maximum number of Go routines to create during the algorithm. The default value is 1, resulting in single-threaded execution. The actual number of cores used for parallel computation will correspond to the available number of logical CPUs, as returned by runtime.NumCPU().

Examples

./wikiplayer Jonas_Brothers Kofi_Annan bfs 5

Jonas_Brothers
We_Day
Kofi_Annan

./wikiplayer https://en.wikipedia.org/wiki/Incandescent_light_bulb https://en.wikipedia.org/wiki/Logic dfs 4

Incandescent_light_bulb
Gender_of_connectors_and_fasteners
Machine
Logic