A* applied to minesweeper game

Artificial Intelligence Programming

Started by Backward April 12, 2013 02:25 PM

45 comments, last by Backward 10 years, 11 months ago

5,832

May 07, 2013 11:48 AM

(EDIT: The game also cheats for you on the first move, it is never a mine... presumably it moves the mine elsewhere in that case - on Windows anyway).

Uh...I've hit a mine on the first move. Just throwing that one out there.

On the version that ships with Windows? I never have... Are you sure it wasn't a minesweeper clone?

EDIT: And a quick test with a 10x10 board and the maximum number of mines (looks like 81, I tried 99 but it set it to 81) seems to confirm that the first click is always safe (played about 5 games).

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

Backward

127

Author

May 07, 2013 08:31 PM


bl_copy[b/12] = true;

I think these indexes are bad. Should it be bl_copy [(b - b %12)/12] [b%12] ?

alvaro

21,604

May 08, 2013 12:42 AM

bl_copy[b/12] = true;
I think these indexes are bad. Should it be bl_copy [(b - b )/12] ?

Hmmm... It should be bl_copy[bl/12][b%12]. I don't know what happened there... Editor ate my modulus operator?

EDIT: Yes! The editor eats modulus operators!

Backward

127

Author

May 08, 2013 08:29 PM

For bigger tables i don't get results... Is it possible to optimize it somehow?

Backward

127

Author

May 09, 2013 07:54 AM

Can i use any other algorithm to find probabilities? Does anyone know which one gives best results for all table sizes 9x9, 16x16 and 30*16?

alvaro

21,604

May 09, 2013 11:29 AM

Can you post an example of a position where the naive algorithm I posted doesn't produce any results? I am sure I can think of some refinements to make the algorithm more practical, and having some example to test on would help.

Backward

127

Author

May 09, 2013 12:09 PM




        {-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-2,-1,-1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1,-2,-1,-2, 1, 1, 1, 1, 1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1, 2, 2, 1, 1, 0, 0, 0, 1,-1,-1,-3},
	{-3,-1,-1,-1,-1,-1,-1, 1, 0, 0, 0, 0, 0, 0, 1,-1,-1,-3},
	{-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3}

This is the table i got when i opened one field. I found 3 mines and they are flagged. I put this table in your algorithm and nothing happens. Table has 40 mines (16x16).

alvaro

21,604

May 09, 2013 01:33 PM

After adapting my code to a board of size 16x16 with 37 bombs left to be found, it produced this after less than 4 seconds:

  -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1 
  -1 1565 1567 1565 1619 1614 1552 1621 1567 1625 1652 1588 1620 1549 1631 1614 1591   -1 
  -1 1593 1551 1621 1566 1549 1592 1624 1614 1504 1585 1624 1587 1567 1643 1568 1536   -1 
  -1 1679 1596 1583 1599 1594 1607 1565 1577 1519 1623 1648 1680 1601 1561 1559 1554   -1 
  -1 1599 1551 1612 1533 1579 1612 1594 1590 1564 1568 1594 1577 1564 1549 1612 1587   -1 
  -1 1548 1622 1603 1644 1644 1632 1535 1639 1630 1577 1565 1570 1565 1623 1621 1636   -1 
  -1 1597 1594 1589 1594 1646 1574 1637 1618 1597 1629 1566 1566 1595 1521 1682 1595   -1 
  -1 1660 1589 1587 1640 1543 1578 1546 1616 1559 1554 1604 1580 1601 1554 1528 1555   -1 
  -1 1487 1564 1579 1654 1592 1583 1551 1606 1585 1574 1677 1572 1590 1620 1629 1597   -1 
  -1 1589 1584 1585 1605 1565 1592 1532 1636 1494 1617 1616 1530 1656 1612 1597 1625   -1 
  -1 1568 1569 1638 1608 1690 1597 1658 1529 1580 1588 1558 1575 1644 1624 1533 1560   -1 
  -1 1608 1587 1646 1595 1604 1588 1630 1643 1594 1613 1638 1603 1603 1537 1581 1603   -1 
  -1 1617 1584 1591 1601 1573 1638 1610 1542 1558 1603 1599 1550 1655 1578 1599 1603   -1 
  -1 1543 1595 1570 1567 1522 1609 1565 1561    0    0    0   -1    0    0 1638 1503   -1 
  -1 1507 1555 1615 1560 1615    0   -1    0   -1   -1   -1   -1   -1   -1    0 1632   -1 
  -1 1515 1614 1625 1533 1616 5022   -1   -1   -1   -1   -1   -1   -1   -1 8362 1581   -1 
  -1 1570 1593 1573 1596 1626 4978   -1   -1   -1   -1   -1   -1   -1   -1 1638 1571   -1 
  -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1

EDIT: Better formatting.

Backward

127

Author

May 09, 2013 02:42 PM

In your algorithm if i understood well, you put randomly all rest mines and then you check is it possible. But there could be many situations when state is not consistent for example there is a square 2 but there are 3 mines around it. Why don't we find all possible consistent combinations and then check for every square how many times there was a mine? It will be just a kind of special case of your algorithm.

alvaro

21,604

May 09, 2013 08:00 PM

I am not sure I understand your suggestion. The brute-force nature of what I proposed will make it so that in many instances only a small fraction of the random distributions tried will be consistent with the known information. It is very reasonable to try to increase this fraction to make the algorithm practical, but most simple ways to that would bias the distributions so the measured probabilities might not be correct.

It can probably be done correctly, perhaps with some variation of the Metropolis algorithm, but I expect this will be tricky.

A* applied to minesweeper game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* applied to minesweeper game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines