Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The ultimate naive solution wold be to go through every possible placement of ships (legal given what information is known) and counting the number of times each square is full.</p> <p>obviously, in a relatively empty board this will not work as there are too many permutations, but a good start might be:</p> <p>for each square on board: go through all ships and count in how many different ways it fits in that square, i.e. for each square of the ships length check if it fits horizontally and vertically.</p> <p>an improvement might be to also check for each possible ship placement if the rest of the ships can be placed legally whilst covering all known 'hits' (places known to contain a ship).</p> <p>to improve performance, if only one ship can be placed in a given spot, you no longer need to test it on other spots. also, when there are many 'hits', it might be quicker to first cover all known 'hits' and for each possible cover go through the rest.</p> <p>edit: you might want to look into DFS.</p> <p>Edit: Elaboration on OP's (@Dbz) suggestion in the comments: hold a set of dismissed placements ('dissmissed') of ships (can be represented as string, say <code>"4V5x3"</code> for the placement of length 4 ship in 5x3, 5x4, 5x5, 5x6), after a guess you add all the placements the guess dismisses, then for each square hold a set of placements that intersect with it ('placements[x,y]') then the probability would be: <code>34-|intersection(placements[x,y], dissmissed)|/(3400-|dismissed|)</code></p> <p>To add to the dismissed list:</p> <ol> <li>if guess at (X,Y) is a miss add <code>placements[x,y]</code></li> <li>if guess at (X,Y) is a hit: <ul> <li>add neighboring placements (assuming that ships cannot be placed adjacently), i.e. add: <ul> <li><code>&lt;(2,3a,3b,4,5)&gt;H&lt;X+1&gt;x&lt;Y&gt;</code>, <code>&lt;(2,3a,3b,4,5)&gt;V&lt;X&gt;x&lt;Y+1&gt;</code></li> <li><code>&lt;(2,3a,3b,4,5)&gt;H&lt;X-(2,3,3,4,5)&gt;x&lt;Y&gt;</code>, <code>&lt;(2,3a,3b,4,5)&gt;V&lt;X&gt;x&lt;Y-(2,3,3,4,5)&gt;</code></li> <li><code>2H&lt;X+-1&gt;x&lt;Y+(-2 to 1)&gt;</code>, <code>3aH&lt;X+-1&gt;x&lt;Y+(-3 to 1)&gt;</code> ...</li> <li><code>2V&lt;X+(-2 to 1)&gt;x&lt;Y+-1&gt;</code>, <code>3aV&lt;X+(-3 to 1)&gt;x&lt;Y+-1&gt;</code> ...</li> </ul></li> <li>if <code>|intersection(placements[x,y], dissmissed)|==33</code>, i.e. only one placement possible add ship (see later)</li> </ul></li> <li>check if any of the previews hits has only one possible placement left, if so, add the ship </li> <li>check to see if any of the ships have only possible placement, if so, add the ship </li> </ol> <p>adding a ship:</p> <ul> <li>add all other placements of that ship to dismissed</li> <li>for each (x,y) of the ships placement add <code>placements[x,y]</code> with out the actual placement</li> <li>for each (x,y) of the ships placement mark as hit guess (if not already known) run stage 2</li> <li>for each (x,y) neighboring the ships placement mark as miss guess (if not already known) run stage 1</li> <li>run stage 3 and 4.</li> </ul> <p>i might have over complicated this, there might be some redundant actions, but you get the point.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow to generate statistically probably locations for ships in battleship
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpseudoDust
    1. USpseudoDust
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow to generate statistically probably locations for ships in battleship
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI believe the number of permutations will be too huge to iterate through in feasible time, and you'll likely end up with roughly or even exactly equal probabilities for each square. It's easy to prove there will be 4 lines of symmetry at the least (vertical, horizontal and 2 diagonal ones). What makes sense, however, is to gather statistics based on real AI vs human games. It's a plausible assumption that humans will tend to use some squares more than others. It may also be dependent on particular person, so the AI may learn and try to distinguish players.
      singulars
      1. PO
      1. USKaradur
    2. COPerhaps I could start with each square having the same probability, and as events happen, it updates squares around it in real time. The question then would be how exactly should the `probability_board` update in response to misses and sinks. Hits are easy
      singulars
      1. PO
      1. USDbz
    3. CO@Karadur - It seems you are only considering an empty board, there isn't much you can say about an empty board in any case, other then - don't guess near the eadg - which my method would solve. But the strategy only really gets interesting when the you already made some guesses. As for the large amount of permutations, the point is you don't need to check every permutation you only need to check (5+4+3+3+2)*2 = 34 options per square i.e. 3400 total, that's not much... plus OP's (@Dbz) suggestion makes it even easier.
      singulars
      1. PO
      1. USpseudoDust
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload