Deep Space O'Brien is a game for the IBM Quantum Experience. To play, first set up a free account here, then go to the Jupyter notebook dashboard here and create a new notebook. Once that's all done, you just need to dump the following code in a cell and run it!
from qiskit_textbook.games.qiskit_game_engine import QiskitGameEngine
import numpy as np
import random
import networkx as nx
################
# The following section is QuantumBlur (copyright IBM 2020)
# Parts that aren't needed have been removed
# See the link below for the full version
# https://github.com/qiskit-community/QuantumBlur
import math
from qiskit import QuantumCircuit, quantum_info
simple_python = False
def _kron(vec0,vec1):
new_vec = []
for amp0 in vec0:
for amp1 in vec1:
new_vec.append(amp0*amp1)
return new_vec
def _get_size(height):
Lx = 0
Ly = 0
for (x,y) in height:
Lx = max(x+1,Lx)
Ly = max(y+1,Ly)
return Lx,Ly
def _circuit2probs(qc):
if simple_python:
probs = simulate(qc,get='probabilities_dict')
else:
# separate circuit and initialization
new_qc = qc.copy()
new_qc.data = []
initial_ket = [1]
for gate in qc.data:
if gate[0].name=='initialize':
initial_ket = _kron(initial_ket,gate[0].params)
else:
new_qc.data.append(gate)
# then run it
ket = quantum_info.Statevector(initial_ket)
ket = ket.evolve(new_qc)
probs = ket.probabilities_dict()
return probs
def _image2heights(image):
Lx,Ly = image.size
heights = [{} for j in range(3)]
for x in range(Lx):
for y in range(Ly):
rgb = image.getpixel((x,y))
for j in range(3):
heights[j][x,y] = rgb[j]
return heights
def _heights2image(heights):
Lx,Ly = _get_size(heights[0])
h_max = [max(height.values()) for height in heights]
image = newimage('RGB',(Lx,Ly))
for x in range(Lx):
for y in range(Ly):
rgb = []
for j,height in enumerate(heights):
if (x,y) in height:
h = float(height[x,y])/h_max[j]
else:
h = 0
rgb.append( int(255*h) )
image.putpixel((x,y), tuple(rgb) )
return image
def make_line ( length ):
# number of bits required
n = int(math.ceil(math.log(length)/math.log(2)))
# iteratively build list
line = ['0','1']
for j in range(n-1):
# first append a reverse-ordered version of the current list
line = line + line[::-1]
# then add a '0' onto the end of all bit strings in the first half
for j in range(int(float(len(line))/2)):
line[j] += '0'
# and a '1' for the second half
for j in range(int(float(len(line))/2),int(len(line))):
line[j] += '1'
return line
def normalize(ket):
N = 0
for amp in ket:
N += amp*amp.conjugate()
for j,amp in enumerate(ket):
ket[j] = float(amp)/math.sqrt(N)
return ket
def make_grid(Lx,Ly=None):
# set Ly if not supplied
if not Ly:
Ly = Lx
# make the lines
line_x = make_line( Lx )
line_y = make_line( Ly )
# make the grid
grid = {}
for x in range(Lx):
for y in range(Ly):
grid[ line_x[x]+line_y[y] ] = (x,y)
# determine length of the bit strings
n = len(line_x[0]+line_y[0])
return grid, n
def height2circuit(height, log=False, eps=1e-2):
# get bit strings for the grid
Lx,Ly = _get_size(height)
grid, n = make_grid(Lx,Ly)
# create required state vector
state = [0]*(2**n)
if log:
# normalize heights
max_h = max(height.values())
height = {pos:float(height[pos])/max_h for pos in height}
# find minimum (not too small) normalized height
min_h = min([height[pos] for pos in height if height[pos] > eps])
# this minimum value defines the base
base = 1.0/min_h
for bitstring in grid:
(x,y) = grid[bitstring]
if (x,y) in height:
h = height[x,y]
if log:
state[ int(bitstring,2) ] = math.sqrt(base**(float(h)/min_h))
else:
state[ int(bitstring,2) ] = math.sqrt( h )
state = normalize(state)
# define and initialize quantum circuit
qc = QuantumCircuit(n)
if simple_python:
# microqiskit style
qc.initialize(state)
else:
qc.initialize(state,range(n))
qc.name = '('+str(Lx)+','+str(Ly)+')'
return qc
def probs2height(probs, size=None, log=False):
# get grid info
if size:
(Lx,Ly) = size
else:
Lx = int(2**(len(list(probs.keys())[0])/2))
Ly = Lx
grid,_ = make_grid(Lx,Ly)
# set height to probs value, rescaled such that the maximum is 1
max_h = max( probs.values() )
height = {(x,y):0.0 for x in range(Lx) for y in range(Ly)}
for bitstring in probs:
if bitstring in grid:
height[grid[bitstring]] = float(probs[bitstring])/max_h
# take logs if required
if log:
min_h = min([height[pos] for pos in height if height[pos] !=0])
alt_min_h = min([height[pos] for pos in height])
base = 1/min_h
for pos in height:
if height[pos]>0:
height[pos] = max(math.log(height[pos]/min_h)/math.log(base),0)
else:
height[pos] = 0.0
return height
def circuit2height(qc, log=False):
probs = _circuit2probs(qc)
return probs2height(probs, size=eval(qc.name), log=log)
################
def create_maze(L,threshold,fraction):
# create a heightmap with L random points
height = {}
for x in range(L):
for y in range(L):
height[x,y] = 0
for _ in range(L):
x = random.choice(range(L))
y = random.choice(range(L))
height[x,y] = random.random()
# apply a blur effect
qc = height2circuit(height)
for j in range(qc.num_qubits):
qc.rx(np.pi*fraction,j)
height = circuit2height(qc,log=True)
# determine what is wall and path (and make a wall around it all)
maze = {}
for x in range(L):
for y in range(L):
if x in [0,L-1] or y in [0,L-1]:
maze[x,y] = 1
else:
maze[x,y] = int(height[x,y]>threshold)
# get the graph corresponding to the total maze
G = nx.Graph()
for x in range(L):
for y in range(L):
if maze[x,y]==0:
for (xx,yy) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if (xx,yy) in maze:
if maze[xx,yy]==0:
G.add_edge((x,y),(xx,yy))
# find subgraph that forms the largest connected component
g = G.subgraph(max(nx.connected_components(G), key=len)).copy()
# find start and end: a pair of vertices with maximum distance
e = nx.eccentricity(g)
d = nx.diameter(g,e)
ext = []
for v in e:
if e[v]==d:
ext.append(v)
start = ext[0]
for v in ext[1:]:
if nx.shortest_path_length(g,start,v)==d:
end = v
return maze, start, end, d
L = 32
threshold = 0.5
fraction = 0.125
def start(engine):
try:
engine.lastpath = [pos for pos in engine.path]
except:
engine.maze, engine.startpoint, engine.endpoint, engine.max_steps = create_maze(L,threshold,fraction)
engine.max_steps += 2
engine.lastpath = []
print('==============================================')
print('== Deep Space O\Brien: Season 5, Episode 18 ==')
print('==============================================\\n')
print('Captain\'s log, stardate 98358.97.\\n')
print('We are in orbit around a planet whose surface seems to be interfering with our transporters.')
print('A shuttle is being sent down to investigate, and I\'ve decided to lead the away team myself.')
print('I haven\'t had to deal with any transporter issues since becoming captain, and I\'m starting to miss them.')
print('\\n')
print('Captain\'s log, supplemental.\\n')
print('It seems that the transporters aren\'t the only system to be affected by this planet.')
print('Time appears to be looping here, repeating the same few minutes over and over.')
print('One of these loops restarted on our way down, disrupting the shuttle\'s engines.')
print('It won\'t be taking off again.')
print('Our best chance of escape is to find one of the few stable points where we can attempt a beam out.')
print('Hopefully we can reach one before the loop restarts.\\n')
print('\\n')
print('How to play:\\n')
print('* You control the red pixel with the arrow buttons.')
print('* Try to find the blue pixel in as few steps as possible.')
print('* When you run out of steps, you\'ll start at the beginning again.')
print('* The text below the screen tells you how many steps are left. ')
print('* You can walk off the current screen where indicated by the arrows.')
print('* The path you took during the last loop will be highlighted.\\n')
engine.step = 0
engine.path = []
engine.X = engine.startpoint[0]
engine.Y = engine.startpoint[1]
engine.success = False
for button in ['up','down','left','right','A']:
engine.controller[button].value = False
next_frame(engine)
def next_frame(engine):
if not engine.success:
dX,dY = 0,0
if engine.controller['up'].value:
dY = -1
if engine.controller['down'].value:
dY = +1
if engine.controller['left'].value:
dX = -1
if engine.controller['right'].value:
dX = +1
if engine.maze[engine.X+dX,engine.Y+dY]!=1:
engine.X += dX
engine.Y += dY
if (dX,dY)!=(0,0):
engine.step += 1
engine.screen.pixel['text'].set_text('Find a good beam out location in '+str(engine.max_steps-engine.step)+' steps or the time loop will restart.')
engine.path.append((engine.X,engine.Y))
for x in range(engine.L):
for y in range(engine.L):
X = int(np.floor(engine.X/engine.L)*engine.L+x)
Y = int(np.floor(engine.Y/engine.L)*engine.L+y)
engine.screen.pixel[x,y].set_text('')
if (X,Y) in engine.maze:
if engine.maze[X,Y]==1:
engine.screen.pixel[x,y].set_color('orange')
elif engine.maze[X,Y]==0:
engine.screen.pixel[x,y].set_color('green')
if (X,Y)==engine.endpoint:
engine.screen.pixel[x,y].set_color('blue')
else:
engine.screen.pixel[x,y].set_color('grey')
if (X,Y) in engine.lastpath:
engine.screen.pixel[x,y].set_brightness(False)
else:
engine.screen.pixel[x,y].set_brightness(True)
for x in range(engine.L):
X = int(np.floor(engine.X/engine.L)*engine.L+x)
Y0 = int(np.floor(engine.Y/engine.L)*engine.L)
if (X,Y0-1) in engine.maze:
if engine.maze[X,Y0]==0 and engine.maze[X,Y0-1]==0:
engine.screen.pixel[x,0].set_text('↑')
if (X,Y0+engine.L) in engine.maze:
if engine.maze[X,Y0+engine.L-1]==0 and engine.maze[X,Y0+engine.L]==0:
engine.screen.pixel[x,engine.L-1].set_text('↓')
for y in range(engine.L):
X0 = int(np.floor(engine.X/engine.L)*engine.L)
Y = int(np.floor(engine.Y/engine.L)*engine.L+y)
if (X0-1,Y) in engine.maze:
if engine.maze[X0,Y]==0 and engine.maze[X0-1,Y]==0:
engine.screen.pixel[0,y]._button.description += '←'
if (X0+engine.L,Y) in engine.maze:
if engine.maze[X0+engine.L-1,Y]==0 and engine.maze[X0+engine.L,Y]==0:
engine.screen.pixel[engine.L-1,y]._button.description += '→'
engine.screen.pixel[engine.X%engine.L,engine.Y%engine.L].set_color('red')
if (engine.X,engine.Y)==engine.endpoint:
engine.success = True
next_frame(engine)
else:
if engine.step==engine.max_steps or engine.controller['A'].value:
for x in range(engine.L):
for y in range(engine.L):
engine.screen.pixel[x,y].set_color(random.choice(['red','blue','green','orange']))
start(engine)
else:
smile = [
'DDOOOODD',
'DOOOOOOD',
'OOBOOBOO',
'OOBOOBOO',
'OOOOOOOO',
'OOROOROO',
'DOORROOD',
'DDOOOODD'
]
officer = [
'DoooooDD',
'oOOOOODD',
'OOBOBODD',
'DOOOOODO',
'dddddddr',
'rrrrrrrD',
'OdddddDD',
'DddDddDD'
]
image = officer
for x in range(engine.L):
for y in range(engine.L):
engine.screen.pixel[x,y].set_brightness(True)
engine.screen.pixel[x,y].set_text('')
if image[y][x] in ['d','D']:
engine.screen.pixel[x,y].set_color('grey')
if image[y][x] in ['r','R']:
engine.screen.pixel[x,y].set_color('red')
if image[y][x] in ['g','G']:
engine.screen.pixel[x,y].set_color('green')
if image[y][x] in ['b','B']:
engine.screen.pixel[x,y].set_color('blue')
if image[y][x] in ['o','O']:
engine.screen.pixel[x,y].set_color('orange')
engine.screen.pixel[x,y].set_brightness(image[y][x]==image[y][x].upper())
engine.screen.pixel[4,5].set_text('▲')
engine.screen.pixel['text'].set_text('Captain O\'Brien and the team made it out! Press A for another go!')
if engine.controller['A'].value:
engine.path = None
start(engine)
engine = QiskitGameEngine(start,next_frame,L=8)