Category:Summer of Code 2013 Student Page - Revision history

Iceiceice at 11:36, 7 April 2014

2014-04-07T11:36:39Z

PL kolek: Blanked the page

2013-05-01T13:34:58Z

Blanked the page

PL kolek: Created page with '{{User:PL_kolek}} Category:SoC Ideas AI Defense Strategies 2013 WARNING: Unfinished =Description=

PL_kolek - AI 'total defense strategy'

My goal is to make AI pla…'

2013-05-01T10:44:03Z

Created page with '{{User:PL_kolek}} Category:SoC Ideas AI Defense Strategies 2013 WARNING: Unfinished =Description= <h4>PL_kolek - AI 'total defense strategy' </h4> My goal is to make AI pla…'

New page

{{User:PL_kolek}}
[[Category:SoC Ideas AI Defense Strategies 2013]]

WARNING: Unfinished

=Description=
<h4>PL_kolek - AI 'total defense strategy' </h4>
My goal is to make AI play more cautiously. Currently it only
tries to kill as many units as possible without taking into account possible enemy moves. I'm going to build into the current algorithm some mechanism to improve AI behavious.

==Heuristics to evaluate enemy response==
First and most important step in making AI smarter is teaching it to take into account enemy actions in the following turn (by turn I mean what happens direcly after I click 'end turn'). In a perfect world that would suffice - we could even learn from the computer new tactics for ideal balance between my and enemy losses. But we all know that Wesnoth game tree branches so quick, that PCs cannot even check all it's possible moves, not to mention the next level of the tree. To siplify calculations, RCA AI takes unit after unit, move after move and considers them in separation. While it decreases complexity exponentially, it makes is impossible to think about setting up a wall, backstabbing and so on. Assuming the AI doesn't change it in the next few months, we need to quickly evaluate our losses in enemy's turn. For that we need something like:
===[Damage_estimation] tag===
While finding (with experiments) 'the best' evaluation algorithm and making the AI use it a good solution, why not let the user/developer choose or even write it on his own? This way scenario creator could choose more accurate (but computation heavy) algorithm in small scenario and lightweight (but less accurate) for bigger ones.
===[Iterative_damage_estimation] tag===
That's similar to previous tag, but this function takes previous map situation and evaluation, a move and calculates new one from that data. That's different from former approach, because it required recalculating everything after every move. This one should evaluate only subset of data, and thus will be faster. On the other hand, I still don't know if such iterative approach is possible in the world of wesnoth AI. If it turns out that it doesn't fit at all, I'll drop that tag.
===[Estimation constant]===
The less accurate we estimate, the smaller damage we predict. Set this constant to 1.25 (or some other magic value) and the results should be in proximity of real outcome. Simple, but better than current magic 'aggression constant'.

Now some proposals for damage_estimation algorithms:
===Simulate enemy turn===
Simplify a lot CAs, cut out not needed and play it! Simple idea, providing that AI is really good at killing things, the results will be accurate. But... the CPU will burn. With some work, maybe on little 1 vs 1 maps it would work.
===Farthest first heuristic===
Order units from the farthest, choose best attack possible, evaluate outcome. The order is chosen that way, so that no unit will be blocked from its attack by other units having more possibilities.

=IRC=
put ONLY your irc nickname in there. in case of alternate nicks, separate by ,

Example content of this section: "user" "user1, user2" (without the quotes)

=Questionnaire=
TODO: fill out the questionnaire, on your copy of this page. Question are here : [[SoC_Information_for_Google#Does your organization have an application template you would like to see students use?]]

← Older revision	Revision as of 11:36, 7 April 2014
Line 1:	Line 1:
−	+	[[Category:Summer_of_Code_2013]]

← Older revision		Revision as of 13:34, 1 May 2013
Line 1:		Line 1:
−	~~{{User:PL_kolek}}~~
−	~~[[Category:SoC Ideas AI Defense Strategies 2013]]~~

−	~~WARNING: Unfinished~~
−
−	~~=Description=~~
−	~~<h4>PL_kolek - AI 'total defense strategy' </h4>~~
−	~~My goal is to make AI play more cautiously. Currently it only~~
−	~~tries to kill as many units as possible without taking into account possible enemy moves. I'm going to build into the current algorithm some mechanism to improve AI behavious.~~
−
−	~~==Heuristics to evaluate enemy response==~~
−	First and most important step in making AI smarter is teaching it to take into account enemy actions in the following turn (by turn I mean what happens direcly after I click 'end turn'). In a perfect world that would suffice - we could even learn from the computer new tactics for ideal balance between my and enemy losses. But we all know that Wesnoth game tree branches so quick, that PCs cannot even check all it's possible moves, not to mention the next level of the tree. To siplify calculations, RCA AI takes unit after unit, move after move and considers them in separation. While it decreases complexity exponentially, it makes is impossible to think about setting up a wall, backstabbing and so on. Assuming the AI doesn't change it in the next few months, we need to quickly evaluate our losses in enemy's turn. For that we need something like:
−	~~===[Damage_estimation] tag===~~
−	While finding (with experiments) 'the best' evaluation algorithm and making the AI use it a good solution, why not let the user/developer choose or even write it on his own? This way scenario creator could choose more accurate (but computation heavy) algorithm in small scenario and lightweight (but less accurate) for bigger ones.
−	~~===[Iterative_damage_estimation] tag===~~
−	That's similar to previous tag, but this function takes previous map situation and evaluation, a move and calculates new one from that data. That's different from former approach, because it required recalculating everything after every move. This one should evaluate only subset of data, and thus will be faster. On the other hand, I still don't know if such iterative approach is possible in the world of wesnoth AI. If it turns out that it doesn't fit at all, I'll drop that tag.
−	~~===[Estimation constant]===~~
−	The less accurate we estimate, the smaller damage we predict. Set this constant to 1.25 (or some other magic value) and the results should be in proximity of real outcome. Simple, but better than current magic 'aggression constant'.
−
−	~~Now some proposals for damage_estimation algorithms:~~
−	~~===Simulate enemy turn===~~
−	Simplify a lot CAs, cut out not needed and play it! Simple idea, providing that AI is really good at killing things, the results will be accurate. But... the CPU will burn. With some work, maybe on little 1 vs 1 maps it would work.
−	~~===Farthest first heuristic===~~
−	~~Order units from the farthest, choose best attack possible, evaluate outcome. The order is chosen that way, so that no unit will be blocked from its attack by other units having more possibilities.~~
−
−
−
−
−	~~=IRC=~~
−	~~put ONLY your irc nickname in there. in case of alternate nicks, separate by ,~~
−
−	~~Example content of this section: "user" "user1, user2" (without the quotes)~~
−
−	~~=Questionnaire=~~
−	~~TODO: fill out the questionnaire, on your copy of this page. Question are here : [[SoC_Information_for_Google#Does your organization have an application template you would like to see students use?]]~~