Original CubeAI release

CubeAI

CSCI-B 351 final project with the goal of making an AI to solve a 2x2 cube and possibly scaling up to higher order cubes. The AI algorithms used are BFS, Better BFS (limit moves), A*, IDA*, and Mini (a minimizing version of MiniMax). There are 3 heuristics implimented: simpleHeuristic, hammingDistance and manhattanDistance. There is a GUI which shows a 2D and 3D cube inaddition to the move states and allows for people to try to solve the cube in an easy way.

How to run:

First make sure you have pygames installed by running pip install pygames. The simplest way to run the code is by running python main.py. To view the command line arguments type python main.py -h. This will show the help page which is shown below:

CubeAI
CSCI-B 351 final project with the goal of making an AI to solve a 2x2 cube and possibly scaling up to higher order cubes.
The AI algorithms used are BFS, Better BFS (limit moves), A*, IDA*, and Mini (a minimizing version of MiniMax).
There are 3 heuristics implimented: simpleHeuristic, hammingDistance and manhattanDistance. 

optional arguments:
  -h, --help  show this help message and exit
  --m False   Run manually (start gui) or run the AI first
  --n 2       The dimension of the cube (nxn)
  --s 5       How many times to scramble the cube
  --a ida*    Which AI algorithm to use: (bfs), (bbfs), (a*), (ida*), (mini)
  --h m       Which heuristic to use: (s)impleHeuristic, (h)ammingDistance, (m)anhattanDistance.

Example images:

3D 2X2 cube in GUI

2D 2x2 cube in GUI

Documentation:

Project structure

├── main.py                 # The main python script which runs all others and serves as the entry point
├── main_gui.py             # Main file that creates the gui
├── AIs.py                  # Python script with different AI algorithms for solving the cube
├── Heuristic.py            # Heuristics for solving the cube
├── Cube.py                 # The class which models the cube and methods to manipulate it
├── ManhattanCube.py        # Class used to represent the cube differently for the Manhattan Distance heuristic
├── tests.py                # Script used to generate test data CSVs found in the tests folder
├── project_files           # Files needed to submit this project such as proposals and formal documentation
├── tests                   # Folder containing the raw CSV test data for different AI algorithms and heuristics
└── unused                  # Contains currently unused and old files

main.py

This is the main file that gets ran. It can start the gui and allow humans to solve the cube or have different AIs solve the cube and show the results on the GUI. The simplest way to run the code is by running python main.py. The console will then walk you through the options. Additionally you can use command line arguments. The first argument is the size of the cube n (nxn), then the scramble length, next the AI algorithm (bfs, bbfs, a*, ida*, mini) and finally the heuristic ((s)impleHeuristic, (h)ammingDistance, (m)anhattanCube).

Dependencies: time, main_gui, AIs, Heuristic

# Start the gui
# n = the size of the cube
# scramble_length = how many scrambles should be made
gui(n, scramble_length)


# Run the specified AI algorithm and start the GUI to show the results
# type = a string specifying which AI algorithm to run
# n = size of the cube
# scramble_length = how many scrambles should be made
# heuristic = The Heuristic object reference that should be used by an applicable AI
ai(type, n, scramble_length, heuristic)

main_gui.py

This script handels all of the GUI work. To start a new GUI instance you must call GUI() and pass it a cube object. GUI has both 2D and 3D models for any nxn cube and can track the moves or make it easy to see the path an AI returned.

Dependencies: sys, math, pygame, time, operator, copy, Cube

class GUI: The main class used to render the data to the screen and handels user inputs and switching between 3D and 2D objects

# Creates a gui instance given a cube.  The width, height and wheather or not to use threeD can also be specified
# cube = cube instance to make a gui of
# width = 800 = the width of the screen
# height = 600 = the height of the screen
# threeD = True = a boolean indeicating if the GUI should open in 3D mode
__init__(cube, width=8--, height=600, threeD=True)

# Update and render the GUI using user input, must be called continuously
update()

# Draws the 2D cube to the screen
draw2DCube()

# Draws 3D cube to the screen
# vertices = verticies that result from the ThreeD_Cube
# faces = faces that result from the ThreeD_Cube
# colors = colors that result from the ThreeD_Cube
draw3DCube(vertices, faces, colors)

# Renderes the text box to the screen and all text.  Also handels word wrapping
renderText(self)

# Takes an AI path and lets users easily travers over this path
# path = the path returned from the AI algorithms
moveList(path)

class Point3D: Makes a point in 3 dimentions. Used to draw the 3D cube. This class was taken entirely from http://codeNtronix.com and developed by Leonel Machava leonelmachava@gmail.com

# Creates a point
# x = 0 = x cord
# y = 0 = y cord
# z = 0 = z cord
__init__(x = 0, y = 0, z = 0)

# Rotates the point around the X axis by the given angle in degrees. 
# angle = the angle the point should be rotated
rotateX(angle)

# Rotates the point around the Y axis by the given angle in degrees. 
# angle = the angle the point should be rotated
rotateY(angle)

# Rotates the point around the Z axis by the given angle in degrees. 
# angle = the angle the point should be rotated
rotateZ(angle)

# Transforms this 3D point to 2D using a perspective projection. 
# win_width = window width
# win_height = window height
# fow = field of view
# viewer_distance = how far away is the viewer
project(win_width, win_height, fov, viewer_distance)

__hash__()

__str__()

class ThreeD_Cube: Class that creates rectangles and moves the 3D cube

vertices = []
faces = []
colors = []

__init__()

# Methhod that takes in a cube state and colors and generates all of the 3DPoints needed to draw them to the screen
# cube = cube.state to be rendered
# color_bank = the color bank desired for each face
update(cube, color_bank)

AIs.py

Dependencies: heapq, time, Cube, Heuristic

All of the algorithms are classes that get initialized with cube objects and then return the path to the correct answer by running the solve method. The path is an array of tuples with the first index being the move made to get from the previous state to the current state and the second index being the current state. A sample path would look something like this:

path = [(None, cube_1), ((0,1), cube_2), ((1,3), cube_goal)]

class BFS: Runs BFS algorithm

# cube = Cube object to run BFS on
__init__(cube)

# timeout = float('inf') = How long the algorithm should run for before throughing a timeout error
# return path from initial cube state to solved state
solve(timeout=float('inf'))

class BBFS: Runs Better BFS algorithm

# cube = Cube object to run BBFS on
__init__(cube)

# timeout = float('inf') = How long the algorithm should run for before throughing a timeout error
# return path from initial cube state to solved state
solve(timeout=float('inf'))

class A*: Runs A* algorithm

# cube = Cube object to run A* on
# heuristic = Heuristic.manhattanDistance = Which Heuristic from Heuristic to run
__init__(cube, heuristic=Heuristic.manhattanDistance)

# timeout = float('inf') = How long the algorithm should run for before throughing a timeout error
# return path from initial cube state to solved state
solve(timeout=float('inf'))

# Find the path using State() given that A* has found the goal_state
# start_state = the initial State()
# end_state = the State() that contains the goal cube
# return the standard path output
find_path(start_state, end_state)

class Bidirectional_A_star: Not implimented. Don't grade.

class IDA*: Runs IDA* algorithm

# cube = Cube object to run IDA* on
# heuristic = Heuristic.manhattanDistance = Which Heuristic from Heuristic to run
__init__(cube, heuristic=Heuristic.manhattanDistance)

# timeout = float('inf') = How long the algorithm should run for before throughing a timeout error
# return path from initial cube state to solved state
solve(timeout=float('inf'))

# Perform iterative deepening operation
# path = Current path
# g = current depth
# bound = what the fValue can't exced
# times=(float('inf'),0) = a tuple with first index equal to the timeout and second index equal to the duration of the test
# return the minium value which is a tuple of solved, path, and fValue
search(path, g, bound, times=(float('inf'),0))

class Mini: Runs Mini algorithm. MiniMax but mini only

# cube = Cube object to run Mini on
# heuristic = Heuristic.manhattanDistance = Which Heuristic from Heuristic to run
__init__(cube, heuristic=Heuristic.manhattanDistance)

# depth = 2 = How deep to look before making a move
# timeout = float('inf') = How long the algorithm should run for before throughing a timeout error
# return path from initial cube state to solved state
solve(depth=2, timeout=float('inf'))

# Runs the mini alg on the current cube
# cube = the cube to run the alg on
# depth = how dep to look
# times=(float('inf'),0) = a tuple with first index equal to the timeout and second index equal to the duration of the test
# retrun a tuple of the best_move and best_score
mini(cube, depth, times=(float('inf'),0))

class State: Stores the state of the cube, parent cube and other information u...