Mixing
How to write a good heuristic function
0
$begingroup$
I have a game, that works based on the following rulesets:
- I have a 3x3 size board, with enemies on some of the spaces
- Each enemy has a type, and 3 values, to differentiate between them: health [H], armor [A], and activation cost [E]
- There can be multiple simmilar enemies on the board
- I have
xnumber of heroes, each with different types of actions, actions that can interract with these enemies on the board. The heroes are not tied to the board, they are not on it, and will never be a part of the board. The board, and the position of the enemies, only matter, when deciding which hero action is usable against them, or not (ie. if the enemy is in range for an action, or not) - In each turn, a single hero, will perform a single action, on one or more enemies on the board, which will result in the enemies losing health, and possibly losing activation cost
- After all the heroes performed a single action, all the enemies will lose activation cost, based on the number of heroes in the game: this is called a cleanup.
- After a hero performed an action or after a cleanup, if any enemy has a zero activation cost, it will activate, and possibly change position, then reset it's activation cost to the initial value.
- After
ynumber of hero turns and cleanups, I will fetch all resulting board states, and I will have to decide (quantify) which board state is better then the other (this will be used for a heuristic function in a minimax algorithm). - The program should find the order of the hero actions, which will result in the least amount of monster activations, indifferent of the number of turns these actions will take.
There are easy decisions between states, and hard decisions.
For example, it's not hard to decide between this board [B1]
-------------------------------------------------------------
| | A [H: 7/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
compared to this board [B2]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
B1 board is definitely better then B2 board, because the top A monster lost more health, and everything else is the same.
But what about this board [B3]:
-------------------------------------------------------------
| | A [H: 6/9 A: 1/1 E: 1/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
and this board [B4]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
On board B4 the top monster lost less health then on board B3, but he is 2 activation costs away from activation, instead of 1.
My problem is, that I can't find the correct connection between the numbers I have, to write a function which can quantify the board. Is there any surefire way how to do this?
optimization puzzle
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
$endgroup$
add a comment |
0
$begingroup$
I have a game, that works based on the following rulesets:
- I have a 3x3 size board, with enemies on some of the spaces
- Each enemy has a type, and 3 values, to differentiate between them: health [H], armor [A], and activation cost [E]
- There can be multiple simmilar enemies on the board
- I have
xnumber of heroes, each with different types of actions, actions that can interract with these enemies on the board. The heroes are not tied to the board, they are not on it, and will never be a part of the board. The board, and the position of the enemies, only matter, when deciding which hero action is usable against them, or not (ie. if the enemy is in range for an action, or not) - In each turn, a single hero, will perform a single action, on one or more enemies on the board, which will result in the enemies losing health, and possibly losing activation cost
- After all the heroes performed a single action, all the enemies will lose activation cost, based on the number of heroes in the game: this is called a cleanup.
- After a hero performed an action or after a cleanup, if any enemy has a zero activation cost, it will activate, and possibly change position, then reset it's activation cost to the initial value.
- After
ynumber of hero turns and cleanups, I will fetch all resulting board states, and I will have to decide (quantify) which board state is better then the other (this will be used for a heuristic function in a minimax algorithm). - The program should find the order of the hero actions, which will result in the least amount of monster activations, indifferent of the number of turns these actions will take.
There are easy decisions between states, and hard decisions.
For example, it's not hard to decide between this board [B1]
-------------------------------------------------------------
| | A [H: 7/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
compared to this board [B2]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
B1 board is definitely better then B2 board, because the top A monster lost more health, and everything else is the same.
But what about this board [B3]:
-------------------------------------------------------------
| | A [H: 6/9 A: 1/1 E: 1/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
and this board [B4]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
On board B4 the top monster lost less health then on board B3, but he is 2 activation costs away from activation, instead of 1.
My problem is, that I can't find the correct connection between the numbers I have, to write a function which can quantify the board. Is there any surefire way how to do this?
optimization puzzle
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
$endgroup$
$begingroup$
I'm not sure I really understand the rules of the game, but it sounds like this might be formulated as a Markov Decision Process (MDP).
$endgroup$
– David M.
Jan 26 at 4:13
add a comment |
0
0
0
$begingroup$
I have a game, that works based on the following rulesets:
- I have a 3x3 size board, with enemies on some of the spaces
- Each enemy has a type, and 3 values, to differentiate between them: health [H], armor [A], and activation cost [E]
- There can be multiple simmilar enemies on the board
- I have
xnumber of heroes, each with different types of actions, actions that can interract with these enemies on the board. The heroes are not tied to the board, they are not on it, and will never be a part of the board. The board, and the position of the enemies, only matter, when deciding which hero action is usable against them, or not (ie. if the enemy is in range for an action, or not) - In each turn, a single hero, will perform a single action, on one or more enemies on the board, which will result in the enemies losing health, and possibly losing activation cost
- After all the heroes performed a single action, all the enemies will lose activation cost, based on the number of heroes in the game: this is called a cleanup.
- After a hero performed an action or after a cleanup, if any enemy has a zero activation cost, it will activate, and possibly change position, then reset it's activation cost to the initial value.
- After
ynumber of hero turns and cleanups, I will fetch all resulting board states, and I will have to decide (quantify) which board state is better then the other (this will be used for a heuristic function in a minimax algorithm). - The program should find the order of the hero actions, which will result in the least amount of monster activations, indifferent of the number of turns these actions will take.
There are easy decisions between states, and hard decisions.
For example, it's not hard to decide between this board [B1]
-------------------------------------------------------------
| | A [H: 7/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
compared to this board [B2]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
B1 board is definitely better then B2 board, because the top A monster lost more health, and everything else is the same.
But what about this board [B3]:
-------------------------------------------------------------
| | A [H: 6/9 A: 1/1 E: 1/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
and this board [B4]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
On board B4 the top monster lost less health then on board B3, but he is 2 activation costs away from activation, instead of 1.
My problem is, that I can't find the correct connection between the numbers I have, to write a function which can quantify the board. Is there any surefire way how to do this?
optimization puzzle
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
$endgroup$
I have a game, that works based on the following rulesets:
- I have a 3x3 size board, with enemies on some of the spaces
- Each enemy has a type, and 3 values, to differentiate between them: health [H], armor [A], and activation cost [E]
- There can be multiple simmilar enemies on the board
- I have
xnumber of heroes, each with different types of actions, actions that can interract with these enemies on the board. The heroes are not tied to the board, they are not on it, and will never be a part of the board. The board, and the position of the enemies, only matter, when deciding which hero action is usable against them, or not (ie. if the enemy is in range for an action, or not) - In each turn, a single hero, will perform a single action, on one or more enemies on the board, which will result in the enemies losing health, and possibly losing activation cost
- After all the heroes performed a single action, all the enemies will lose activation cost, based on the number of heroes in the game: this is called a cleanup.
- After a hero performed an action or after a cleanup, if any enemy has a zero activation cost, it will activate, and possibly change position, then reset it's activation cost to the initial value.
- After
ynumber of hero turns and cleanups, I will fetch all resulting board states, and I will have to decide (quantify) which board state is better then the other (this will be used for a heuristic function in a minimax algorithm). - The program should find the order of the hero actions, which will result in the least amount of monster activations, indifferent of the number of turns these actions will take.
There are easy decisions between states, and hard decisions.
For example, it's not hard to decide between this board [B1]
-------------------------------------------------------------
| | A [H: 7/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
compared to this board [B2]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
B1 board is definitely better then B2 board, because the top A monster lost more health, and everything else is the same.
But what about this board [B3]:
-------------------------------------------------------------
| | A [H: 6/9 A: 1/1 E: 1/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
and this board [B4]:
-------------------------------------------------------------
| | A [H: 8/9 A: 1/1 E: 2/3] | |
-------------------------------------------------------------
| | A [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
| | B [H: 9/9 A: 1/1 E: 3/3] | |
-------------------------------------------------------------
On board B4 the top monster lost less health then on board B3, but he is 2 activation costs away from activation, instead of 1.
My problem is, that I can't find the correct connection between the numbers I have, to write a function which can quantify the board. Is there any surefire way how to do this?
optimization puzzle
optimization puzzle
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
asked Jan 24 at 1:30
Adam BaranyaiAdam Baranyai
936
936
$begingroup$
I'm not sure I really understand the rules of the game, but it sounds like this might be formulated as a Markov Decision Process (MDP).
$endgroup$
– David M.
Jan 26 at 4:13
add a comment |
$begingroup$
I'm not sure I really understand the rules of the game, but it sounds like this might be formulated as a Markov Decision Process (MDP).
$endgroup$
– David M.
Jan 26 at 4:13
$begingroup$
I'm not sure I really understand the rules of the game, but it sounds like this might be formulated as a Markov Decision Process (MDP).
$endgroup$
– David M.
Jan 26 at 4:13
$begingroup$
I'm not sure I really understand the rules of the game, but it sounds like this might be formulated as a Markov Decision Process (MDP).
$endgroup$
– David M.
Jan 26 at 4:13
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3085316%2fhow-to-write-a-good-heuristic-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3085316%2fhow-to-write-a-good-heuristic-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I'm not sure I really understand the rules of the game, but it sounds like this might be formulated as a Markov Decision Process (MDP).
$endgroup$
– David M.
Jan 26 at 4:13