The purpose of this entry is to describe the 4 type of grammars that can be used to classify a language, and the means used to classify a language as one of the four types of grammrs.
From a linguistics and NLP standpoint, languages can be classified by 4 possible grammar types. From the most expressive description to the least expressive description, a language can be described by a grammar known as type 0, type 1, type 2, or type 3. Each of the different grammars has a common name. A given grammar can sometimes describe other grammars. A type 0 grammar can describe type 1, type2, and type 3 grammars. A type 1 grammar can describe type 2 and type 3. A type 2 grammar can describe a type 3 grammar. A type 3 grammar cannot describe any other type of grammar.
For the four types of grammars, each are composed of rules known as productions, which have the general form of w1 -> w2 . Each production rule generates a sequence of terminal tokens and non-terminals. Non-terminals are production rules that go by the lhs symbol, w1 .
A recursively enumerable grammar is also known as a type 0 grammar. A type 0 grammar has no restrictions on its production rules. Context-sensitive grammar is a type 1 grammar. A type 1 grammar is restricted to productions where the number of symbols on the rhs is equal to or greater than the number of symbols on the lhs. Context-free grammar is a type 2 grammar. A non-terminal in a type 2 grammar can be replaced by its rhs. In comparison, a non-terminal in a type 1 grammar can only be replaced if there is a production that matches the symbols on the rhs with an equivalent lhs. A regular grammar is a type 3 grammar. A regular grammar is also known as a regular expression, which is used by Perl, Python, and grep when searching on strings. A production of a regular grammar has a restricted expression. The lhs is a non-terminal. The rhs is a terminal, which is optionally followed by a non-terminal.
Grammars are also more formally known as phrase structure grammars.
G = phrase structure grammar as a set
G = (V,T,S,P)
V is a vocabulary, a set of tokens and non-tokens(non-terminals)
T is a subset of V. T is the set of terminal tokens
S is a start symbol/token that is a member of V
P is a set of production rules
N is V - T, set of non-terminal symbols/tokens
Types of grammars and restrictions on their productions, w1 -> w2
0 no restrictions
1 length(w1) <= length(w2), w2=lambda
2 w1 = A, where A is non-terminal symbol
3 w1=A and w2=aB or w2=a, where A is an element of N, B is an element of N, and a is an element of T, or S->lambda
Friday, September 25, 2009
Sunday, September 20, 2009
Tracing the boot up sequence of TAEB part 2
This entry goes into detail of the top of the main loop of the taeb script, line 81-98.
taeb,lines 81-98 is the top-level of the taeb main loop. The main loop is composed of 2 main parts. The first item in the main loop is the actual operational statement. The later item, which is actually multiple statements, are only executed if taeb has been told via the command line option, --loop, to re-execute itself after it has completed playing a nethack session.
Let's review these 2 portions by first going over the later item, since it is only executed when specified via the command-line.
taeb, line88: only reinitialize/restart taeb if local variable $loop is not equal to 0. This will happen when --loop is specified via the command-line.
taeb, line90: reset all taeb variables and states
taeb, lines 92-96: Sleep for 5 seconds before starting a new nethack game
The eval statement, which is the first statement ecountered at the start of this loop, does all the work.
taeb, line 83: sets INT handler to print message to screen and prevent starting a new game by setting $loop to 0.
taeb, line 84: execute a taeb session
taeb, line 85: reports the results of a taeb session
taeb, line84, is TAEB->play;The method play is sent to the TAEB object, which is defined in TAEB.pm.
TAEB.pm, lines 742-749: Inside this loop, each iteration is a step. At the end of each step, results are store of the step. The last step of the taeb session will print its results to the screen.
Inside each step, the following methods are called in order:
redraw
display_topline
human_input
full_input
handle_XXXX called
redraw is invoked from TAEB::Display::Curses. redraw is used to repaint the entire nethack screen at the start of a step. display_topline is also invoked from TAEB::Display::Curses, too. display_topline displays any messages received from the last step in the current step. human_input is defined inside TAEB.pm. human_input is used to get keyboard input if ai allows human control and a key is pressed. Under normal operational circumstances, human_input will not capture anything.
full_input is a wraper method that is used to capture nethack screen data and load it into the taeb database. At the start of full_input's operation, the screen scraper is reset to take new info and the publisher is turned off. The publisher is resumed after scraping and processing of the scrape is finished. After the publisher is off, then next instruction performed is process_input, which reads any input from a previous action or user and sends it to the vt, virtual terminal. Afterwords, the screen is scraped and loaded into the Taeb database.
The next step performed is that dungeon and senses variables are updated. After the update of these items, the publisher is renabled. This completes the phase of a step where the percepts are captured.
taeb,lines 81-98 is the top-level of the taeb main loop. The main loop is composed of 2 main parts. The first item in the main loop is the actual operational statement. The later item, which is actually multiple statements, are only executed if taeb has been told via the command line option, --loop, to re-execute itself after it has completed playing a nethack session.
Let's review these 2 portions by first going over the later item, since it is only executed when specified via the command-line.
taeb, line88: only reinitialize/restart taeb if local variable $loop is not equal to 0. This will happen when --loop is specified via the command-line.
taeb, line90: reset all taeb variables and states
taeb, lines 92-96: Sleep for 5 seconds before starting a new nethack game
The eval statement, which is the first statement ecountered at the start of this loop, does all the work.
taeb, line 83: sets INT handler to print message to screen and prevent starting a new game by setting $loop to 0.
taeb, line 84: execute a taeb session
taeb, line 85: reports the results of a taeb session
taeb, line84, is TAEB->play;The method play is sent to the TAEB object, which is defined in TAEB.pm.
TAEB.pm, lines 742-749: Inside this loop, each iteration is a step. At the end of each step, results are store of the step. The last step of the taeb session will print its results to the screen.
Inside each step, the following methods are called in order:
redraw
display_topline
human_input
full_input
handle_XXXX called
redraw is invoked from TAEB::Display::Curses. redraw is used to repaint the entire nethack screen at the start of a step. display_topline is also invoked from TAEB::Display::Curses, too. display_topline displays any messages received from the last step in the current step. human_input is defined inside TAEB.pm. human_input is used to get keyboard input if ai allows human control and a key is pressed. Under normal operational circumstances, human_input will not capture anything.
full_input is a wraper method that is used to capture nethack screen data and load it into the taeb database. At the start of full_input's operation, the screen scraper is reset to take new info and the publisher is turned off. The publisher is resumed after scraping and processing of the scrape is finished. After the publisher is off, then next instruction performed is process_input, which reads any input from a previous action or user and sends it to the vt, virtual terminal. Afterwords, the screen is scraped and loaded into the Taeb database.
The next step performed is that dungeon and senses variables are updated. After the update of these items, the publisher is renabled. This completes the phase of a step where the percepts are captured.
Saturday, September 19, 2009
Tracing the boot up sequence of TAEB part 1
The purpose of this entry is to describe in plain talk how Taeb starts up and executes it 'main' loop. By understanding the 'main' loop of the taeb framework, this will enable creation of Taeb agents.
taeb, line1: enables text file to be interpreted as a Perl script
taeb, line2: no questionable Perl constructs allowed
taeb, line3: ? literally says to add to @INC the the library using the literal 'lib'
taeb, line4: Use Perl library Getopt::Long to process command-line options
taeb, lines 7-20: defintion of print_usage subroutine which shows the command-line options that can be used to configure Taeb operation
taeb, line22: local variable used to control whether or not taeb will just stop when it receives an interrupt or reset and begin a new execution. See while-loop at line 81.
taeb, line23: local list that stores command-line specified options for taeb. This local list is then transferred to Taeb's configureation. See lines 24, 28, 43.
taeb, line24: local hash that is initialzed to store the hard reference to the variable $loop and the list @config_overrides.
taeb, lines 25-39: Code used to alternate operation of Taeb via command-line options. Also, used to display the options that can be specified to Taeb.
taeb, line41: Specify that TAEB.pm must be used and found.
taeb, line43: Change Taeb configuration from specified command-line options
taeb, lines 45-47: Add to Taeb configruation that no ai should be used if command-line option specified.
taeb, lines 49-77: handlers assigned to signals TSTP, CONT, TERM, USR1, and USR2 signals.
taeb, line79: Flush after every write
taeb, lines 81-98: Top of the main loop of Taeb.
taeb, line1: enables text file to be interpreted as a Perl script
taeb, line2: no questionable Perl constructs allowed
taeb, line3: ? literally says to add to @INC the the library using the literal 'lib'
taeb, line4: Use Perl library Getopt::Long to process command-line options
taeb, lines 7-20: defintion of print_usage subroutine which shows the command-line options that can be used to configure Taeb operation
taeb, line22: local variable used to control whether or not taeb will just stop when it receives an interrupt or reset and begin a new execution. See while-loop at line 81.
taeb, line23: local list that stores command-line specified options for taeb. This local list is then transferred to Taeb's configureation. See lines 24, 28, 43.
taeb, line24: local hash that is initialzed to store the hard reference to the variable $loop and the list @config_overrides.
taeb, lines 25-39: Code used to alternate operation of Taeb via command-line options. Also, used to display the options that can be specified to Taeb.
taeb, line41: Specify that TAEB.pm must be used and found.
taeb, line43: Change Taeb configuration from specified command-line options
taeb, lines 45-47: Add to Taeb configruation that no ai should be used if command-line option specified.
taeb, lines 49-77: handlers assigned to signals TSTP, CONT, TERM, USR1, and USR2 signals.
taeb, line79: Flush after every write
taeb, lines 81-98: Top of the main loop of Taeb.
Saturday, September 12, 2009
Demo AI with TAEB and try_explore part 1
TAEB ships with an AI known as Demo. one can use it as a reference for creating your own AI with TAEB. At its most simplistic level, the creation of a TAEB AI invovles the following steps:
1. Create a Perl module that inherits from TAEB::AI
2. Create a method called next_action that returns a an object of type TAEB::Action
I will be describing how next_action in Demo moves around the the Nethack dungeon via next_action sending the try_explore method. In TAEB's Demo AI, one of the actions that it can execute is defined by the try_explore method. From the current position in the Nethack dungeon, TAEB will use try_explore to find the next best tile to reach amount it's 8 nearest neighbors.
try_explore itself is merely a wrapper. The work is done first_match, which takes as an argument a type of the destination tile. In this case, the destination tile type is 'unexplored'. Tile types are defined in lib/TAEB/Util.pm from lines 73-91. first_match is part of TAEB::World::Path package. The purpose of first_match is to identify the type of data structure that will be used to search for the next tile position. Typically, for the purposes to try_explore this will be undef. After determining the type of data structure for searching, first_match calls _dijskstra, which is an implementation of the Dijkstra path finding algorithm.
1. Create a Perl module that inherits from TAEB::AI
2. Create a method called next_action that returns a an object of type TAEB::Action
I will be describing how next_action in Demo moves around the the Nethack dungeon via next_action sending the try_explore method. In TAEB's Demo AI, one of the actions that it can execute is defined by the try_explore method. From the current position in the Nethack dungeon, TAEB will use try_explore to find the next best tile to reach amount it's 8 nearest neighbors.
try_explore itself is merely a wrapper. The work is done first_match, which takes as an argument a type of the destination tile. In this case, the destination tile type is 'unexplored'. Tile types are defined in lib/TAEB/Util.pm from lines 73-91. first_match is part of TAEB::World::Path package. The purpose of first_match is to identify the type of data structure that will be used to search for the next tile position. Typically, for the purposes to try_explore this will be undef. After determining the type of data structure for searching, first_match calls _dijskstra, which is an implementation of the Dijkstra path finding algorithm.
Saturday, September 5, 2009
Alternate means of running a Taeb AI agent
The easiest way to use an AI agent other than Demo in Taeb is to install the new agent into your Taeb installation. If you do this, then you only need to have a config.yml in your .taeb directory that specifies this new agent.
But, if for some reason, you don't want the agent's source code to be installed into your main installation, there is another way. As before, you will still need a config.yml in your .taeb file. If you have followed the software conventions for Taeb agents, cd into your agent's lib directory;The lib directory only contains the directory 'TAEB'. Inside that directory, lib, which is considered the 'top' of your agent's code, run 'taeb'. This will grab the agent defined under 'taeb' as the agent to run.
One can get the same results if one sets the full path of PERL5LIB to the 'lib' directory of your agent. This method has the advantage that only a config.yml is needed. No need to run taeb from the specific lib directory of your agent.
But, if for some reason, you don't want the agent's source code to be installed into your main installation, there is another way. As before, you will still need a config.yml in your .taeb file. If you have followed the software conventions for Taeb agents, cd into your agent's lib directory;The lib directory only contains the directory 'TAEB'. Inside that directory, lib, which is considered the 'top' of your agent's code, run 'taeb'. This will grab the agent defined under 'taeb' as the agent to run.
One can get the same results if one sets the full path of PERL5LIB to the 'lib' directory of your agent. This method has the advantage that only a config.yml is needed. No need to run taeb from the specific lib directory of your agent.
Friday, September 4, 2009
TAEB keyboard commands
The keyboard commands that can be used to interact with a TAEB-based agent are defined in TAEB/lib/TAEB.pm
p - pause agent
d - change draw mode
i - show inventory
\cP - show old message
\cX - Senses
e - equipment menu
I - item spoiler data
M - monster spoiler data
\e - user input
r - refresh screen
\cr - refresh screen
q - save and exit
Q - controlled quit and exit
p - pause agent
d - change draw mode
i - show inventory
\cP - show old message
\cX - Senses
e - equipment menu
I - item spoiler data
M - monster spoiler data
\e - user input
r - refresh screen
\cr - refresh screen
q - save and exit
Q - controlled quit and exit
How to stop a TAEB AI properly
shift+Q
If you try some other key sequence, such as ctrl-c, it will just stop, but when you re-run taeb again it will pick up where you left off. Most of the time I just want to start over.
Many key commands I think are located in lib/TAEB.pm in the TAEB source.
If you try some other key sequence, such as ctrl-c, it will just stop, but when you re-run taeb again it will pick up where you left off. Most of the time I just want to start over.
Many key commands I think are located in lib/TAEB.pm in the TAEB source.
Structure of TAEB AI Behavioral Part 3
For the personality described the the Perl module Explorer.pm, each time the method next_action is called from the base class TAEB::AI::Behavioral::Personality, the member list is scanned for the behavior with the highest urgency.
The member list this is scanned is called prioritized_behaviors, which is an array of strings that are the humand-readable name of a possible behavior of the agent. The elements of prioritized_behaviors are(listed in the order of scanning from top to bottom) is: FixHunger, Heal, FixStatus, Defend, AttackSpell, BuffSelf, Kite, Melee, ProjectFiles, Vault, Shop, Carrion, GetItems, Equip, Identify, DipForExcalibur, Wish.
When the next_action is called it first performs any post-behaviors by sending the done method to complete any steps from the current behavior, if defined. The behavior Luckstone appears to be the only behavior with an implementation of the done method. After calling done, next_action will scan the entire prioritized_behaviors array, looking fof the first behavior with the highest urgency. If there are multiple behaviors with the same urgency and the urgency is the largest, then the first one found is the most urgent behavior. As next_action goes through each behavior in the prioritized_behaviors list, it executes each behavior's prepare method. The prepare method of a TAEB::AI::Behavior instance performs setup in preperation for a behavior to be chosen as the most urgent next behavior. For example, for the Explore.pm behavior, the prepare method performs a search of the nethack maze from its current position. When next_action completes its iterations over the contents of the prioritized_behaviors, all behaviors have had their prepare methods executed, but only one behavior is the most urgent and will be converted into a nethack command, TAEB::AI::Action subclass.
The member list this is scanned is called prioritized_behaviors, which is an array of strings that are the humand-readable name of a possible behavior of the agent. The elements of prioritized_behaviors are(listed in the order of scanning from top to bottom) is: FixHunger, Heal, FixStatus, Defend, AttackSpell, BuffSelf, Kite, Melee, ProjectFiles, Vault, Shop, Carrion, GetItems, Equip, Identify, DipForExcalibur, Wish.
When the next_action is called it first performs any post-behaviors by sending the done method to complete any steps from the current behavior, if defined. The behavior Luckstone appears to be the only behavior with an implementation of the done method. After calling done, next_action will scan the entire prioritized_behaviors array, looking fof the first behavior with the highest urgency. If there are multiple behaviors with the same urgency and the urgency is the largest, then the first one found is the most urgent behavior. As next_action goes through each behavior in the prioritized_behaviors list, it executes each behavior's prepare method. The prepare method of a TAEB::AI::Behavior instance performs setup in preperation for a behavior to be chosen as the most urgent next behavior. For example, for the Explore.pm behavior, the prepare method performs a search of the nethack maze from its current position. When next_action completes its iterations over the contents of the prioritized_behaviors, all behaviors have had their prepare methods executed, but only one behavior is the most urgent and will be converted into a nethack command, TAEB::AI::Action subclass.
Thursday, September 3, 2009
Structure of the Taeb AI Behavioral Part 2
The Behavioral AI has 4 possible personalities which are defined by the Perl pm's Explorer, ScoreWhore, Bathophobe, and Descender. Explorer.pm is the base personality. ScoreWhore, Bathophobe, and Descender are all based upon Explorer.pm.
When Explorer.pm is instantiated by the Taeb framework, a hash, %behaviors, is created. This has uses the string names of actions as keys;These keys are mapped to instances of a TAEB::AI::Behavioral::Behavior::actionStringName. Explorer.pm contains an array of strings called prioritzed_behaviors.
Each time next_action is called, the work is done in Behavioral.pm. When next_action is called, the first task accomplished is that the criticalness of each action, which we will now call a behavior, will be calculated. The criticalness of each behavior is a property which is called urgency, which is either a string or numeric value. The string values of urgency are critical, important, normal, unimportant, fallback, and none. The corresponding numerical values are 50, 40, 30, 20, 10, and 0.
The method next_action calculates the urgency for each of the behaviors in the prioritized_behaviors. The urgency is calculated by the find_urgency method. For each behavior, find_urgency examines the current state of the agent with respect to the environment and sets the urgency member value. As the urgency is calculated, next_action is always looking for the behavior with the largest urgency. If multiple items have the same urgency value, the behavior that is in the prioritized_behavior first is the behavior that will be selected for generating a nethack action. Sometimes, no urgency is calculated. In the case of Explore.pm, the prepare method merely executes the Explore behavior each time Explore is examined during the next_action method.
When Explorer.pm is instantiated by the Taeb framework, a hash, %behaviors, is created. This has uses the string names of actions as keys;These keys are mapped to instances of a TAEB::AI::Behavioral::Behavior::actionStringName. Explorer.pm contains an array of strings called prioritzed_behaviors.
Each time next_action is called, the work is done in Behavioral.pm. When next_action is called, the first task accomplished is that the criticalness of each action, which we will now call a behavior, will be calculated. The criticalness of each behavior is a property which is called urgency, which is either a string or numeric value. The string values of urgency are critical, important, normal, unimportant, fallback, and none. The corresponding numerical values are 50, 40, 30, 20, 10, and 0.
The method next_action calculates the urgency for each of the behaviors in the prioritized_behaviors. The urgency is calculated by the find_urgency method. For each behavior, find_urgency examines the current state of the agent with respect to the environment and sets the urgency member value. As the urgency is calculated, next_action is always looking for the behavior with the largest urgency. If multiple items have the same urgency value, the behavior that is in the prioritized_behavior first is the behavior that will be selected for generating a nethack action. Sometimes, no urgency is calculated. In the case of Explore.pm, the prepare method merely executes the Explore behavior each time Explore is examined during the next_action method.
Wednesday, September 2, 2009
Structure of the Taeb AI Behavioral Part 1
This is the start of a series of entries on the Taeb AI agent known as Behavioral.
Taeb is an AI agent written in Perl5. Within the Taeb framework, the Behaviorial agent would be found within lib/TAEB/AI module.
Overall, Behavioral is composed of 5 modules:
lib/TAEB/AI
lib/TAEB/AI/Behavorial
lib/TAEB/AI/Behavioral/Behavior
lib/TAEB/AI/Behavioral/Meta
lib/TAEB/AI/Behavioral/Personality
lib/TAEB/AI contains the Behavioral module and the Perl module Behavioral.pm. Behavioral.pm Behavioral.pm will cause a user to use a specific subclass of the Behavioral class.
The Behavioral module contains the Behavior, Meta, and Personality modules. The Behavior module contains the various actions an agent can perform. Meta defines the urgency type, which is used to choose a particular action. Personality contains the various types of Behavioral agents. In addition, the Perl modules Behavior.pm, Personality.pm, and ThreatEvaluation.pm live here. Every agent can accomplish some sort of action. Behavior.pm is a base class that defines the common attributes of an action. Personality.pm is the base class of the different types of Behavioral agents. ThreatEvaluation.pm is a data object used to determine the relationship between resource consumption and attacking a monster.
In the Personality module, there are 4 different types of Behavioral agents: Bathophobe, Descender, Explorer, and ScoreWhore. In the config.yml file, one specifies one of these Behavioral agent types.
Taeb is an AI agent written in Perl5. Within the Taeb framework, the Behaviorial agent would be found within lib/TAEB/AI module.
Overall, Behavioral is composed of 5 modules:
lib/TAEB/AI
lib/TAEB/AI/Behavorial
lib/TAEB/AI/Behavioral/Behavior
lib/TAEB/AI/Behavioral/Meta
lib/TAEB/AI/Behavioral/Personality
lib/TAEB/AI contains the Behavioral module and the Perl module Behavioral.pm. Behavioral.pm Behavioral.pm will cause a user to use a specific subclass of the Behavioral class.
The Behavioral module contains the Behavior, Meta, and Personality modules. The Behavior module contains the various actions an agent can perform. Meta defines the urgency type, which is used to choose a particular action. Personality contains the various types of Behavioral agents. In addition, the Perl modules Behavior.pm, Personality.pm, and ThreatEvaluation.pm live here. Every agent can accomplish some sort of action. Behavior.pm is a base class that defines the common attributes of an action. Personality.pm is the base class of the different types of Behavioral agents. ThreatEvaluation.pm is a data object used to determine the relationship between resource consumption and attacking a monster.
In the Personality module, there are 4 different types of Behavioral agents: Bathophobe, Descender, Explorer, and ScoreWhore. In the config.yml file, one specifies one of these Behavioral agent types.
Subscribe to:
Posts (Atom)