The Battle for Wesnoth Wiki - User contributions [en]

FormulaAIandAdaptation

2008-04-12T00:28:07Z

Alesis-Novik: /* Timeline */

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units. After seeing the source, I would say that something as simple as a vector of simplified unit_stats would be able to hold the information on the units. The information on units can be collected from the unit .cfg files, and accessed easily from any other AI class (most importantly the similarity engine). There vectors could be grouped, making them specialized for certain unit groups, as I mentioned. The knowledge base would have information on the relations between those groups.

===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)
===Summary===
The basic work flow of the AI engine would be something like this: the AI evaluates the situation it is currently in and checks the goals set to it (so it doesn't go offensive if it has to defend). After that, the possible plan from the case base is selected by looking at the position the AI is in. If the plan doesn't fit in the current situation perfectly (which would rarely be the case), the AI calls the similarity engine to evaluate the closest plan that can be produced with the resources available. This would include accessing the knowledge base and checking how close the units look like each other. The AI will be able to calculate possible outcome of the knew plan and discard it, if it would prove totally useless. The process would then be repeated (the best possible plan would in the end be selected (there is an option of recombination of the plans to produce a greater effect and a better plan))

==Timeline==
*Until May 26: The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections.
*May 26 - July 7: The second part would be to write a case base so it could store plans and create new plans, along with the probability of success. Since this would include the most communication with players, I believe getting this working and filling it would take most of the time until midterm.
*July 7 - August 18: The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible). After writing this, the testing would begin, trying to see how the new AI scales with the old one.

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula to get close enemies and functions in pathutil for close tiles selection[http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]
*An additional formula to get the possible battle outcomes [http://svn.gna.org/viewcvs/wesnoth?rev=25641&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-04-12T00:25:33Z

Alesis-Novik: /* The Knowledge Base */

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units. After seeing the source, I would say that something as simple as a vector of simplified unit_stats would be able to hold the information on the units. The information on units can be collected from the unit .cfg files, and accessed easily from any other AI class (most importantly the similarity engine). There vectors could be grouped, making them specialized for certain unit groups, as I mentioned. The knowledge base would have information on the relations between those groups.

===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)
===Summary===
The basic work flow of the AI engine would be something like this: the AI evaluates the situation it is currently in and checks the goals set to it (so it doesn't go offensive if it has to defend). After that, the possible plan from the case base is selected by looking at the position the AI is in. If the plan doesn't fit in the current situation perfectly (which would rarely be the case), the AI calls the similarity engine to evaluate the closest plan that can be produced with the resources available. This would include accessing the knowledge base and checking how close the units look like each other. The AI will be able to calculate possible outcome of the knew plan and discard it, if it would prove totally useless. The process would then be repeated (the best possible plan would in the end be selected (there is an option of recombination of the plans to produce a greater effect and a better plan))

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections. This part could be done prior to the beginning of the official coding start.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success. Since this would include the most communication with players, I believe getting this working and filling it would take most of the time until midterm.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible). After writing this, the testing would begin, trying to see how the new AI scales with the old one.

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula to get close enemies and functions in pathutil for close tiles selection[http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]
*An additional formula to get the possible battle outcomes [http://svn.gna.org/viewcvs/wesnoth?rev=25641&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-04-08T01:35:06Z

Alesis-Novik: /* Details */

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units. After seeing the source, I would say that something as simple as a vector of simplified unit_stats would be able to hold the information on the units. There vectors could be grouped, making them specialized for certain unit groups, as I mentioned. The knowledge base would have information on the relations between those groups.
===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)
===Summary===
The basic work flow of the AI engine would be something like this: the AI evaluates the situation it is currently in and checks the goals set to it (so it doesn't go offensive if it has to defend). After that, the possible plan from the case base is selected by looking at the position the AI is in. If the plan doesn't fit in the current situation perfectly (which would rarely be the case), the AI calls the similarity engine to evaluate the closest plan that can be produced with the resources available. This would include accessing the knowledge base and checking how close the units look like each other. The AI will be able to calculate possible outcome of the knew plan and discard it, if it would prove totally useless. The process would then be repeated (the best possible plan would in the end be selected (there is an option of recombination of the plans to produce a greater effect and a better plan))

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections. This part could be done prior to the beginning of the official coding start.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success. Since this would include the most communication with players, I believe getting this working and filling it would take most of the time until midterm.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible). After writing this, the testing would begin, trying to see how the new AI scales with the old one.

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula to get close enemies and functions in pathutil for close tiles selection[http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]
*An additional formula to get the possible battle outcomes [http://svn.gna.org/viewcvs/wesnoth?rev=25641&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-04-08T01:27:03Z

Alesis-Novik: /* Timeline */

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units. After seeing the source, I would say that something as simple as a vector of simplified unit_stats would be able to hold the information on the units. There vectors could be grouped, making them specialized for certain unit groups, as I mentioned. The knowledge base would have information on the relations between those groups.

===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections. This part could be done prior to the beginning of the official coding start.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success. Since this would include the most communication with players, I believe getting this working and filling it would take most of the time until midterm.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible). After writing this, the testing would begin, trying to see how the new AI scales with the old one.

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula to get close enemies and functions in pathutil for close tiles selection[http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]
*An additional formula to get the possible battle outcomes [http://svn.gna.org/viewcvs/wesnoth?rev=25641&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-04-08T01:23:37Z

Alesis-Novik: /* The Knowledge Base */

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units. After seeing the source, I would say that something as simple as a vector of simplified unit_stats would be able to hold the information on the units. There vectors could be grouped, making them specialized for certain unit groups, as I mentioned. The knowledge base would have information on the relations between those groups.

===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible)

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula to get close enemies and functions in pathutil for close tiles selection[http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]
*An additional formula to get the possible battle outcomes [http://svn.gna.org/viewcvs/wesnoth?rev=25641&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-04-06T20:50:12Z

Alesis-Novik: /* Commits */

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units.
===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible)

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula to get close enemies and functions in pathutil for close tiles selection[http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]
*An additional formula to get the possible battle outcomes [http://svn.gna.org/viewcvs/wesnoth?rev=25641&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAI

2008-03-31T18:24:49Z

Alesis-Novik:

== Overview ==

The Wesnoth Formula AI is an attempt to develop an AI framework for Wesnoth that allows easy and fun development and modification of AIs for Wesnoth.

Wesnoth already has support for AIs written in Python, but writing AIs in Python has a couple of problems:

* it's still rather difficult, especially for a non-programmer, to develop an AI, even in Python
* Python is insecure; a malicious trojan horse Python script masquerading as an AI could do untold damage

The Wesnoth Formula AI aims to create a fairly simple, pure functional language which allows one to implement an AI. It also aims to allow AIs to be tweaked and modified by people with relatively little technical skill; anyone who can use WML should also be able to use the Formula AI to tweak an AI to make the AI in a scenario behave how they want.

The Wesnoth Formula AI is currently in an experimental stage of development. One can play with it and develop a rudimentary AI. Feedback is appreciated.

To develop an AI using the Formula AI, set ai_algorithm=formula_ai in [side].

== Approach ==

To use the Formula AI, one should put an [ai] tag inside the [side] tag. Inside this [ai] tag, one should specify the 'move' attribute to be a formula which specifies what movement the AI will make. Each time it's the AI's move, this formula will be run, and the move it results in will be executed. Then the formula will be run again; it'll continue to be run until it stops producing a valid move, at which point the AI will end its turn. Alternatively there is a command that the formula may return which will make it end its turn immediately.

A sample AI which does nothing but recruit Wolf Riders is as follows:

[side]
...
ai_algorithm=formula_ai
[ai]
move="recruit('Wolf Rider')"
[/ai]
[/side]

== Formula Command Line ==

To attempt to make it convenient to debug formulas, one can run formulas from within Wesnoth, and see the results. To run a formula, just start game and type 'f'. A command textbox will appear, where you can type a formula, and the results will be printed. For instance, typing

8 + 4

will result in "12" appearing on the screen. You can now use Wesnoth like a calculator. :-)

== Formula Basics ==

* The Formula language supports basic arithmetic operations, such as: +, -, *, /, % and ^. It supports integers but does NOT support decimal or floating point numbers. For example:

4 + 8*7 #evaluates to 60
(4 + 8)*7 #evaluates to 84
8 % 6 #evaluates to 2
5 / 2 #evaluates to 2
3 ^ 2 #evaluates to 9

* It also supports equality, = and !=, and comparison operators, <, >, <=, and >=. 'false' values are 0 (integer) and null. Other values are true. It also supports common operators such as and, or, and not:

2 = 4 #evaluates to 0
2 <= 3 #evaluates to 1
0 != 1 #evaluates to 1
not 4 #evaluates to 0
not 0 #evaluates to 1
(2 < 4) and (3 > 6) #evaluates to 1 and 0 which evaluates to 0
(2 < 4) or (3 > 6) #evaluates to 1 or 0 which evaluates to 1

* Formula language supports also 'dice' operator 'd'. Example usage is:

3d5

Which will give you one of results of rolling three five-sided dice (so random number between 3 and 15).

== Data Types ==

Formula System supports different types of data, which can be stored as a variables and are used in evaluations:

* Numbers: like 0, 1, 2 etc. Floating-point numbers are not supported. 0 is equal to logical 'false', any other number is 'true'.

* Text strings:

'this is a text string'

* Lists: A list is a sequence of values. For example, ai.my_units is a list of unit objects. A list is represented as square brackets, [], surrounding a comma-seperated list. For instance:

[4, 8, 7]

is a list of three numbers, and

[]

is a empty list. Various functions can operate on lists.

== AI Formula Language ==

=== Overview ===

The formula language must be able to access information about the scenario being played to make intelligent decisions. Thus there are various 'inputs' that one may access. A simple example of an input is the turn number one is on, given by the input, 'turn'. Try bringing up the formula command line using 'f' and then type in

turn

The AI will print out the current turn number the game is on.

The 'turn' input is a simple integer. However, some inputs are complex types which contain other inputs, or which may be lists of inputs. For instance, the input 'my_units' contains a list of all the AI's units.

A complex input such as a unit will contain a variety of inputs inside it. If one has a unit input, called 'u' for instance, one can access the 'x' co-ordinate of that unit by using u.loc.x -- u.loc accesses the 'location' object inside the 'unit' object, and the 'location' object contains 'x' and 'y' inputs inside it, which are the x and y co-ordinate of the unit.

=== Built-in functions ===
The formula language contains a large number of built-in functions which allow you to carry out all kinds of complex tasks. Syntax used to explain functions usage in this document is:

<result> = <function name>( <comma-separated list of parameters> [, <comma-separated list of optional parameters] )

Function may return <result> as:
* <variable> - any of the supported variable types
* <boolean> - false ( 0 or null ) or true ( 1 )
* <unit> - unit
* <location> - place on a gamemap
* <action> - object, which, if later passed to 'move= ' as the result of formula evaluation, make the AI perform a desired action.
* <result> - any of the above

Also function may return only single argument, or be able to return a whole list.

There are a wide variety of functions which can be used to accomplish many different tasks. You can also [[#Custom Functions|define your own functions]].

==== 'attack' function ====

<action> = attack( <attacker's position>, <destination>, <attack location> [, <weapon> ] )

The first three parameters are locations. At the begining, unit which is standing at <attacker's position> is moved to <destination> place. Then, from that place unit is attacking unit which stands in place marked by <attack location>. Fourth optional parameter is number, and indicates which weapon attacker should use - if not specified, best possible weapon is chosed automatically.

==== 'abs' function ====

<number> = abs( <input number> )

Function returns absolute value of an <input number>, for example

abs( -5 )

will return 5.

==== 'chance to hit' function ====

<number> = chance_to_hit( <unit> , <location> )

This function returns how possible ( in % ) it is to hit given <unit> in a specific <location>. For example:

chance_to_hit( my_leader , my_leader.loc )

shows how easy it is to hit your leader has in a place he is currently standing on.

==== 'choose' function ====

<result> = choose( <input list> , <formula> )

This function evaluates <formula> for each item in the <input list>. Will evaluate to the one item which <formula> gave the highest value. For example:

choose(my_units, level)

gives back the unit with the highest level.

==== 'close enemies' function ====

<units list> = close_enemies( <location> , <distance> )

This function gets a list of enemies in the given or smaller distance from the location. For example:

close_enemies(loc(10,10), 5)

gives back a list of enemies in the distance of 5 tiles or less from the tile (10, 10).

==== 'dir' function ====

<list of names> = dir ( <input object> )

This function return list with all names of <input object's> members. For example:

dir( my_leader )

will result in output:

[ 'x', 'y', 'loc', 'id', 'leader', 'hitpoints', 'max_hitpoints', 'experience', 'max_experience', 'level',
'total_movement', 'movement_left', 'side', 'is_enemy', 'is_mine']

This command is useful in formula command line, to get information about members of different type of data. To get list of members of the ai, type:

dir( self )

==== 'distance_between' function ====

<number> = distance_between( <location A> , <location B> )

This function returns distance (in hexes) between <location A> and <location B>. For example:

distance_between( loc( 1, 1) , loc( 3, 3) )

will return 3.

==== 'distance_to_nearest_unowned_village' function ====

<number> = distance_to_nearest_unowned_village( <location A> )

This function returns distance (in hexes) between <location A> and nearest unowned village.

==== 'defense_on' function ====

<number> = defense_on( <unit> , <location> )

This function returns defense rate of given <unit> in a specific <location>. For example:

defense_on( my_leader , my_leader.loc )

shows how good defense your leader has in a place he is currently standing on.

==== 'evaluate_for_position' function ====

==== 'fallback' function ====

<action> = fallback( <name> )

This function allows to chose different AI which will take control over side untill the end of current turn. For example:

fallback( 'default' )

will transfer control to the default C++ AI.

==== 'filter' function ====

<reult list> = filter( <input list>, <formula> )

This function will run <formula> on each item in the <input list>. Will evaluate to a <result list> which only contains items the <formula> was true for. For example:

filter(my_units, hitpoints < max_hitpoints)

will return all of your units which have less than maximum hitpoints. For instance this could be used if looking for candidates for healing.

==== 'find' function ====

<result> = find( <input list>, <formula> )

This function will run <formula> on each item in the <input list> and will return a first item for which <formula> was true. For example:

filter(units, id = 'Elvish Archer' )

will return first unit with id equal to 'Elvish Archer'.

==== 'head' function ====

<variable> = head( <list of variables> )

Head returns first item from the <list of variables>, for example

head( [ 5, 7, 9] ) #returns 5
head( [ 'Orc', 'Human' ] ) #returns 'Orc'

==== 'is_village' function ====

<boolean> = is_village( <map or ai.map> , <location> ) #1

<boolean> = is_village( <map or ai.map> , <coordinate x> , <coordinate y> ) #2

The first argument is always a 'map' - member of the ai which provides information about the gamemap.

In #1 usage, we put in as a second argument location. In #2, second and third arguments are numbers: coordniates of the certain hex on a map. Function checks if that place is a village, and returns either 1 (yes, it is village) or 0 (no, it isn't village). Example of usage:

is_village( map , loc( 2, 3) )

is_village( map , 2, 3)

Both check, if hex with coordinates 2,3 is a village.

Remember, when using is_village in custom function, you either have to access map by writing 'ai.map', or specify ai as a 'default input'.

==== 'if' function ====

<result> = if( <condition> , <if true> , <otherwise> )

If the <condition> parameter is true, the function will evaluate to being equal to its second input ( <if true> ), otherwise it will evaluate to being equal to its third input ( <otherwise> ).
For instance, an AI that recruits Wolf Riders on the first turn, and Orcish Grunts thereafter might look like this:

move="if(turn = 1, recruit('Wolf Rider'), recruit('Orcish Grunt'))"

==== 'loc' function ====

<location> = loc( <X number>, <Y number> )

Function will return a location (pair of numbers) from two given input arguments.

==== 'map' function ====

<result list> = map( <input list> , <formula> )

This function will run <formula> on each item in the <input list>, and evaluate to a new <result list> which contains the same number of items as in <input list>, with the formulas run on each item. For example:

map(my_units, hitpoints)

will give a list back with the number of hitpoints each unit has. This is more useful in conjunction with other functions.

==== 'max' function ====

<number> = max( <list of numbers> )

Function will return maximal number from a list,

max( [ 2, 8, -10, 3] )

will return 8.

==== 'max_possible_damage' function ====

<number> = max_possible_damage( <attacking unit> , <defending unit> )

Function returns highest possible damage that <attacking unit> can inflict to <defending unit>.

==== 'min' function ====

<number> = min( <list of numbers> )

Function will return minimal number from a list,

min( [ 3, 7, -2, 6] )

will return -2.

==== 'move' function ====

<action> = move( <source> , <destination> )

For example unit formula like:

move(me.loc, loc(me.loc.x, me.loc.y - 1) )

will make unit move one hex north.

==== 'nearest_keep' function ====

<keep location> = nearest_keep( <input location> )

Function returns location of nearest keep to the specified <input location>, or null if there is no keep on the map.

==== 'recruit' function ====

<action> = recruit( <unit name> [, <location> ] )

This function results in recruting a unit specifed by <unit name> at first free castle hex, or at given <location>. Function:

recruit('Footpad', loc(3,3) )

will result in recruting Footpad at castle hex with coordinates 3,3.

==== 'set_var' function ====

<action> = set_var( <key> , <value> )

This action sets new variable, for example:

set_var( 'Number one' , 1 )

Will create variable with name 'Number one' and assign 1 to it.

==== 'size' function ====

<number> = size( <list of variables> )

This function returns how many variables are stored in a list:

size( [ 5, 7, 9] ) #return 3
size( [ 'Archer', 'Fighter' ] ) #return 2

==== 'sort' function ====

<result list> = sort( <input list> , <formula> )

This function evaluates to a <result list> sorted according to the comparison <formula> for each item 'a' and its successor 'b'. For instance, sorting units according to hitpoints would be done by:

sort( my_units, a.hitpoints > b.hitpoints )

==== 'sum' function ====

<number> = sum( <list of numbers> )

This function evaluates to the sum of the items in the <list of numbers>. For example

sum( [ 2, 5, 8] )

returns 15, and:

sum( map( my_units, max_hitpoints - hitpoints ) )

finds the total damage your units have taken.

==== 'switch' function ====

<result> = switch( <variable>, <value 1>, <outcome 1>, ... , <value N>, <outcome N> [, <default outcome> ] >

Switch funtion takes variable, and checks if it is equal to any of the specified <values>. If matching value is found, <outcome> assigned to it is returned, if not, then function returns either <default outcome> (if specified) or null.

==== 'unit_at' function ====

<unit> = unit_at( <location> )

This function takes only one argument - location, and returns unit if there is one standing in that location, or null otherwise. Example of usage:

unit_at( loc( 4, 4) )

==== 'unit_moves' function ====

<locations list> = unit_moves( <unit location> )

Function returns list of all possible locations which unit standing at <unit location> can reach. If unit can't move, or there is no unit standing at given location, empty list is returned.

==== 'units_can_reach' function ====

<units list> = units_can_reach( <possible moves list>, <location> )

Function takes as an input list of possible moves ( ai.my_moves for units that belong to AI, or ai.enemy_moves for units that belong to the opponent ) and checks which units from that list can reach <location>.

=== Custom Functions ===

* You can define your own functions. A function is a formula which takes some inputs as parameters. Suppose we wanted to define a function that puts some value on a unit, we might add the following to the [ai] tag:

[function]
name=value_unit
inputs="unit"
formula="unit.hitpoints + unit.level*4"
[/function]

This has defined a new function which takes a 'unit' as an input, and runs the given calculation over it.

* We can have multiple inputs in our functions, to define them, just create comma-separated inputs list:

inputs="attacker,defender"

This has defined a new function which takes both 'attacker' and 'defender' as an inputs.

* Sometimes, we use one of our inputs really often in our function - to make our life easier we can make its members (inputs) directly accessible from within the formula. This is improved version of function from above:

[function]
name=value_unit
inputs="unit*"
formula="hitpoints + level*4"
[/function]

As you can see, if we define input with a * char at the end, we make it a 'default input' for a formula. Note, that you can define only one default input per function.

* It is important to know difference between formulas defined in custom functions, and formula defined by a 'move=' in a [ai] tag. For example, if we want to get info about leader, we write in formula 'my_leader' - which acces member of the AI. To be able to use 'my_leader' in custom functions we have to add 'ai' as an input for our function:

inputs="ai"

allows us to access leader info by writing 'ai.my_leader', or:

inputs="ai*"

allows us to access leader info by simply writing 'my_leader'

* You can also use 'def' [[#Keywords|keyword]] to define custom functions

=== Comments ===

Comments in Formula AI scripts are enclosed by {}:

{Define opening move}
def opening(*ai)
if(turn = 1,
move(loc(11,23), loc(14,22)),
[])

Comments may also be included at the end of a line:

def opening(*ai)
if(turn = 1,
move(loc(11,23), loc(14,22)), {capture village}
[]) {do nothing}

and they may also be used inline:

def opening(*ai)
if(turn = 1,
move(loc(11,23) {my_leader}, loc(14,24) {closest village}),
[]) {do nothing}

== Keywords ==

The formula language has some reserved keywords to provide primitive functionality. Currently the following keywords are defined:

* where: This keyword is used to defining statements in formulas. You can define multiple comma-separated statements. Syntax:

<formula> where <comma-separated list of statements>

For example formula:

a + b where a = 2, b = 4

will give as result 6.

* functions: Returns a list of all built-in and custom functions available to the AI

* def: This keyword creates functions using the syntax:

def function_name(arg1, arg2, ....) function_body

For example,

def sum(x,y) x + y

creates a function sum taking two arguments and returns their sum.

== Unit Formulas ==

You san specify a formula for any kind of unit. This is a simple way of doing it:

[unit]
...
formula="move(me.loc, loc(me.loc.x, me.loc.y - 1))"
[/unit]

Custom unit formulas are executed first at the begining of side's turn. Above formula will simply move unit one hex to the north every turn. Note how "me" keyword allows access to unit itself.

You can also define AI unit-specific variables and use them in you formulas:

[unit]
...
formula="if(attack, attack, move(me.loc, choose(unit_moves(me.loc), -distance_between(self, me.vars.guard_loc))))
where attack = choose(filter(attacks, units = [me.loc] and distance_between(me.vars.guard_loc, target) <= me.vars.guard_radius), avg_damage_inflicted)"
[ai_vars]
guard_radius=3
guard_loc="loc(8,5)"
[/ai_vars]
[/unit]

This formula will get location position from variable guard_loc and make sure that unit attacks opponent which is 3 hexes (value specified by guard_radius variable) or less from guard_loc.

Types of variables that are supported:
*number:
variable=3
*text (important: note the ' ' within " "):
name="'I am variable'"
*list:
number_list=[ 1, 2, 3]
*location:
place="loc(X,Y)"

= Tool Support =

== ctags ==

For some rudimentary support for exuberant ctags, add the following to .ctags (or create the file if it doesn't exist):

--langdef=formulaai
--langmap=formulaai:.fai
--regex-formulaai=/^def[ \t]*([a-zA-Z0-9_]+)/\1/d,definition/

This is especially nice when used with an editor or plugin with ctags support, such as Taglist for Vim.

== Vim ==

===Syntax Highlighting===

Follow these steps to enjoy vim syntax highlighting support for Formula AI.

# Grab the Formula AI vim syntax file, [http://svn.gna.org/viewcvs/*checkout*/wesnoth/trunk/data/tools/vim/formulaai.vim formulaai.vim].
# Copy formulaai.vim to .vim/syntax
# Add the following to .vimrc :
autocmd! BufRead,BufNewFile *.fai setfiletype formulaai

===Taglist Support===

First you will need the very nice [http://www.vim.org/scripts/script.php?script_id=273 taglist plugin]. Follow the link for downloads and install directions if you don't already have it installed.

Next, you'll need Formula AI support for exuberant ctags, follow the instructions in the [[#ctags|ctags]] section.

Once you have all that, simply add the following line to your .vimrc:

let tlist_formulaai_settings = 'formulaai;d:definition'

To test it all out, open a Formula AI script file and enter the command
:Tlist

You should now have some nice highlighting and be able to easily navigate through formula, enjoy!

[[Category:Development]]

[[Category:Development]]

FormulaAIandAdaptation

2008-03-30T21:27:36Z

Alesis-Novik:

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units.
===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible)

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Commits==
*An additional formula and functions in pathutil [http://svn.gna.org/viewcvs/wesnoth?rev=25349&view=rev]

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-03-30T17:38:24Z

Alesis-Novik:

==Personal Information==
I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest in AI and plan to work on that in the near future and I am eager to learn. Out of the more interesting things that I have programmed I could point out an algorithmic, non-bruteforce SuDoku solver, a Mastermind solver and a Java 3d pipeline.

==The Idea==
Create a FormulaAI based AI for Wesnoth. Write additional FormulaAI syntax if needed for a better AI. Provide the non-programmer users a simple way to define special characteristics of the AI that would override the default AI preferences (for example make a certain story unit behave in some specific way).

==Details==
After the discussions about the AI on the IRC, I was reading up and thought about an, in my opinion, interesting approach to the problem. First of all, from playing the game and talking to other player (done before summer begins) we get the idea of tactics and ideas they use while playing. We also need to make the AI be able to add to the tactic and strategy base on its own considering the outcome of each move. Obviously, with the mass of the possible options in the game, the full base would never be completed, so we need to use another method to ensure the effect. The AI would not only have the information on the tactics, but a large base of environment relations (like how one unit scales with the other and the land effect on them). Based on the current case, the strategy and tactics base and the world information it would compare and scale how close to a successful plan it can get from the current state, a similarity engine, if you will (for example, if one powerful unit could defeat the enemy, and we have two weaker units, maybe their combined power can defeat the enemy too). This type of strategy is a valid option in a TBS AI development and was used in other games like Civilization. Of course, there will always be some uncertainty, and that will be solved with probabilistic reasoning.
===The Case (Strategy and tactics) base===
This would be the plan and strategy base, updated on each action taken. The base plans and tactics would be inserted from user experience. The others the AI would formulate itself, with probability of success. After setting the major goal, such as defence or attack, the AI could use genetic algorithms to evaluate or create the best plan. Since the variations are too great, there would be an iteration limit set (this could also relate to difficulty: the harder the opponent, the more iterations).
===The Knowledge Base===
This would hold the information on every aspect of the game and would be updated with user created content as available. For example it would know that some two units are both archers, along with their statistics. This is quite straight forward: arrays of information on units (probably split into logical groups) with connections between (so we can select healers from elves or elves from healers, depending on how we sort them. The knowledge base would also hold information on terrain effects on units.
===The Similarity Engine===
This would compare the existing plans to the available resources and choose the best solution. For example, if we know that two fighters can defeat an enemy, it scales what are the chances of, lets say a fighter and a healer or two rangers. It wouldn't chose what looks closer, but what *looks better* (lets say in this case, the two rangers). Simple evaluation function could look something like (unit.hitpoints/hitpoints_in_plan * i + unit.damage/damage_in_plan * j) where i and j would be based on priorities (to survive or to do more damage)

==Timeline==
*The first part would be to integrate the knowledge base to the AI, since it would need grouping and connections.
*The second part would be to write a case base so it could store plans and create new plans, along with the probability of success.
*The third part would be to write effective evaluation functions along with a probability engine to calculate success rate of possible plans. This may be done by using the Monte Carlo method (it is used when there are large arrays of data and discreet calculations are impossible)

==Overall==
The result should be an AI with both overall and detailed customization (e.g. overall would be aggressive or defensive and detailed would be guarding or assassinating) and adaptiveness to new strategic plans and user created content.

==Other==
On a side note, I'd like to say that I am really interested in game development and would gladly continue working on Wesnoth after Google Summer of Code. Also, the reason why I can't contribute much now is that I have to attend the university and we are having some midterm exams, so I need to study a bit.
[[Category:Summer of Code]]

FormulaAIandAdaptation

2008-03-24T23:24:34Z

Alesis-Novik: /* Details */

FormulaAIandAdaptation

2008-03-20T22:00:24Z

Alesis-Novik: /* Details */

FormulaAIandAdaptation

2008-03-20T17:49:20Z

Alesis-Novik: New page: ==Personal Information== I am Alesis Novik, a computer science student. My IRC name is Alesis-Novik. I am quite good at programming c++ and writing effective algorithms. I hold an interest...

SummerOfCodeIdeas

2008-03-20T17:27:05Z

Alesis-Novik: /* FormulaAIandAdaptation (Alesis-Novik) */

This is a compilation of ideas from ML. Needs to be refined (more detailed description, deliverables, workload estimation?):

== I want to be one of your Google Summer of Code students, what should I do... ==

Here is a quick list of things to do to get you started
* Create an account on gna.org
* Create an account on the wesnoth forum
* Join the irc channel (#wesnoth-dev on irc.freenode.net) and introduce yourself. We will not give formal interviews, but we will clearly favor people we have learnt to know during the selection process
* Contact one of our SummerOfCode people (Ivanovic, Sirp, Boucman, Mordante) to have your forum nick marked as a Summer of code student

* Start a wiki page about your idea, add a link on the bottom of this page and add this information on it:
** List your account names (gna, forum, irc nick) so that we can recognize you
** Fill the questionnaire on this page: [[SoC_Information_for_Google#Does_your_organization_have_an_application_template_you_would_like_to_see_students_use.3F_If_so.2C_please_provide_it_now.| List of questions to answer]]
** Detail your idea as much as possible, look at other students pages, and please give milestones and studies you've done

* Though not mandatory, it is highly advisable to go to the [[EasyCoding]] and [[NotSoEasyCoding]] pages and implement one of these ideas (or any idea of similar scope) so we have an idea how you work. Be sure to use your gna account when submitting these patches so we know who it is coming from. You can also implement some features from our feature request database at gna. When you implement something, also list it on your own page with a reference to the patch.

== List of Ideas for the Project (Suggestions from the wesnoth developers) ==

Here is only a short description of possible Ideas we have, each has a page of its own with a more detailed version on it.

=== Writing an AI based on the formula AI ===

Wesnoth has always had a simple C++ based AI. David (our lead developer) has been working on a simple language to write AI in Wesnoth: [[FormulaAI]]

The Wesnoth AI is used as an opponent in most campaigns, and as such is an important piece of code for the Wesnoth project. Unfortunately, because the skills required to understand and modify it are rather arcane, it is also one of the most neglected parts of the Wesnoth code. This is a place where a lot of research and useful work could be done. But keep in mind that [[WhyWritingAWesnothAIIsHard|writing an AI for Wesnoth is difficult]].

[[SoC Ideas FormulaAI]] - Full version of the idea, with detailed information

=== Extending the Multiplayer server ===

Our multiplayer community is generally strong and healthy, but we believe its growth is limited by some problems in the interface of the multiplayer lobby.

[[SoC Ideas Multiplayer server]] - Full version of the idea, with detailed information

=== Scenario/Campaign editor ===

Currently, in order to create campaign or multiplayer scenarios, it is necessary to manually edit WML files - XML-like configuration files. The goal of this project would be to create a graphical editor to make the creative process easier.

[[SoC Ideas Scenario and Campaign Editor]] - Full version of the idea, with detailed information

=== Addon server ===
Wesnoth has an addon server which offers users to upload user
made content (UMC). This allows all other users of Wesnoth
to easily download and install this content. The server was
originally written for user-made campaigns but contains a lot
more types of addons nowadays. Both the server side and the
client side need to be improved.

[[SoC Ideas Addon Server]] - Full version of the idea, with detailed information

=== Map editor ===
The map editor in Wesnoth serves two goals, making it easy to create
a new map and helping the terrain artists to test their new terrains.

[[SoC_Ideas_Map_Editor]] - Full version of the idea, with detailed information

=== Other possible ideas to be fleshed out ===
A MapGenerator rewrite - better scalable for outdoor maps, plus the possibility to define areas (similar to the caverns in the cave generator) etc.

=== Make your own ideas ===
If you have your own idea the best thing is to join IRC wesnoth-dev at irc.freenode.net and discuss the idea with the developers there. If the developers think your idea is interesting and like the feature you can start to turn it into a full proposal. Once done discuss it again on IRC so the developers can accept your idea.

== Information about our Project ==
The information we provided google with about our project can be looked up at the site [[SoC Information for Google]].

== People to bug on IRC ==
We have prepared a list of people with their "area of competence". This is to give you an idea on which areas those people can be of help for you. Of course you should always just ask in the IRC chan, but those are the most likely ones to answer questions in the respective area. And here is the list:

[[SoC People to bug on IRC]]

== GSoC Student Applicant Ideas ==

Every student interested to work on Wesnoth as part of Summer of Code should create a page of his own where several things should be listed. Here is a short list of what should be mentioned on the list (the more info for us, the better...):

* Who are you? Please list your IRC and forum nickname in here and describe yourself so that we get you to know.
* What do you want to work on? Please flesh out your personal ideas, so that we get to know what you plan to work on.
* If you already submitted patches, please list those so that we have a reference.

=== [[FormulaAIandDynamicScripting]] (barbarianhero) ===
This project idea uses Formula AI and Dynamic Scripting to create a tunable and adaptive AI.

===[[FormulaAIandAdaptation]] (Alesis-Novik) ===
The new idea and aproach using strategic and inside game knowledge

===[[ExtensibleScenarioEditor]] (david.hilton) ===
On a conceptual level, this idea combines a finite state machine editor with a code generator to create scenarios.

===[[RandomCampaignGenerator]] (kartik thakore) ===
Procedural Campaign generation that combines random map generation, story generation, and strategy generation.

===[[LaoSoCIdeas]] by lao ===
Under Construction...

===[[AddonServer]] (giebfried) ===
This project is to improve the server and client sides of the addon server, as suggested above.

===[[EvolutionaryMapEditor]] (xonev) ===
Under Construction
[[Category:Summer of Code|*]]

SummerOfCodeIdeas

2008-03-18T17:59:32Z

Alesis-Novik: /* GSoC Student Applicant Ideas */

This is a compilation of ideas from ML. Needs to be refined (more detailed description, deliverables, workload estimation?):

== I want to be one of your Google Summer of Code students, what should I do... ==

Here is a quick list of things to do to get you started
* Create an account on gna.org
* Create an account on the wesnoth forum
* Join the irc channel (#wesnoth-dev on irc.freenode.net) and introduce yourself. We will not give formal interviews, but we will clearly favor people we have learnt to know during the selection process
* Contact one of our SummerOfCode people (Ivanovic, Sirp, Boucman, Mordante) to have your forum nick marked as a Summer of code student

* Start a wiki page about your idea, add a link on the bottom of this page and add this information on it:
** List your account names (gna, forum, irc nick) so that we can recognize you
** Fill the questionnaire on this page: [[SoC_Information_for_Google#Does_your_organization_have_an_application_template_you_would_like_to_see_students_use.3F_If_so.2C_please_provide_it_now.| List of questions to answer]]
** Detail your idea as much as possible, look at other students pages, and please give milestones and studies you've done

* Though not mandatory, it is highly advisable to go to the [[EasyCoding]] and [[NotSoEasyCoding]] pages and implement one of these ideas (or any idea of similar scope) so we have an idea how you work. Be sure to use your gna account when submitting these patches so we know who it is coming from. You can also implement some features from our feature request database at gna. When you implement something, also list it on your own page with a reference to the patch.

== List of Ideas for the Project (Suggestions from the wesnoth developers) ==

Here is only a short description of possible Ideas we have, each has a page of its own with a more detailed version on it.

=== Writing an AI based on the formula AI ===

Wesnoth has always had a simple C++ based AI. David (our lead developer) has been working on a simple language to write AI in Wesnoth: [[FormulaAI]]

The Wesnoth AI is used as an opponent in most campaigns, and as such is an important piece of code for the Wesnoth project. Unfortunately, because the skills required to understand and modify it are rather arcane, it is also one of the most neglected parts of the Wesnoth code. This is a place where a lot of research and useful work could be done.

[[SoC Ideas FormulaAI]] - Full version of the idea, with detailed information

=== Extending the Multiplayer server ===

Our multiplayer community is generally strong and healthy, but we believe its growth is limited by some problems in the interface of the multiplayer lobby.

[[SoC Ideas Multiplayer server]] - Full version of the idea, with detailed information

=== Scenario/Campaign editor ===

Currently, in order to create campaign or multiplayer scenarios, it is necessary to manually edit WML files - XML-like configuration files. The goal of this project would be to create a graphical editor to make the creative process easier.

[[SoC Ideas Scenario and Campaign Editor]] - Full version of the idea, with detailed information

=== Addon server ===
Wesnoth has an addon server which offers users to upload user
made content (UMC). This allows all other users of Wesnoth
to easily download and install this content. The server was
originally written for user-made campaigns but contains a lot
more types of addons nowadays. Both the server side and the
client side need to be improved.

[[SoC Ideas Addon Server]] - Full version of the idea, with detailed information

=== Map editor ===
The map editor in Wesnoth serves two goals, making it easy to create
a new map and helping the terrain artists to test their new terrains.

[[SoC_Ideas_Map_Editor]] - Full version of the idea, with detailed information

=== Other possible ideas to be fleshed out ===
A MapGenerator rewrite - better scalable for outdoor maps, plus the possibility to define areas (similar to the caverns in the cave generator) etc.

=== Make your own ideas ===
If you have your own idea the best thing is to join IRC wesnoth-dev at irc.freenode.net and discuss the idea with the developers there. If the developers think your idea is interesting and like the feature you can start to turn it into a full proposal. Once done discuss it again on IRC so the developers can accept your idea.

== Information about our Project ==
The information we provided google with about our project can be looked up at the site [[SoC Information for Google]].

== People to bug on IRC ==
We have prepared a list of people with their "area of competence". This is to give you an idea on which areas those people can be of help for you. Of course you should always just ask in the IRC chan, but those are the most likely ones to answer questions in the respective area. And here is the list:

[[SoC People to bug on IRC]]

== GSoC Student Applicant Ideas ==

Every student interested to work on Wesnoth as part of Summer of Code should create a page of his own where several things should be listed. Here is a short list of what should be mentioned on the list (the more info for us, the better...):

* Who are you? Please list your IRC and forum nickname in here and describe yourself so that we get you to know.
* What do you want to work on? Please flesh out your personal ideas, so that we get to know what you plan to work on.
* If you already submitted patches, please list those so that we have a reference.

=== [[FormulaAIandDynamicScripting]] (barbarianhero) ===
This project idea uses Formula AI and Dynamic Scripting to create a tunable and adaptive AI.

===[[FormulaAIStancesSearchandEvaluation]] (andrewbwm) ===
This project implements Unit Behavioral Stances that are determinet by Search & Evaluation algorithms to determine a flexibile AI.

===[[FormulaAIandThinkingAhead]] (Alesis-Novik) ===
This project idea uses methods to make the AI *think* ahead.

[[Category:Future]]