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

Les styles cognitifs : concept VS mesures

Le but de cet article est de présenter brièvement mon projet de thèse en l’illustrant par un problème fréquent en psychologie : la différence entre un concept et une mesure. Cet énoncé, semblant être tout droit sortie d’un cours de méthodologie de base, n’est pas toujours intégré chez le chercheur.

L’exemple le plus flagrant que j’ai découvert jusqu’alors est le concept de style cognitif. Mince ! C’est justement mon sujet de thèse. Qu’est-ce que les styles cognitifs en deux mots ?

Historiquement, le concept apparaît lors de l’observation que les individus ne diffèrent pas que dans leurs performances globales à une tâche mais également dans la façon dont ils perçoivent, conceptualisent ou résolvent des problèmes (Witkin & Asch, 1948) .  En bref, il n’y a pas que l’aptitude (~qualité de traitement de l’information), mais il y a aussi une manière d’approcher l’information (~comment l’information est traitée).  Sans rentrer trop dans la définition du concept, il est simple de comprendre cette approche si l’on se base sur la dichotomie intuitif VS analytique. Le style analytique est rationnel, rigoureux, convergeant, séquentiel, réflexif et déductif. Le style intuitif serait divergeant, global, impulsif, inductif et créatif. (Kozhevnikov et al. 2014 ; Nickerson et al. 1985).

D’autres (Messick 1984) rajoutent que le style cognitif pourrait être un pont entre la personnalité et les aptitudes, les deux domaines les plus investis de la psychométrie. Historiquement, nous sommes face à un concept d’un nouveau type qui promet en terme de pouvoir explicatif et de nouvelles recherche.

Lors de l’explication de ce concept, je me retrouve souvent à devoir utiliser une définition simple mais pratique de Messick (1984) : la valeur d’un concept. Messick différencie un concept à valeur différenciée (~bipolaire) d’un concept à valeur directionnelle (~unipolaire). La valeur différenciée signifie qu’un pôle d’une dimension n’est pas généralement préférable (il n’est pas nécessairement mieux d’être extraverti qu’introverti). Par opposition, il sera toujours mieux d’être fort que faible. La force est donc un concept à valeur directionnelle. Le lecteur psychologue aura rapidement compris où je veux en venir : la personnalité est un concept à valeur différenciée, alors que les aptitudes sont à valeurs directionnelles.

VD

C’est maintenant que le concept des styles se corse. Si la manière d’approcher un problème (par exemple une approche analytique) est toujours préférable, alors le style cognitif est un concept à valeur directionnelle. Si résoudre un problème de manière analytique est toujours préférable, alors l’opposé (approche intuitive) ne peut qu’être moins bien.  Si c’était le cas, le concept perdrait beaucoup en intérêt car il ne serait probablement pas particulièrement différent de l’intelligence fluide.

Or, j’espère que j’arriverai à vous convaincre que ce pourrait être erroné. L’approche analytique est lente est méthodique l’approche intuitive est rapide et imprécise. Les économistes aiment bien l’opposé entre les métiers de management et d’analyse. Il est difficile de dire qu’un métier est hiérarchiquement supérieur à l’autre, bien que le travail soit complètement différent. D’une part, le manager se doit d’être rapide dans se prises de décisions, de réagir rapidement et d’être créatif dans ses solutions. L’analyste peut prendre le temps pour résoudre son problème. On se représente facilement qu’une approche analytique, lente pourrait ne pas être très adaptée au manager. Bref, c’est beaucoup de synthèse pour arriver à une situation archétypique, mais on voit l’idée.

Maintenant, disons que la valeur différenciée du style cognitif est acceptée, on peut continuer notre cours de méthodologie. On a un concept, il est innovant, il promet l’accès à plein de nouvelles recherches passionnantes, qu’est-ce qu’on fait ? On aimerait bien avoir un outil qui permette d’obtenir une mesure valide (qui mesure bien ce qu’elle prétend mesurer) et fidèle (elle est stable et reproductible).

Comment mesurer les styles cognitifs ? C’est une question qui n’est pas si évidente. En réfléchissant au concept, on se rend rapidement compte que le style cognitif se trouve dans le processus, dans la boîte noire. Comment l’information est traitée, quel est le raisonnement interne ? Ces informations ne sont pas faciles à saisir.

Plus pragmatiquement, en psychologie nous connaissons deux types principaux de tests : les tests de performance maximale (où l’on fait vrai ou faux) et les questionnaires. Il s’agit des outils respectifs des deux grands domaines d’investigation psychologique : les questionnaires pour la personnalité et les tests de performance maximale pour les aptitudes.

Historiquement, les premières mesures des styles cognitifs sont des tests de performance maximale. L’Embedded Figures Test (Witkin et al. 1971) ainsi que le Matching Familiar Figures Test de Kagan (1966).

Group Embedded Figures Test - sample item
Group Embedded Figures Test – sample item

Dans l’exemple d’item de l’Embedded Figures Test, nous voyons déjà apparaître une forme géométriquement simple (le triangle) et nous devons ensuite pouvoir le dessiner dans une forme géométriquement plus complexe dans un temps donné.  Nous pouvons nous questionner sur la validité conceptuelle, de tels tests. Effectivement, les réponses à cette catégorie de tests peuvent être objectivement catégorisées comme vraies ou fausses. Une question légitime est de nous demander s’il est possible qu’un score composé du nombre de questions répondues correctement puisse estimer un concept à valeur différenciée. Si tel était le cas, cela signifierait qu’un individu ayant répondu incorrectement à toutes les questions est comparable à l’individu qui a répondu correctement dans tous les cas. Ce postulat est difficile à défendre à la lumière des analyses factorielles « découvrant » le facteur général d’intelligence de Spearman (1904).

Dans ce courant de pensée, Weisz, O’Neill et O’Neill (1975) concluent dans leur étude que la validité discriminante (est-ce que le test mesure plus le concept désiré ou autre chose) est mauvaise et que l’objectif des chercheurs devraient être d’arriver à distinguer empiriquement les concepts de niveau cognitif (~aptitude) et de style cognitif.

Une année plus tard (coïncidence ? I think not), Kirton (1976) développe le premier questionnaire ayant l’ambition de mesurer les styles cognitifs. Il s’agit du Kirton-Adaptor-Innovator. De nombreuses autres mesures peu différenciées ont été développées. Comme il l’a déjà été mentionné, les questionnaires sont les outils typiques des mesures de la personnalité. Parallèlement, des critiques équivalentes existent : Von Wittich et Antonakis (2011) remarquent que la personnalité permet de prédire en grande partie le score au KAI et donc que l’utilité discriminante des styles cognitifs est très limitée (sic.). Moins négatif, j’espère que cette critique s’adresse principalement à la mesure par questionnaire et non au concept.

Dans ma première étude j’ai trouvé des résultats comparables aux découvertes de Von Wittch et Antonakis (2011). Le questionnaire que j’utilisais (CSI Allinson et Hayses, 1996) était prédictible en bonne partie (R^2=0.5) par la personnalité et le sexe.  De plus, les coefficients insinuaient que la dimension analytique-intuitif du CSI est très proche de la dimension Adaptor-Innovator du KAI.

Dans ma prochaine étude (résultats en juin 2016), j’essayerai de reproduire les résultats de Weisz, O’Neill et O’Neill (1975) en montrant que les mesures par performance maximale des styles cognitifs corrèlent plus avec un test d’aptitude qu’avec une mesure par questionnaire des styles cognitifs. Cela repose sur le postulat de Campbell et Fiske (1959) qui repose sur la démonstration que différentes mesures d’un concept devraient plus corrélés entre elles qu’avec des mesures d’un autre concept. Or, nous observerons probablement que ce n’est pas le cas.

En conclusion, il se pourrait que le problème de manque de résultats empiriques des styles cognitifs résultent simplement du fait que, jusqu’alors, les chercheurs ont échoué à mesurer les styles cognitifs dans ce qu’ils sont : un processus invisible à valeur différenciée.

model

Pour tenter de surmonter le problème de mesure, mon sujet de thèse est d’essayer de mesurer la manière dont un individu va jouer à un jeu de réflexion basique. Tel que le GAR inspiré du jeu RushHour. Le but serait de pouvoir mesurer un comportement proche d’une stratégie de jeu qui devrait, idéalement, être indépendant (pour respecter l’idée de valeur différenciée) de la performance au jeu (que nous définissons ici comme le temps nécessaire pour résoudre un problème). La première idée était de mesurer parallèlement le nombre de coups et le temps pour résoudre un niveau. Avec l’idée sous-jacente qu’un individu qui fait moins de coups est un individu qui réfléchit plus longuement avant de se lancer dans l’action, ce qui catégoriserait un individu analytique.

Il a malheureusement été découvert que le temps et le nombre de coups sont fortement corrélés (n’importe qui qui reste bloqué 3 minutes sur un niveau va faire exploser le compteur de coups). Il semblait donc nécessaire d’aller plus loin.deeper

Ce qui serait intéressant serait de connaître la « qualité » du coup (il peut rapprocher de la solution, éloigner, ou encore être nul) ainsi que le temps qui le précède. Il serait alors possible d’observer des cluster de comportement (temps de réflexion suivi de plusieurs actions utiles et rapides). Dans ce but, j’ai développé un algorithme permettant de mapper les niveaux qui sera décrit dans le prochain article !

Félix Cuneo

Allinson, C., & Hayes, C. (1996). The Cognitive Style Index, a measure of intuition-analysis for organizational research. Journal of Management Studies, 33, 119-135.

Kagan, J. (1966). Reflection-impulsivity : The generality and dynamics of conceptual tempo. Journal of Abnormal Psychology, 71 (1), 17-24.

Kirton, M. (1976). Adaptors and innovators: A description and measure. Journal of applied psychology, 61(5), 622.

Kozhevnikov, M., Evans, C., & Kosslyn, S. M. (2014). Cognitive Style as Environmentally Sensitive Individual Differences in Cognition A Modern Synthesis and Applications in Education, Business, and Management.Psychological Science in the Public Interest, 15(1), 3-33.

Messick, S. (1984). The nature of cognitive styles: Problems and promise in educational practice. Educational psychologist, 19(2), 59-74.

Nickerson, R., Perkins, D. & Smith, E. (1985). The teaching of thinking. Hillsdale, NJ: Erlbaum.

Spearman, C. (1904). « General Intelligence, » objectively determined and measured. The American Journal of Psychology, 15 (2), 201-292.

von Wittich, D., & Antonakis, J. (2011). The KAI cognitive style inventory: Was it personality all along? Personality and Individual Differences, 50(7), 1044–1049.

Weisz, J. R., O’Neill, P., & O’Neill, P. C. (1975). Field Dependence-Independence on the Children’s Embedded Figures Test : Cognitive Style or Cognitive Level ? Development Psychology, 11 (4), 539-540.

Witkin, H. A., & Asch, S. E. (1948). Studies in space orientation. IV. Further experiments on perception of the upright with displaced visual fields. Journal of Experimental Psychology, 38(6), 762.

Witkin, H., Oltman, P., Raskin, E., & Karp, S. (1971). A manual for the embedded figures test. Palo Alto, CA. : Consulting Psychologists Press.

 

Jeu comme outil psychométrique

Les styles cognitifs décrivent la manière dont un individu va recevoir et traiter l’information ou encore comment il résoudra un problème dans sa vie quotidienne. Il s’agit d’un processus. Les tests existants (questionnaires ou performances maximales) sont loin de mesurer un processus. C’est dans cette optique que je propose d’utiliser le jeu (vidéo) comme nouvelle approche des styles cognitifs. En effet, la performance de jeu peut être utilisée comme indicateur des aptitudes cognitives. Parallèlement, les stratégies de jeu peuvent être utilisées comme indicateur des styles cognitifs : est-ce qu’une personne jouera par essai et erreur, laissant une part au hasard, ou planifiera et jouera de manière stratégique pour atteindre plus sûrement son objectif ? D’autres articles, de type pédagogique (statistique et programmation) pourrait être trouvé sur ce carnet.