Enabling AI to Design Sorting Algorithms

Several boxes are randomly arranged in a line. By regularly repeating the following three functions, the arrangement of the boxes, originally random, can be sorted by the weight of the boxes from lightest to heaviest.

• Function to place two boxes on the left and right pans of a balance scale.
• Function to swap the positions of two boxes placed on the balance scale.
• Function to return the positions of two boxes placed on the balance scale to their original positions without swapping.

Can AI design sorting algorithms?

A game app was developed using these three functions to sort, and upper-grade elementary school students were asked to play. Although they were given some hints, they were encouraged to figure out the process independently. As a result, approximately 30% of the elementary school students were able to design algorithms akin to bubble sort. Bubble sort can be considered an algorithm that is easy for humans to design.

Key Points of this Educational Game

Designing algorithms is often thought to require coding, or programming skills, but this is not necessarily the case. Just as one might think one needs to write sheet music to compose, being able to play instruments like the piano or guitar enables composition in essence. Similarly, providing tools that allow students to demonstrate algorithms in their minds is beneficial.

Play Logs, Symbol Sequences, and Reinforcement Learning

The play logs of this educational game, when converted into symbols representing each function, become mere symbol sequences. By rewarding symbol sequences that lead to sorted states and penalizing those that don't (as needed), reinforcement learning becomes possible. Thus, it becomes feasible to allow AI, rather than elementary school students, to design sorting algorithms. Is bubble sort as easy to design for AI as it is for humans? What differences exist between human thought processes and those of AI?

Can it be Said that an Algorithm was Designed? The Chinese Room

Using the aforementioned method, if AI can learn how to lead to a sorted state, can it be said that "AI has designed an algorithm"? This question is fundamentally similar to the Chinese Room debate.

Computational Complexity: Processing Cost vs. Design Cost

In the field of computational complexity theory, which studies the difficulty of problems, the primary measure of computational complexity is the "cost of solving a problem (computation/processing time, required memory)". This research studies the difficulty of problems by using the "cost of discovering how to solve a problem" as a measure.