Niya is a tic-tak-toe board game. The major mechanic of Niya is that your move determines what move your opponent can make. Each tile has two values associated with it; a letter, and a number. When a tile is played, the other player has to match one of the two values for their next move. There are several ways to win: have a row of your tiles, have a column of your tiles, have a diagonal of your tiles, have a 2-by-2 of your tiles, or make it that your opponent can't play on any unplayed tiles.
Python 3 with the built in modules are required to play.
The following module is needed to view the profile generated by cProfile:
pip install cprofilev
I've made three separate files to preserve milestones.
-
The first file worked on is Niya.py
- First working version of Niya created.
- Written without using profiling for optimization.
- Written with readability in mind.
-
The second file is NiyaButFaster.py
- Speeds up script without any major architectural changes.
- Uses cProfile to determine time sinks.
- Uses Bencharker.py to test fastest way to speed up a function.
-
The last and fastest version of Niya is NiyaBut1D.py
- Testing a different architecture to see if it is faster.
- Changed the board from a 2D array to a 1D array.
- Uses Bencharker.py to test fastest way to speed up a function.
The real goal of the project is to learn how to approach a huge computational problem and shrink it. I want to learn how to measure the size of the problem. Where I'm standing, and how to accomplish it. I want to learn more about group theory and apply it to the project. The goal is to make a piece of software that will solve Niya completely, and let the user play with the computer.
- Written in Python.
- No classes.
- Generate boards randomly.
- Play with the computer.
- Only use modules included with Python.
- Utilize a profiler to view what is taking time.
- Optimize; preferably to around a minute per board.
- Make a perfect computer player.
- Calculate the number of unique boards.
- Have a way to determine if a board plays the same as another.
- Calculate the time, memory, and storage required to solve all boards.
- Write a technical overview of my findings.
- Solve each board in less than 10 seconds.
- Solve every board that exists; all 20,922,789,888,000 of them!
- Store all boards somewhere.
- Board solved in one minute and a half; much quicker than the initial six minutes required.
- Computer is hard to tie; let alone winning against it when it has the first move.
- Wasn't able to series every board with no duplicates.
- Not enough time to calculate every board.
- The way score is calculated is slower than it needs to be.
- Learned quite a bit about Python.
- Able to reason a computational problem smaller.
- Application of Group Theory to a real problem.
- Learned how to use a profiler to see a programs runtime statistics.
- Understand why to not optimize too early.
- Niya is completely deterministic.
- Need to give myself a deadline for projects like this.
- Arrays take a lot of time to parse, and should favor a 1D array when possible.
- Python ==operator is sometimes considerably slower than using the in_operator.
- Calling the all and join function takes a long time.
- Pythons stack limit has saved me several times.
I've spent quite a bit of time working on the solver, and I would like to spend more. However, I've gained the lesson of how to optimize calculations of a large data set, and how to push Python to it's limits. Continuing will have diminishing returns with that goal. However, if I were to continue some of these would be worked on next:
- Generating many boards at once; save and recall them for play.
- Rework the way the score and win chances are calculated to be quicker.
- Use a different way of representing the board to increase the speed of the calculations.
- Multi-thread the script.
To benchmark, use cProfile to generate a profile with the following on the command line:
python -m cProfile -o [out_file] [script.py]
This saves the results of the profile to out_file.
To view out_file, use cprofilev by running the following:
cprofilev -f [outfile]
This generates a website at localhost:4000.
309913219 function calls (301813506 primitive calls) in 387.157 seconds
ncalls tottime percall cumtime percall filename:lineno(function)
8/1 0.000 0.000 387.157 387.157 {built-in method builtins.exec}
1 0.000 0.000 387.157 387.157 Niya.py:1(<module>)
1 0.000 0.000 387.147 387.147 Niya.py:371(SolveWrapper)
8099576/1 57.498 0.000 387.147 387.147 Niya.py:206(Solve)
10086195 15.801 0.000 167.172 0.000 Niya.py:131(CheckWin)
23356773 79.573 0.000 79.573 0.000 Niya.py:75(CreateBoardHash)
9600102 36.365 0.000 78.385 0.000 Niya.py:90(CheckRow)
8099576 50.359 0.000 52.722 0.000 Niya.py:142(FindPlayable)
37588640 18.438 0.000 36.149 0.000 {built-in method builtins.all}
8809291 31.380 0.000 31.380 0.000 Niya.py:119(CheckBox)
10086195 28.612 0.000 28.612 0.000 Niya.py:96(CheckCol)
123295844 23.582 0.000 23.582 0.000 Niya.py:92(<genexpr>)
15257197 16.088 0.000 16.088 0.000 Niya.py:183(AddSmartScore)
9017360 12.994 0.000 12.994 0.000 Niya.py:105(CheckDia)
15257197 7.437 0.000 7.437 0.000 Niya.py:160(PlayPiece)
15257197 4.506 0.000 4.506 0.000 Niya.py:165(UnplayPiece)
15257509 2.362 0.000 2.362 0.000 {method 'append' of 'list' objects}
840816 2.150 0.000 2.150 0.000 Niya.py:169(NoPlays)
140972045 function calls (132348212 primitive calls) in 204.492 seconds
ncalls tottime percall cumtime percall filename:lineno(function)
11/1 0.000 0.000 204.492 204.492 {built-in method builtins.exec}
1 0.000 0.000 204.492 204.492 NiyaButFaster.py:1(<module>)
1 0.000 0.000 204.481 204.481 NiyaButFaster.py:363(SolveWrapper)
8623683/1 38.935 0.000 204.481 204.481 NiyaButFaster.py:198(Solve)
10424110 10.749 0.000 74.835 0.000 NiyaButFaster.py:115(CheckWin)
24742929 43.044 0.000 43.044 0.000 NiyaButFaster.py:59(CreateBoardHash)
9301687 25.767 0.000 25.767 0.000 NiyaButFaster.py:101(CheckBox)
8623683 23.609 0.000 23.609 0.000 NiyaButFaster.py:126(FindPlayable)
10424110 22.083 0.000 22.083 0.000 NiyaButFaster.py:78(CheckCol)
16119246 12.604 0.000 12.604 0.000 NiyaButFaster.py:176(AddSmartScore)
9554363 9.986 0.000 9.986 0.000 NiyaButFaster.py:87(CheckDia)
10001533 6.249 0.000 6.249 0.000 NiyaButFaster.py:69(CheckRow)
16119246 6.120 0.000 6.120 0.000 NiyaButFaster.py:152(PlayPiece)
16119246 3.518 0.000 3.518 0.000 NiyaButFaster.py:157(UnplayPiece)
913292 1.815 0.000 1.815 0.000 NiyaButFaster.py:161(NoPlays)
111644609 function calls (103331903 primitive calls) in 115.063 seconds
ncalls tottime percall cumtime percall filename:lineno(function)
6/1 0.000 0.000 115.063 115.063 {built-in method builtins.exec}
1 0.000 0.000 115.063 115.063 NiyaBut1D.py:1(<module>)
1 0.000 0.000 115.059 115.059 NiyaBut1D.py:335(SolveWrapper)
8312667/1 41.606 0.000 115.059 115.059 NiyaBut1D.py:159(Solve)
8312667 17.823 0.000 17.823 0.000 NiyaBut1D.py:98(FindPlayable)
15624817 11.643 0.000 11.643 0.000 NiyaBut1D.py:137(AddSmartScore)
9217152 11.163 0.000 11.163 0.000 NiyaBut1D.py:87(CheckBox)
15624817 7.325 0.000 11.128 0.000 NiyaBut1D.py:53(CreateBoardHash)
10229169 8.535 0.000 8.535 0.000 NiyaBut1D.py:59(CheckRow)
9595748 6.465 0.000 6.465 0.000 NiyaBut1D.py:68(CheckCol)
23937573 5.802 0.000 5.802 0.000 {method 'join' of 'str' objects}
9920327 3.446 0.000 3.446 0.000 NiyaBut1D.py:76(CheckDia)
868035 1.251 0.000 1.251 0.000 NiyaBut1D.py:123(NoPlays)
There are many permutations that will play the exact same way regardless on how it is represented in actuality. Each tile matches 6 others; 3 with letters and 3 with numbers. Therefore there are a lot of duplicate boards that are represented differently but play exactly the same. It would be possible to decrease the amount of time required to compute all boards by detecting these duplicates.
The follow are some ways a board that plays the same that are represented differently:
['A4', 'C3', 'D4', 'B4'] ['C1', 'A1', 'D3', 'A4']
['D3', 'D1', 'A2', 'B2'] =rotate=> ['C2', 'B3', 'D1', 'C3'] etc...
['A1', 'B3', 'B1', 'A3'] ['C4', 'B1', 'A2', 'D4']
['C1', 'C2', 'C4', 'D2'] ['D2', 'A3', 'B2', 'B4']
['A4', 'C3', 'D4', 'B4'] ['B4', 'D4', 'C3', 'A4']
['D3', 'D1', 'A2', 'B2'] =mirror=> ['B2', 'A2', 'D1', 'D3']
['A1', 'B3', 'B1', 'A3'] ['A3', 'B1', 'B3', 'A1']
['C1', 'C2', 'C4', 'D2'] ['C1', 'C2', 'C4', 'D2']
['A4', 'C3', 'D4', 'B4'] ['A4', 'C3', 'D4', 'B4']
['D3', 'D1', 'A2', 'B2'] =swap=> ['D3', 'D1', 'A2', 'B2'] etc...
['A1', 'B3', 'B1', 'A3'] ['A1', 'B3', 'B1', 'A3']
['C1', 'C2', 'C4', 'D2'] ['C1', 'C2', 'C4', 'D2']
['A4', 'C3', 'D4', 'B4'] ['A3', 'C2', 'D3', 'B3']
['D3', 'D1', 'A2', 'B2'] =swap=> ['D2', 'D4', 'A1', 'B1'] etc...
['A1', 'B3', 'B1', 'A3'] ['A4', 'B2', 'B4', 'A2']
['C1', 'C2', 'C4', 'D2'] ['C4', 'C1', 'C3', 'D1']
Perhaps there are more ways to represent the board differently but have them play in the exact same way. However based on the permutations I found this means every 4,608 boards are the same, leaving 4,540,536,000 unique boards.
Knowing that every 4600 boards are symmetrical is useless unless it can determine that the solution has been found and recall the score. So the question becomes how to represent 4608 different permutations of the same information in a concise and limited way. One way that I came up with would to be to represent each spot with what they match with. This could be condensed down to 16 bits for each of the 16 tiles. If I were to calculate all the boards that are possible without recalculating something that I already have because of Group Theory I would want a way to present a board that maximizes find-ability. A board can be hashed independently of the content of how it is required to show the board for use and playability. The hash would require 16 bits for each spot on the board.
['A4', 'C3', 'D4', 'B4'] 'A4' would be represented as 0011001010010010
['D3', 'D1', 'A2', 'B2'] Continue this for each space
['A1', 'B3', 'B1', 'A3']
['C1', 'C2', 'C4', 'D2']
This solution fixes how the data is represented in terms of playability, however this solution is not rotationally independent. This hash would need to be generated eight times; one for each rotation and mirrors.
If space is the concern it could be further reduced by removing each tiles own bit since a tile won't ever match itself. This would make rotating the board more difficult. Another way to shrink the hash is by understanding that information is duplicated in the hash. Using the example above, the hash of A1, A2, A3, B4, C4, D4 would all point back to A4. The hash could remove A4, and it's 16 bit of space, and not lose it's uniqueness. The question then becomes how do you hash that in a consistent way to find all 4600 boards.
If I were to start calculating every unique board it would take about 9000 years to run and 300 Gbs of space to store.
If I were to calculate all 4.5 billions boards on my computer at a minute per board, it would take 8,700 CPU years to finish.
For the moment it's hashing every board that it calculates. This takes up about 2Gb worth of memory for each board. I can exchange that space for time by only hashing boards before turn 8. This would lose me a few seconds for each board, but gain about 1.5Gb of memory. Calculating all the board states won't be feasible in memory and would require a database to refer to and would add to the time and space overhead.
If each board can be hashed in 32 bytes, it would take about 136Gb to just store each board. This does not include the first few moves or overhead. This hash would be content independent, however it would be rotational dependent, and would require to hash each board 8 times; one for each rotation with mirror.