A
A
Albert2015-01-12 00:06:03
Programming
Albert, 2015-01-12 00:06:03

I came up with a board game, what algorithm would you recommend for an opponent-bot?

Dots
A game for two players in which the players take turns trying to guess the location of the dots drawn by the opponent on the opponent's map.
Playing fields - 50-cell rectangles, 10 "verticals" by 5 "horizontals".
3f1443a15f354e02be1430501fe7598d.png
Cells of each horizontal are assigned "numbers" 1..10, numbering from left to right.
Each player draws 5 dots on his field (or marks cells in a different way), one on each horizontal line.
The location of the points on the field is expressed by the sequence of "numbers" of cells starting from the top (first) horizontal and ending with the bottom (fifth).
Move. Player A in one move names 2 options for the alleged location of points on the field of player B. Player B points out to player A the option that is closest to the guess. Let player A named Option 1 and Option 2. Then player B does the following:
for each horizontal, finds the absolute difference between the numbers of the marked cell and the cell, according to Variant 1, these five values ​​are added up = Result1;
the same operations are carried out with the numbers of the marked cell and the cell according to option 2 = Result2;
Result1 and Result2 are compared. If Result1<Result2, then Option1 was closer to the conceived variant.
bc93b93443b343c28b99cf72c7c6e1a9.png
If Outcome1=Outcome2, then player B declares that both options are equally close to the guess.
After that, another player's turn begins, and so on until one of the options matches the guessed location of points on the opponent's field. Here, 2 types of the game are provided: 1) the end of the game, 2) "guessing to the end" - determining the location of the opponent's points by the losing player (without moving the move)

Answer the question

In order to leave comments, you need to log in

3 answer(s)
A
Azim Kurt, 2015-01-12
@Symphony

A game for two participants in which the players take turns trying to guess the location of the dots drawn by the opponent on the opponent's map.

Look at the algorithm of the game "Sea Battle"

X
xmoonlight, 2015-01-12
@xmoonlight

You blew my mind!

P
Pavel, 2015-01-12
@ProgramCodePav

There is just an idea :)
You can make a lot of the most effective (or in terms of complexity) samples in advance. And also the bot will write each applied sample to a file. On the basis of the file data, the opponent's pseudo-cunning algorithm can be implemented. For example, 3 times one sample (or similar) works, and the fourth time the worst sample for the player, which will adapt to the previous 3 options. Also, for one of the 5 variants of the bot, you can make it random. That's all for the first step.
Next, we need a small study of effectiveness. In general, a bot can cheat, but if the game is fair, then the algorithm must be human.
For example, the first step:
option 1 and 2 start exactly in the center, but option 2 is 1 cell to the right in the upper horizontal to evaluate the difference in the upper horizontal. If less, then next time - twice to the left.
The second example comes out of the first: you can first check all 5 contour lines, pushing to the left and right only one point in option B.
Yes, the first option turns out to be idle, which is not good, but it gives accuracy in the assessment.
Second stage:
After evaluating all the contour lines, all answer options can be sharply pushed in positive directions (for example, 5 points of option 1, all to the edge - left, right, left, left, left - this is based on the analysis of the results of the first stage, and 5 points of option 2 is the same as option 1, but divided by 2).
Third stage: (fail)
combine options 1 and 2 step by step.
for example, option 1 won more than option 2.
Let me remind you the location of option 1 (from the center): left, right, left, left, left.
And this is the location of option 2 (from the center): left / 2, right / 2, left / 2, left / 2, left / 2.
So the first (upper) horizontal line of variant 2 moves to the left by a distance to the left / 4 (that is, to a cell). If you ... then I broke down :) because the returned data is not numbers, but bool. (I'll try to think it out, I'll just give an answer better in an earlier way, suddenly you catch the direction and do it better)
-----------
Another algorithm: sequential.
The first stage is similar to the previous algorithm, that is, both options are equally located with a deviation of one cell, on one horizontal line, then on the other and to the end to collect data.
The difference is that if option 2 explores the map, then option 1 goes to the winning point along with option 2.
for example:
Location of all points, step 1:
Option 1 <=> option 2
Center <=> Center + 1 cell to the right
Center <= > Center
Center <=> Center
Center <=> Center
Center <=> Center
Option 2 won. So in the first horizontal line, the standard point becomes Center + 1 cell to the right. That is:
Location of all points, step 2:
Option 1 <=> option 2
Center + 1 cell right <=> Center + 1 cell right
Center <=> Center + 1 cell right
Center <=> Center
Center <=> Center
Center <=> Center
Option 2 lost.
Location of all points, step 3:
Option 1 <=> option 2
Center+1cell right<=> Center+1cell right
Center <=> Center+1cell left
Center <=> Center
Center <=> Center
Center <=> Center
If option 2 lost, then the point of the second horizontal was in the center. And in this way.
--
Pros and cons. The first option, obviously, is more efficient, but it is not thought out to the end, and the second option is 100% working, but quite long.
Of course, you can combine options 1 and 2. Thus, after the first stage (evaluation of cells closest to the center), you can move the points to the extreme positions.
What I haven't thought through - there is probably a way to use both options, not when one is idle :)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question