Course:CPSC312-2017-Math24 Solver

From UBC Wiki

Math24 Solver

Authors: Lydia Li, Emrys Yang

What is the problem?

The Math24 Game is an arithmetical card game in which the objective is to find a way to manipulate four integers so that the end result is 24. For example, for the card with the numbers 4, 7, 8, 8, a possible solution is (7 - (8 / 8)) * 4 = 24. We will attempt to generate a Math 24 game of simple difficulty using Prolog and see if Prolog can solve it (generate all possible solutions). For more information of Math24, see here: 24 Game

What is the something extra?

- We will attempt to see if we can create a simplified solution so that same solution with different number order will be eliminated.

     Example: (6 + 7 + 5 + 6) = 24 and (7 + 6 + 6 + 5) = 24 will be regarded as the same solution.

- We will attempt to see if we can create higher levels of difficulties for Math24 and have Prolog solve it too:

     The original version of 24 is played with an ordinary deck of playing cards with all the face cards removed. The aces are taken to have the value 1 and the basic game proceeds by having 4 cards dealt and the player that can achieve exactly number 24 using allowed operations wins this round of the game. 

Normally when we play this game, we only using basic operations (addition, subtraction, multiplication, division, and parentheses) to keep it simple and time-saving. However, in our Math24 Solver, we would like to include face cards (Jack = 11, Queen = 12, King = 13) and using more complex operations:

  • Exponentiation.
     Example: for cards 4, 2, 5, 3, we can do calculations like (4^2 + 5 + 3) = 24.
  • Square Root. (Due to prolog language expression, sqrt() is same as 2√, so card 2 is needed for this operation)
     Example: for cards 4, 9, 2, 9, we can do calculations like (4 * (9 - sqrt(9))) = 24.   
  • Logarithms.
     Example: for cards 4, 2, 10, 12, we can do calculations like (log2(4) + 10 + 12) = 24.
  • Factorial.
     Example: for cards 3, 2, 6, 6, we can do calculations like (3! + 2 *6 + 6) = 24.

What did we learn from doing this?

In this project, we found using Prolog for Math24 Solver Logic programming is a feasible one but not the best one. It makes the expression easier and faster, and more particularly in the following aspects:

  • Prolog a pure functional language, which is based on the theory of predicate logic. The most basic way to write is to set the relationships between settled items. Thus these relations can be used when you ask the target query to find out the relationship between various objects. The system itself can automatically match, finding out the answer to the question.
  • Prolog provides a simple way to express interpretive program. It tries to use its internal rules matching engine to meet the needs of each Boolean function, which is nearly transparent for us (programmers). In a way, it helps us focus more on what we have done, instead of thinking about what to do next.
  • Prolog, compare to other programming languages, is more readable and easier for logic composition. When we design our project, we first set up another base case, and then consider the simple relations, and finally, start the complex one. Each clause or relation is built on previous, so when prolog run, it will first judge if the case meets the base case, if not, it will test the simple one and then the complex one. So, when writing the code, prolog provide a clear and reasonable logic progress which is easier for both programmer and other people to understand how the whole project works.

On the other hand, however, Prolog is inconvenient in some calculation aspect.

  • When we implemented “Exponentiation” function in our Math24 project, and tried to put “^” in between four random integers, we found out that since Prolog will recursively run the program until it lists all the solution and try every possible use of every operator, it is easy for Prolog to reach its maximum memory. So, in current setting, Prolog does not have the ability to calculating large numbers, like: 10^8 or 9^6. In this case, it throws an Error Exception: “Out of global stack”.
  • In our project Math24 Solver, Prolog needs to consider every solution that makes four random integers into 24. We use reverse Polish Notation to list all possible arrangements of operators and numbers (can also be regarded as enumeration method) and then try every case to get all arrangements that can get 24 (or 24.0). Therefore, for some cases, especially cases using an advanced operator, the memory limit exceeded, and also throwing the Exception: “Out of global stack”.
  • When we call the clauses, Prolog cannot change the constant in the functions as other programming languages, we can only call those clauses we already defined or change the constant directly in the clauses.

Things we did that are different from "Something extra":

  1. Logarithm. We can apply logarithm in our Math24 Solver project, but we found that Prolog only has logarithm with “Base 10” or “Base e”. As our solver is help users get 24 in their result, we should mainly focus on integer calculation. Our random numbers are limited between 1 and 13, therefore, except 1 and 10, most of the number will not get integer after using logarithm in the operation. Thus, we believe that adding logarithm operator(both log10 and loge) is not helpful for our solver and may let the memory have extra burden when running the project.
  2. Factorial. Factorial, compared to previous operators, is different in Prolog, as it is not a defined operator. To able the factorial in our project, we need to build-in its function by ourselves. However, similar to exponential operator's case as we mentioned above, when doing factorial with four numbers, the system needs to calculate all possible use of operators, so a case like that 7! * 6! * 8! * 5! or 7 ^ 6! * 8! * 5! is included. As factorial usually results in a large number, time four large number or even have exponential operator between them is not possible for prolog's memory. Therefore, including factorial in our solver as an operator to solve the 24 problem is currently not feasible.

Code Submission

Link to our code: Math 24 solver