The goal of this article is to study the contribution of FCA (Formal Concepts Analysis) to (1) optimize (2) organize (3) discover new concepts or a better operation of the semantic memory of an Arti cial Intelligence (AI) system based on a cognitive approach. The system has been applied to game modeling (here the Reversi board game), since games are a very good experimental eld for performance evaluation. After describing the COGITO project, which tries to assess the pros and cons of cognitive modeling over pure operational but non explicative paradigms in games modeling, the paper stresses out the bene ts of FCA in providing a better abstraction, and a more reliable way to handle con ictual knowledge.
One of the old dreams of Arti cial Intelligence (AI) was to substitute humans with AI systems, in most of the chores involving problem solving. During the past fty years, two methodological tracks have been extensively explored: Either imitating human behavior, a trend that naturally leads researchers to mimic the human cognitive structure, seen as the outcome of a natural selection [9]; Or definitely assessing that humans and computers are utterly di erent, and designing algorithms tted to machines, thus bypassing human skills in problem solving [12]. If the rst trend seems nowadays set aside because of its too many failures, this paper attempts to revive some of its claims, by constraining the project to a very simple task. This task, a REVERSI board game [7], has interesting basic properties: { In a cognitive approach, games require di erent mechanisms: Capturing an input, trying to map it with the present memory state, learning it if new, and exploiting the integrated shape through reasoning when playing a new game. Thus, the behavior of a cognitive-based system could easily be tracked in its di erent steps. { A totally di erent approach, the Minimax (also called the Von Neuman theorem, [11]), has given very good results. However, the Minimax is a way to win in a zero sum play, not a way to learn or to understand. { This situation enables the evaluation of the pros and cons of a cognitive approach, versus a pragmatically performant but non explicative method, for a given task (even if more or less biased).
This paper describes a part of a more extensive project named COGITO
(both a research team, and an implemented software), restricted to the
management and operation of the semantic memory , and the mechanisms that acquire
(i.e. learn) or exploit (i.e. play) the knowledge required to learn to play a Reversi
game.These aspects are implemented and functional. The goal of this article is,
after describing the founding assumptions and the selected cognitive model, to
study the contribution of FCA (Formal Concept Analysis) to (
Designing a Reversi Board Game and Player In a computational framework, the play has been modeled with predicates that are the founding elements which compose these noteworthy patterns. The retained basic predicates are the following: 1. isM ine(x): For the system, its own pieces 2. isOpp(x): The adversary's pieces 3. isEmpty(x): A position on the board which can possibly be occupied by a next move 4. isEdge(x): A noteworthy position on the edge of the board. The piece that occupies it is harder to take. 5. isCorner(x): Also a noteworthy position. 6. near(x; y): De nes neighborhood. Might lead to a capture, if x are not of the same color as y. 7. aligned(x; y; z): Three pieces on a same line, either vertical, horizontal, or even a diagonal. Allows to capture the two other pieces, if z is not of the same color as x and y.
To implement the game, one needs to: { Acquire the board 'state', also called the board con guration. It requires the coordinates of all pieces, and which predicates each piece instantiates. { Map the present board to a set of stored noteworthy patterns that express playing strategies. { Choose the best and thus perform a move. { Learn moves from the other player in order to enhance the system abilities.
NA cAodnvcaenpcteudal CBASIMRXTAIONCCESTP NNGAYSSEELII cRoaaueennnBnlncaeaaggellysiyiBpnnisscteoieiussoakl COMOARTDRINIXATES
INPUT
Stimulus MEMORY Primary mEYRUQemoryNORSSPEE Memory
REASONING ENGINE Introspection Decision making
DNDCAAEV ONCCSETP
OUTPUT ENVIRONMENT Coordinates(x,y) The theoretical computational model underlying the design of such a requirement set is provided in gure 2. The board is described as a matrix, and is transmitted, from the environment to the Rulebook module, through an I/O module. The latter determines all the possible moves, and generates the set of all resulting matrices, to be transmitted to the Basic Conceptual Analyzer. This package transforms the matrices into a logical set of rst order formulas, using the basic predicates de ned above. The outcome is a set of facts in a logical format, transmitted to the Advanced Conceptual Analyzer. The latter maps the possible patterns of the board with the already stored noteworthy patterns. Then, it launches the reasoning module which chooses between the possible moves, according to the set of board con gurations and recognized noteworthy patterns. This choice is based on an evaluation associated with the pattern, representing the number of times it has gured in a winning game (in the form of a 'probability of winning' with the appropriate formula). This cognitive structure schema has been largely inspired from the 'arti cial consciousness model' in [10]. The latter involves a much larger set of elements and relationships. The COGITO project work has mostly focused on the memory and reasoning parts of the model. As seen here, the primary memory is a temporary bu er that stores the results of perceived inputs (short term memory). The memory module contains two other parts: An episodic memory, storing games and moves as they have been played during di erent sessions, and the semantic memory, keystone of this contribution. Both have exactly the same structure, and the episodic memory content is 'appended' to the semantic memory. 3 3.1
The Semantic Memory Structure
Memory as a Graph Structure
The semantic memory stores:
(
The graph representation has been implemented here with a graph oriented
ATTRIBUTE
RPBS
RELATED
OBJECT
CBS DBMS (an open source system called Neo4j), and exploited. It works quite well in most of the cases.
However, observation has shown the following liabilities, that were transformed into requirements for an FCA modeling: { The abstraction level is quite low, and still too close to the operational requirements of the game. { When reasoning on patterns as pure attributes, any composition of patterns inherits the valuation of its members. For instance, if two 'winning' RPBS, when associated, could generate a con ict, the present approach would not detect it. { It is possible that the information appended from the episodic memory and some already existing parts of the semantic memory, turn out to be redundant. The present model does not prevent such a situation, neither does it cure it. 3.2
The Contribution of FCA to the Semantic Memory
Organization FCA (Formal Concepts Analysis) [6] helps organizing and structuring information presented as a collection of objects and their properties. Figure 3 shows that the semantic memory content is a very good candidate for such a design. Thus, it has been performed on the CBS/RPBS matrices presented in Figure 3, using Concept Explorer (Conexp, [13]) an open source concept lattice builder. A recent work on a neighboring application, related to semantic neural decoding [5] has encouraged such an attempt. Human cognitive structures are neural, and an imitative model, such as our Cognitive Semantic Memory, would probably bene t from the same achievements. The discussed improvements are those described in the following subsections.
Reducing Redundancy, Optimizing Decision Making, Evaluating Patterns Quality and Discovering New Patterns In Figure 6, three concepts introduce more than ve noteworthy patterns (RPBS). This helps to reduce redundancy, as mentioned previously, by merging these patterns into one, without any loss of information on the whole set of acquired data. Let us note that FCA concepts are sets of CBS sharing the same properties. This means that games could be put into categories, and a classi cation of winning games and their hierarchy, can be extracted from this work (see next subsection).
Also, a hierarchy among the RPBS seems to appear. This might lead to a more intelligent search on the matching RPBS (in the reasoning module of Figure 2) by reducing the number of homomorphisms applied to each board. Thus, the decision making might take less time, without reducing the number of RPBS in the search space.
The RPBS introduced in the parent concepts of a common concept (introducing at least one CBS) have potentially a common subpart, that could be extracted as a new (and e cient) RPBS (see Figure 7).
Also, RPBS have been weighted, in the COGITO system, according to their presence frequency in winning, respectively losing games. We have tried to build lattices based on this feature. Figure 8 shows the organization of the winning games. Such a piece of information is crucial since it might help modifying the RPBS weights.
Discovering New Rules and Strategies Moreover, and unexpectedly,
Conexp has helped us nd rules featured as follows, that might be caused by
inclusions of RPBS:
where:
r < n > RP BSid(w) =>< m > RP BSid1; RP BSid2; :::RP BSidk
(
This means that beyond the relationships between concepts (CBS) and attributes (RPBS), FCA helps discovering possible dependancies amongst attributes themselves, leading to a re-design of the noteworthy pattern notion. Samples of Derived Rules 1 < 7 > RPBS2451946951846987668P [100 \%] ==> < 7 > RPBS-4298734809266812793P RPBS5155796358318376653P RPBS-332696813166452205P RPBS-7263297845748811357P
RPBS2695868336796769590P RPBS844283409270944352P; [..] 58 < 20 > RPBS6368401393598113686G [95 \%]=> < 19 > RPBS617699568208265822G; [..] The experiment has shown that FCA can provide very interesting modi cations to the initial memory structure. For the moment this step has not been automated, because we wanted to evaluate FCA added value: indeed, it has improved the quality and reliability of the acquired knowledge. However, FCA must not be run on a learning system, since it would bias the learning step (when the system acquires new RPBS and CBS from games played against a human player). The general idea is to re-design the memory with FCA, and this time, automatically, but only after a reasonable number of games where the memory has more or less acquired elements, and to rerun FCA only until another quite large number of games have been played. During the game step, it would be valuable to store the ongoing CBS in a concept. Concepts can be 'weighted' with values expressing their reliability. Thus the ongoing CBS can inherit its parent concept present weight and, bene ting from the lattice structure, drastically reduce the number of possible RPBS (in the reasoning module). Also, it would be interesting to constantly check stabilization in learning, in order to build a sort of a nal lattice, which will represent a stable and 'mature' state of the semantic memory. We also anticipate that the nal number of concepts will also stabilize. A future experiment will be performed to determine the nal lattice size.