This essay will concern problem-solving and specifically how computational techniques can be used to solve problems. I plan to achieve this by constructing a game-playing agent and identifying the components that an agent would need to solve problems. This shall be done by describing how the agent might work in the abstract and a specific case. The specific case shall entail the agent’s ability to solve a game called ‘Scotland Yard’.
‘An agent is anything that can be viewed as perceiving its environment through sensors and acting upon its environment through actuators’ (Norving and Russell, 2013)3. All of the parts of an agent shall be discussed apart from the actuators. Primarily this essay is set to discuss strategy. However, without the ability to understand the task that the strategy is being developed for and having a method to extract information from that task any strategy developed would be limited.
Now a game is defined as follows “A form of competitive activity or sport played according to rules” (Oxforddictionaries.com, 2016)1. From this, we can discern that any game will be made up of four components. The first of which is the activity that shall take place, with that activity being competitive, and the second is the rules that will provide constraints. Now implicitly there is the need to have something or someone perform the competitive activity. Then finally there is the environment in which the game takes place.
A Game’s four components
1.
The Activity: What will take place during the
game.
2.
The Rules: Constrain how the activity is
performed.
3.
The Agent: An entity that will perform the
activity, in accordance with the rules.
4. The World: Place the agents will perform the activities. Like the rules, the world will place implicit restraints on how agents will perform activities.
The activity, rules and the world will collectively
be referred to as the environment. This will be the place in which an agent or
agents can perform activities. Splitting down both a game and an agent into
individual components is mainly inspired by Object Orientated Programming. For
Object orientated programming the following sequence is given (Horstmann,2010)4.
- . Discover classes
- . Determine the roles and responsibilities of each class
- . Describe the relationship between each class
Using this sequence to breakdown the agent into components and then describing the role of each of those components as well as creating a process that links all the components.
The specific game being used to describe the agent’s ability to solve problems is called Scotland Yard. Scotland yard is a board game that has two distinct activities. One is for a single agent to navigate a transport network and avoid agents that are searching for it. The other is for a group of agents, called ‘Detectives’, to search the transport network for the single agent, known in the game as ‘Mister X’. The network is a set of nodes and links that allow agents to move from one node to another. Each round every agent moves to a new node via a link with the agent playing as Mister X going first. Mister X’s position is secret apart from on 3rd, 8th and 13th turn but the type of link Mister X uses is revealed each turn. Links are designated as taxi, bus or underground links. The agents seeking to find Mister X have a finite resource of tickets that are used up every time they move (4 taxi, 3 bus, 3 underground). The game ends when either a detective arrives on the same node as Mister X in the same go or the detectives run out of tickets.
Now back to the abstract, describing how a person thinks about playing a game is going to be vital in identifying what components an agent might need to be made out of. The action of a person playing Scotland yard will then be linked to an abstract concept with the hope that each of these concepts has a computational implementation.
So when first playing Scotland Yard a person reads through the guide and looks at the game board and objects contained in the box. The guide contains a description of the activity and the rules. The description of the activity makes reference to the game board (world) and the pieces that will be placed on the board. The rules then explicitly place constraints on how those pieces may be moved around the board.
In the abstract, there is a game that provides a set of information that contain activity descriptions and object references that an agent needs to be able to understand. Objects are placed into the game world and are then constrained by the environment. Implicitly by the landscape of the board and explicitly by the rules.
Once the person has remembered all the information contained in the guide they start thinking about how they might avoid the detectives in their role as Mister X. The person can look at the board and judge the distance between Mister X and each of the detectives and choose a node that distances themselves from the detectives. However, given the person would have to also reveal the mode of transport used there is an element of information denial to be considered. For example: if they have 4 possible nodes to travel to of which only one has a link for the tube and all of them have taxi links choosing the tube would give away their exact location. Finally settling on a node that balances distance and a mode of transport with the most possible outcomes they would make their first move. This process will then repeat until Mister X or the Detectives win. There exist far more decision making factors than mentioned above including but not limited to a person’s ability to judge the thought process of others, the ability to manipulate them through speech and the ability to think many turns ahead of the current round.
There exists within the game world from the point of the object or objects that an agent controls a set of possible decisions after considering the rules and the landscape. These decisions then need to be assessed relative to a goal. In the case of games, the objective set out in the activity that determines a victor. Once each of these possible decisions has been assessed the one that gives the greatest chance of victory should then be chosen. Now it becomes about breaking down that process into components that can be put together to replicate that process
Our breakdown of a game had it split into four components. The activity and rules should be read and stored by the agent. The agent will also need to take in information about the game world it exists in and then make a decision based on that information. To achieve this the agent must have some senses (A mechanism that can take in information about the outside world), a memory (ability to store information gained from the outside world and form its thoughts on information) and a decision-making component.
The last component which is probably the hardest to define is the agent to act like our person will require an ability to learn and by learn I mean assess information based on its actions that will allow its future performance to be improved. In our example with a person, this would represent the person having a greater chance of victory from game to game based on improvements to their ability to play the game as well as their ability to adapt how they play relative to who they are playing against.
This essay shall only consider the agent’s ability to improve its decision-making ability based on games its played rather than opponents its played against. This is a limit of the specific example and time available. The abstract agent should defiantly have the ability to adapt depending on the opponent. A process diagram is in the appendix that shows the process by which the agent would play a game based on our observations of a person playing.
To complete the process with our specific example each of the components will have to be created using things that can interlink with one another and be hosted on a computer. Starting with the senses, these will take in information from outside the agent so it can make decisions in the world. For an agent playing Scotland Yard the simplest form of sense would be a stream of structured information that it has the ability to read. An example of this would be Javascript Object Notation (Duckett,2014)5 which would allow for the rules, activity description and world data to be passed into the agent (APPENDIX A).
When the agent is able to take in the information about the activity, rules and the current state of the world then comes the point when it can make use of this information to make a decision. The decision mechanic is merely an assessment of available information to produce an allowable move within a game. The effectiveness of which can be measured by seeing if the agent improved its chance of winning. For our specific example, we have a set of nodes that do or do not have a detective on them and a list of links of varying types. For Scotland yard three possible decision-making processes have been looked at that will use the information available to the agent.
Process One (APPENDIX C) is simple, find a set of possible moves and randomly choose one. Although this is the opposite of a carefully thought out decision it doesn’t allow the detectives to figure out where it’s going to go next. By this I mean they cannot pick up a pattern in how the agent is making decisions. However, the agent is just as likely to cause its own downfall as it is to outwit the detectives.
Moving on from complete randomness comes Process Two (APPENDIX C). Here the distance between each possible move and each of the detectives is measured. The node that will place the largest possible distance between the agent and the detectives is chosen. On the face of it, that seems fine but it does not take into account denying the detectives information allowing them to predict the agents' next move.
Process Three (APPENDIX C), is slightly more complicated but gives the agent a better chance. Lying somewhere between 1 and 2, three will incorporate elements of randomness but ultimately have a goal in mind. If we give the agent the ability to store information about each game, it has played then the more it plays the more information it has available to it.
With every move and every game, additional information about the effectiveness of the decision-making process can be gathered and analysed by the learning process. This initially could in be a human who observes the agent and adjusts the decision making process from game to game. Ideally, these changes will be supported by information gathered by the agent.
The processes in the appendix are specific approaches for the Scotland yard Example. Ideally, the agent should be able to generate a decision-making process based upon the information gained from the environment it is placed in. Parts of the agent at this current moment in time could be fulfilled by a person. Using a person to run a process allows for that process to be defined at a high level. The learning process and the selection of an appropriate decision-making process are tasks that initially can be performed by a person. Then by gathering information on how a person performs that process a more rigid set of instructions can be defined so that a computer can replicate the person. The only constraint to this approach is that the person will have to provide information outputs within a form that the other components can make use of.
The agent process and components can be
adapted to suit any game that meets the definition and structure provided above,
giving people a general process to follow when approaching an unknown game
(APPENDIX B). Then once information about how successful an initial attempt at
any game is gained the agent can refine its decision-making process to
gradually improve its chances of winning. The person can use this information
to either try to construct an agent using computational logic or write down a
formal system that they or another person can follow.
References
1. Oxforddictionaries.com. (2016). game -
definition of game in English from the Oxford dictionary. [online]
Available at: https://www.oxforddictionaries.com/definition/english/game
[Accessed 15 Aug. 2016].
2. Ravensburger. (2016). Scotland
Yard Rules. [online] Available at: https://www.ravensburger.com/spielanleitungen/ecm/Spielanleitungen/Scotland_Yard_W_And_B_GB.pdf
[Accessed 15 Aug. 2016].
3.
Norving, P. and Russel, S.
(2013). Artificial intelligence. [s.l.]: Pearson Education Limited.
4.
Horstmann, C. (2010). Big
Java. Hoboken, N.J.: Wiley.
5. Duckett, J. (2014). JavaScript et jQuery. Indianapolis, IN: Wiley.
Appendix A
Sample
Scotland Yard Board Information from Sample
{
"nodes": [
{"nodeID":"114","agents":[]}
,{"nodeID":"126","agents":[]}
,{"nodeID":"132","agents":[]}
,{"nodeID":"140","agents":["MisterX"]}
]
,"links": [
{"nodeID1":"114","nodeID2":"126","transport":"taxi"}
,{"nodeID1":"114","nodeID2":"unkown","transport":"taxi"}
,{"nodeID1":"114","nodeID2":"unkown","transport":"taxi"}
,{"nodeID1":"114","nodeID2":"unkown","transport":"taxi"}
,{"nodeID1":"114","nodeID2":"unkown","transport":"taxi"}
,{"nodeID1":"114","nodeID2":"140","transport":"bus"}
,{"nodeID1":"114","nodeID2":"132","transport":"taxi"}
,{"nodeID1":"126","nodeID2":"unkown","transport":"taxi"}
,{"nodeID1":"126","nodeID2":"unkown","transport":"taxi"}
,{"nodeID1":"132","nodeID2":"140","transport":"taxi"}
,{"nodeID1":"140","nodeID2":"126","transport":"taxi"}
,{"nodeID1":"140","nodeID2":"unkown","transport":"underground"}
,{"nodeID1":"140","nodeID2":"unkown","transport":"underground"}
,{"nodeID1":"140","nodeID2":"126","transport":"underground"}
]
}
Appendix B: Agent Process
