Bruteforce creation of a map for the GAR

So this article will be in english since it could interest people just for the code.

Little summary : I have my little game : a Game About Rectangles, I wanted to measure how people are going to solve each game.  My goal was to find a strategy that is not necessarily correlated with the performance (i.e. defined as the time to solve the level).  The first insight was that a player can either think and play (therefore a little amount of moves, but rather slowly) or play more impulsively (therefore a high amount of moves, but quicker). The utopia was to think that the number of moves and the time wouldn’t be highly  correlated. Obviously, I found through the different levels of increasing difficulty a correlation that goes over .7 most of the time.

It makes sense that people tending to spend more time to solve a problem also tend to do more moves. Therefore, finding that easily (with only two variables by level) something that could be the strategy of the individual was unrealist.

Talking with my supervisor, we conclude that I should go deeper in the behavior of the player. In particular, what is the quality of the move, what was the time before this particular move ? Can we observe some pattern of behavior (some clusters of « thinking/inaction » and some clusters of « action » that are useful). To do all that, something was necessary. To be able, for every situation of each level, to find the quickest way to the solution. The challenge begins here.

People often think programming is science : they see complicated code and they think « wow, not for me ! » What I discovered, is that the first pedagogic approach when teaching programming is explaining the plurality of the solution. People get stuck when they think « there is one way, how can I discover it ? » Maybe there is one single most efficient way, but you can achieve well enough with a more « crafted » code.

That’s precisely what I love about programming : you have to design your conceptualization of the situation. How to put the problem on the paper ? You quickly find that programming relies on a high level of creativity (yes, I dare say that !).

So, let’s review quickly the conceptualization of the game.

  • A level is one given set of pieces, defined by their position at the beginning. A level ends when you manage to drag the red rectangle out of the 6×6 board.
  • A state is a particular position for each rectangles of our level
  • A move is what you can do with only one click : dragging one rectangle to a different spot

The goal : being able to tell, for each state (of an individual’s path to solve the problem) how many moves are needed to finish the level.

My first idea was to define what is a finite state (red rectangle on cases row 3 and col 5-6) and to bruteforce every possible move until reaching a finite state. But, I quickly found that there was a problem. Some levels are solvable in 20 moves. At each state, you have about 10 different possibles moves. It yields that the algorithm is going to calculate 10^20 different states… No gooderino.

Some thinking later, a guy gave me a great help. Florent Garcin accepted to meet me to give me some precious piece of advice. He came up with the idea that solves everything : the number of states are finite. The number of moves you can do are infinite, but often, you will visit an already known state. Therefore, there is no need to perform action on this state. The goal then was to create a MAP of the level. Each point would be a state and each point will be connected to several other states. When two states are linked, it means that you can go from one to another in only one move. Some states (points) are finite, it is then easy to know, for any state, how close you are from a solution.

Now, let’s look at the code

Step 1 : what defines a state ? Pieces type (vertical, horizontal ? small, big ?) and pieces position.

p1=c(2,1,3,2)
p2=c(2,1,1,1)
p3=c(2,1,5,5)
p4=c(3,1,6,3)
p5=c(3,2,2,1)
p6=c(2,2,5,1)
p7=c(3,2,1,6)
p8=c(3,2,2,4)

lvl1=rbind(p1,p2,p3,p4,p5,p6,p7,p8)

We can define then define a matrix n x 4, where n is the number of pieces. The first number describes the size of the piece (2 cases or 3), the second number defines the horizontality (1) or verticality (2), the third describes row position and the fourth the column position.

Then, we want to draw on a board similar to our game those information :

DrawBoard=function(pice){
board=matrix(0,6,6)
for (i in 1:dim(pice)[1]){
taille=pice[i,1] # size of the piece
x=pice[i,3]
y=pice[i,4]
if(pice[i,2]==1){ # if the pieces i is horizontal
board[x,y:(y+taille-1)]=i # we add something to the case on the right (next column)
} else if (pice[i,2]==2) { # if vertical
board[x:(x+taille-1),y]=i # we add something to the case below (next row)
}
}
board}

> DrawBoard(lvl1)
[,1] [,2] [,3] [,4] [,5] [,6]
[1,]   2   2   0   0   0   7
[2,]   5   0   0   8   0   7
[3,]   5   1   1   8   0   7
[4,]   5   0   0   8   0   0
[5,]   6   0   0   0   3   3
[6,]   6   0   4   4   4   0

Step 2 : we have to know which moves are possible

Now we have a Board that describe the free slot (0’s) and the occupied slot (non 0) and which piece occupies the slot (piece number). Then our goal will be to perform all possible action on each piece. There is 4 possibles action : going down ; up ; left  or right. Obviously horizontal pieces will only be checked for left or right and vertical pieces for down and up.

Little glossary : NextPieces is our list of all different states (it consists in several matrix of n x 6) ; Path describes how states are connected.

checkup=function(){
# COLboard=initboard[,temppieces[i,4]] #performs on a specific pieces that is vertical : we check the column of the piece
ROW<<-temppieces[i,3] #the row of the piece if(ROW>1){ ##if the row of the piece is 1, then it is all the way up and we can't go higher
if(initboard[(ROW-1),COL]==0){ #if the upper slot is 0 then it is free and we can go up !
temppieces[i,3]< if(AlreadyFound(temppieces)==TRUE){Path[[tempindex]]<<-c(Path[[tempindex]],Ind)} else {
### Very important line : we check if the new state is already found, if it is not we add it to the list, if it already exists we will connect the states we are working on to the state that already exist (they are connecting themselves in one move)
NextPieces<<-lappend(NextPieces,temppieces) # NextPieces is the list of states
Path<<-lappend(Path,c(Ind))
dico<<-lappend(dico,stringstate)

}
checkup()} #this function has to be recursive. Indeed, a piece can go several slots up if they are all free.
}}

The <<- sign is very important in R, it allows to define a global variable (a variable that exists outside the function scope)

Obviously, we have four of these functions that we won’t present for parcimony.

Step 3 : We have to know which are the next possible states of a given state

We just saw the functions that analyse the possible moves of a specific piece. We now want to apply that to every pieces of a given state. Somehow I didn’t manage to find a way to not put a for here… I did not want to lose too much time and the function is quite efficient, but still, I used a for loop in R.

shame

So, here is the function that performs « OneMove » and try all different possibilities on a state.

OneMove=function(pice){ #Pice is here the n x 6 matrix we know (element of the NextPieces list)
Ind<<-Ind+1 #each time we perform a one move, we work on another state. Therefore the Ind global variables keep track of which state we are working on, it is necessary in order to link the different state when they are connected by "OneMove".
picec<<-pice
if (IsFinal(picec)==TRUE){} else {
for (i in 1:dim(picec)[1]){
temppieces<<-picec
i<<-i
initboard<<-DrawBoard(temppieces)
COL<<-temppieces[i,4]
ROW<<-temppieces[i,3]
if(picec[i,2]==1){ ##if the piece is horizontal, we check right and left
checkright()
temppieces<<-picec
checkleft()

} else if (picec[i,2]==2) { ## if vertical, we check up and down
checkdown()
temppieces<<-picec
checkup()

}}
}}

Alternative step : a quick presentation of « necessary but uninteresting functions »

First, we need a function that tells us if a state already exist in our dictionnary. What changes between two states : only the third and fourth column (i.e.position of pieces ; their size and direction is stable). We can then use a toString of these variables and apply to the dictionnary the equality :

AlreadyFound=function(pice){
stringstate<<-toString(pice[,3:4])
tempindex<<-which(lapply(dico, function(x) x==stringstate)==TRUE)
length(tempindex)!=0
}

We save tempindex because, let’s say with state 454, we obtain a new state, already existing : the state 322, we have to tell somehow that 454 and 322 are connected. That’s the role of what we saw in the « checkup » function : Path[[tempindex]]<<-c(Path[[tempindex]],Ind)

Then, we want a function that tells us if the state is final

IsFinal=function(pice){
pice[1,4]==5 ##base of first piece (red rectangle) is on 5th column.
}

A function to add an element to a list (it doesn’t exist in base R)

lappend lst[[length(lst)+1]] return(lst)
}

 

Step 4 : Compute all states !

It is quite simple, we just have to run OneMove on the basic state, then OneMove on the states that we just created, eventually, the system don’t find anymore new « state » and we can comfortably say that the level is mapped.

ComputeAllStates=function(lvlmat,depth){
NextPieces<<-list(lvlmat)
Ind<<-0
tempindex<<-NULL
Path<<-list(c())
dico<<-list(toString(lvlmat[,3:4]))
prevsize=0
for (i in 1:depth){
size=length(NextPieces)
diffsize=size-prevsize
lapply(NextPieces[(prevsize+1):size],OneMove)
prevsize=size
print(length(NextPieces))
}
}

Step 5 : Create the map

To create our network we used a powerful package ‘igraph’. So, let’s go on with our example. We have 1079 states in the first level. Each of these states are obviously connected to other states. We stocked this information in the list ‘Path’.

> head(Path,3)
[[1]]
[1] 2 3 4 5 6 7 8 9 10 11 12

[[2]]
[1] 1 3 4 13 14 15 16 17 18 19 20 21

[[3]]
[1] 1 2 4 22 23 24 25 26 27 28 29

Easily readable : the index of the list ([[1]]) means state 1 is connected to the element of his vector. The library ‘igraph’ wants a matrix L*2 where L is the number of connections (1-2 is one connection). A quite simple function allows me to go from Path to what I call « PotLinks »

GetPossiblesLinks=function(mypath){
potlinks=NULL
for (i in 1:length(mypath)) {
potlinks=rbind(potlinks,cbind(rep(i,length(mypath[[i]])),mypath[[i]]))
}
potlinks
}

Then a bit of uninteresting code :

PotLinks=GetPossiblesLinks(Path)
finalornot=as.numeric(lapply(NextPieces,IsFinal))
finalornot[1]=-1 ## c'est le starting point


clr=NULL
for (i in 1:length(V(mynet))){
if (finalornot[i]==1) {clr[i]="red"} else if(finalornot[i]==0) {clr[i]="blue"} else {clr[i]="yellow"}}
V(mynet)$color=clr
mynet=graph.data.frame(PotLinks,directed=F,vertices=data.frame(cbind(1:1079,finalornot)))
mynet=simplify(mynet,remove.multiple=T)

That yields to the plot :

Rplot

Now we already won, the network system is here very powerful and the last two things we need to do are trivial. We need to find which for every move a player does in which state he is. It is quite easy because we just need the coordinates of the pieces. And we need to find the quickest path to a final state which is preprogrammed in the package ‘igraph’. Let’s take a look :

theindexes=get.shortest.paths(mynet,V(mynet)[1],V(mynet)$color=='red')[[1]][1]

There, theindexes stocks the different states composing one of the most efficient way to solve the level. We can draw them for fun.

library(RColorBrewer)
pdf(height=6*length(dessin), width=6)
par(mfrow=c(length(dessin),1))
for(i in 1:length(dessin)) {
image(t(dessin[[i]])[1:6,6:1],col=c("white",brewer.pal(9, "Paired")), axes=F,bty="o")
box()
}
dev.off()

Thanks for reading !

Rplots